[자료구조] 큐 (Queue)

07. 큐 (Queue)

07-1. 큐의 이해와 ADT 정의

 

큐(Queue)는 선입선출 방식의 자료구조이다. FIFO(First-In, First-Out) 구조라고도 불린다.

따라서 스택과 달리 데이터를 넣을 땐 앞에서 넣고, 뺄 땐 뒤에서 빼는 구조이다.

큐도 스택처럼 배열을 기반으로, 연결 리스트를 기반으로 모두 작성 가능하다.

 

큐 자료구조의 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);
- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

 

07-2. 큐의 배열 기반 구현

 

배열 기반으로 큐를 작성하면 Front와 Rear을 가리키는 포인터를 사용하게 된다.

Enqueue 때마다 Rear가 같이 뒤로 늘어나고, Dequeue를 할 때마다 Front가 앞에서 뒤로 따라간다.

하지만 이렇게 하면 다음 사진과 같은 경우, 큐에 빈공간이 있지만 이를 가리키는 포인터가 없어 값을 저장할 수 없게된다.

배열 큐의 문제상황

따라서 Rear포인터가 배열의 끝에 도착하면, 다시 맨 앞으로 보내야 한다. (Front 포인터도 마찬가지)

이러한 방식으로 동작하는 배열기반 큐를 원형 큐(circular queue)라고 한다. (배열 기반 큐는 대부분 원형 큐를 의미)

 

- 원형 큐 (Circular Queue)의 소개

원형 큐의 경우 배열의 길이가 N이면 데이터가 N-1개일 때 다 찬 것으로 간주한다. (배열을 꽉 채우지 않는다)

왜냐하면 꽉 채워 넣는 경우, 큐가 다 찼을때나 비었을때나 모두 F가 R보다 한칸 앞서기 때문에 구분 할 수 없기때문이다.

따라서 원형 큐는 다음과 같은 특성을 가지게 된다.

원형 큐가 텅 빈 상태: F와 R이 동일한 위치를 가리킨다.

원형 큐가 꽉 찬 상태: F가 R의 앞칸을 가리킨다.

원형 큐 (Circular Queue)

 

07-3. 큐의 연결 리스트 기반 구현

 

연결 리스트로 큐를 구현할 때는, Enqueue의 경우 뒤에서 넣고, Dequeue의 경우 앞에서 부터 빼는 방식으로 구현할 수 있다.

마지막 노드를 Dequeue할 땐, F는 자동으로 마지막 노드의 next가 되기 때문에 NULL값이 되지만,

R의 경우 그냥 쓰레기 값을 가진 채로 둬도 문제가 생기지는 않는다.

 

연결 리스트 기반 큐

 

07-4. 큐의 활용

 

큐는 특정 현상을 시뮬레이션 하는데 사용될 수 있다.

나는 해당 단원을 통해 햄버거 가게 대기실 수용인원을 시뮬레이션 해보는 실습을 해보았다.

코드를 보고 이해는 할 수 있지만 사실 이 코드를 혼자 짜라고 하면 짤 수 있을지 의문이긴 하다..ㅎㅎ..

코드는 밑에 깃헙 주소로 남기도록 하겠다.

 

햄버거 실습 코드: https://github.com/z0299/DataStructure/tree/main/Queue

GitHub - z0299/DataStructure: to study data structure

 

07-5. 덱(Deque)의 이해와 구현

 

덱(Dequeue와는 다르다. Deque이다.)은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조이다.

즉 데이터를 넣고 빼는데 방식의 제한이 없다.

따라서 Deque은 double-ended queue를 줄여 표현한 스택과 큐의 특성을 모두 갖는 자료구조이다.

덱 또한 배열 기반과 연결 리스트 기반으로 작성이 가능하다. 하지만 덱의 구현에 가장 어울리는 방식은 '양방향 연결 리스트'이다.

큐와 덱의 차이

 

덱 자료구조의 ADT는 다음과 같다.

void DequeInit(Deque * pdeq);
- 덱의 초기화를 진행한다.
- 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.

int DQIsEmpty(Deque * pdeq);
- 덱이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void DQAddFirst(Deque * pdeq, Data data);
- 덱의 머리에 데이터를 저장한다. data로 전달된 값을 저장한다.

void DQAddLast(Deque * pdeq, Data data);
- 덱의 꼬리에 데이터를 저장한다. data로 전달된 값을 저장한다.

Data DQRemoveFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸한다.

Data DQRemoveLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.

Data DQGetFrist(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.

Data DQGetLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.