큐(queue), 원형 큐(circular queue)

큐는 한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다. 새로운 원소가 삽입되는 끝을 rear이라 하고 원소가 삭제되는 끝을 front라 한다.

큐에 대한 제약이 의미하는 바는, 만약 원소 A, B, C, D, E를 이 순서대로 큐에 삽입한다면 제일 먼저 삭제되는 원소는 A라는 것이다. 이와 같이 큐에 제일 먼저 삽입된 원소가 제일 먼저 삭제되기 때문에, 이 큐를 선입선출(FIFO, First-In-First-Out) 리스트라고도 한다.

먼저 다음과 같이 큐에 삽입할 구조를 정의해주고, 배열 queue를 선언해 준다. 초기 상태의 배열에는 원소가 존재하지 않으므로, 첫 번째 원소의 인덱스(front)와 마지막 원소의 인덱스(rear)는 모두 -1이다.

이제 함수 addQ와 deleteQ를 구현해보자. queueFull의 구현은 stackFull의 구현과 비슷하다. 합수 addQ와 deleteQ는 구조적으로 스택의 push, pop 함수와 비슷하다.

스택은...