큐(Queue)

큐의 이해

큐는 스택과 함께 언급되고 또 비교되는 자료구조이다.  스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한 차이점이다.

큐의 자료구조를 실생활에서 예를 들자면 터널, 고무 호스, 양쪽으로 구멍 난 통, 줄을 서는 것 등등이 있다. 

이렇듯 큐는 '선입선출' 구조의 자료구조이다. 때문에 FIFO(First-In, First-Out) 구조의 자료구조이다.

큐의 ADT 정의

스택과 마찬가지로 큐의 ADT도 정형화된 편이다. 큐의 핵심 연산

enqueue        : 큐에 데이터를 넣는 연산

dequeue        : 큐에서 데이터를 꺼내는 연산

보편적인 큐 자료구조의 ADT

void QueueInit(Queue * pq);

- 큐의 초기화를 진행한다.

- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다. 

int QIsEmpty(Queue * pq);

- 큐가 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)를 반환한다.

void Enqueue(Queue  * pq, Data data);

- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue * pq);

- 저장순서가 가장 앞선 데이터를 삭제한다.

- 삭제된 데이터는 반환된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue * pq);

- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.