Chapter 07. 큐의 이해와 ADT 정의

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

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

---

스택과 마찬가지로 큐의 ADT도 정형화된 편입니다. 큐의 핵심이라고 할 수 있는 두 가지 연산을 소개하겠습니다.

• enqueue    큐에 데이터를 넣는 연산
• dequeue    큐에서 데이터를 꺼내는 연산

 

스택에서 데이터를 넣고 빼는 연산을 가리켜 각각 push, pop이라고 하는 것처럼, 큐에서 데이터를 넣고 빼는 연산에 대해서도 각각 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)
//저장 순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
//본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

큐의 ADT를 보면 스택의 ADT와 상당히 유사함을 확인할 수 있습니다. 

 

이제 큐를 직접 구현해 볼 것입니다. 큐도 스택과 마찬가지로 배열 기반으로도 구현할 수 있고, 연결 리스트 기반으로도 구현할 수 있습니다.