여러 개의 데이터 항목들이 일정한 순서로 나열된 자료 구조로, 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있다. 큐에 저장된 데이터 항목들은 먼저 삽입된 것이 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제된다. 그래서 큐를 선입 선출 리스트(First In First out)라 부른다.
큐의 종류
- 선형(Linear) 큐
- 이동(Moving) 큐
- 환형(Circular) 큐
선형 큐의 경우 삽입하는 점을 Rear Pointer, 시작하는 점을 Front Pointer라 부르면 이 데이터 공간을 고정되어 있다. 따라서 할당된 공간의 끝까지 Rear Pointer가 도달하면 더 이상 자료를 삽입할 수 없는 상태인 rear = N 상태가 되면 오버 플러우(overflow)가 발생한다. 이 오버플로우를 해결하는 방법에는 2가지가 있는 이동큐(Moving Queue) 방식과 환영큐(circular Queue) 방식이 있다.
이동 큐 방식은 큐내의 원소들을 이동시키는 방법이며 원형 큐 방식은 큐 구조를 원형을 연결하여 rear포인터의 값을 변화시켜 가용공간에 원소를 삽입하는 방식이다.