큐 (Queue)
들어가는 말
스택은 한쪽 끝에서 데이터를 넣고 꺼내는 LIFO(Last In, First Out) 구조였다.
반면 큐(queue)는 줄이나 대기열을 뜻하며, 양쪽 끝의 역할이 나뉜 자료구조다.
enqueue 연산으로 한쪽 끝에 데이터를 넣고, dequeue 연산으로 반대쪽 끝에서 데이터를 꺼낸다.
따라서 가장 먼저 들어온 데이터가 가장 먼저 나오는 FIFO(First In, First Out) 구조가 된다.
은행 창구에 먼저 줄을 선 고객이 먼저 업무를 보는 모습을 떠올리면 이해하기 쉽다.
배열 기반 큐
선형 큐의 한계
시도 1: 출구 인덱스를 0번에 고정
출구 인덱스를 0번으로 생각하고, 값이 들어올 때마다 배열의 뒤쪽에 차례로 저장해보자.
5개의 값이 들어오면 배열은 다음과 같은 모습이 된다.
1. Before dequeue
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4이 상태에서 dequeue 연산을 수행해 보자.
2. After dequeue and shifting
+---+---+---+---+---+
| b | c | d | e | |
+---+---+---+---+---+
0 1 2 3 4출구 인덱스를 0번으로 고정했으므로, a를 dequeue한 뒤에 끝내서는 안 된다.
다음 dequeue를 위해 배열에 남은 요소를 한 칸씩 앞으로 옮겨야 한다.
이처럼 dequeue할 때마다 남은 요소를 옮기면, 요소가 n개일 때 최대 n - 1번의 이동이 필요하다.
따라서 출구 인덱스를 0번에 고정하는 방식은 비효율적이다.
시도 2: front와 rear 인덱스 사용
이전 방식의 문제를 해결하기 위해 입구와 출구의 위치를 front와 rear 인덱스로 각각 관리한다.
두 인덱스의 초기값은 모두 0으로 둔다.
먼저 배열에 1개의 값을 저장해보자.
1. After the first enqueue
front rear
| |
v v
+---+---+---+---+---+
| a | | | | |
+---+---+---+---+---+
0 1 2 3 4rear가 가리키던 0번 인덱스에 값을 저장한 뒤 rear를 1 증가시켰다.
이제 enqueue를 반복해 배열을 끝까지 채워 보자.
2. After filling the array
front rear
| |
v v
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4 5값을 배열에 삽입할 때마다 rear를 증가시켰다.
따라서 배열을 모두 채운 지금 rear는 배열의 길이와 같다.
이 상태에서 dequeue 연산을 수행해 보자.
3. After dequeue
front rear
| |
v v
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4 5dequeue는 front 인덱스에 저장된 값을 반환하고, front를 다음 인덱스로 옮긴다.
dequeue한 뒤에도 a가 배열에 남아 있어 의문이 들 수 있다.
a는 큐의 인터페이스를 통해 더 이상 접근할 수 없으므로, 배열에 남아 있어도 논리적으로는 삭제된 상태다.
이제 계속해서 dequeue 연산을 수행해 보면 문제점이 드러난다.
4. After four dequeues
front rear
| |
v v
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4 54번 dequeue한 뒤에는 e만 유효한 원소로 남는다.
배열 앞부분은 논리적으로 삭제된 원소가 차지하고 있지만, rear는 이미 배열의 끝에 도달해 있다.
따라서 앞쪽에 빈 공간이 남아 있어도 새로운 원소를 enqueue할 수 없다.
오버플로우는 저장 공간이 가득 찬 상태에서 데이터를 더 넣으려다 넘쳐흐르는 상황을 말한다.
반면 이처럼 실제로는 공간이 남아 있는데도 삽입할 수 없는 상황을 가짜 오버플로(false overflow)라고 한다.
원형 큐
배열 기반 큐에서는 앞서 살펴본 두 방식의 문제가 발생한다.
이를 해결하는 방법은 rear가 배열의 마지막 인덱스를 넘으면 다시 0번 인덱스를 가리키게 하면 된다.
이처럼 배열의 처음과 끝을 연결해 논리적으로 원형처럼 사용하는 구조를 원형 큐라고 한다.
이 글에서는 최대 용량이 정해진 원형 큐를 살펴보겠다.
빈 상태와 가득 찬 상태 구분하기
원형 큐를 사용하면 앞서 살펴본 문제는 해결할 수 있지만, 또 다른 문제가 생긴다.
그림으로 살펴보자.
1. Initial state (empty)
front == rear
|
v
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
0 1 2 3 4
2. After five enqueues (full)
front == rear
|
v
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4
3. After four dequeues
rear front
| |
v v
+---+---+---+---+---+
| x | x | x | x | e |
+---+---+---+---+---+
0 1 2 3 41번 그림은 원소가 없는 초기 상태로, front와 rear의 초기값은 모두 0이다.
2번 그림에서는 원소를 계속 enqueue하면서 증가한 rear가 배열을 한 바퀴 돌아 다시 0번 인덱스를 가리킨다.
3번 그림에서 dequeue하면 front와 rear는 다시 같은 인덱스를 가리킨다.
따라서 두 상태 모두 front와 rear가 0번을 가리키므로, 두 인덱스만으로는 큐가 비었는지 가득 찼는지 알 수 없다.
그렇다면 1번 그림에서 두 인덱스의 초기값을 0이 아닌 -1로 설정하면 해결되지 않을까?
초기값을 -1로 설정해도 인덱스는 배열을 한 바퀴 돌면 다시 0번부터 사용한다.
결국 dequeue와 enqueue를 반복하면 front와 rear가 다시 같은 인덱스를 가리키므로, 이 방법으로는 빈 상태와 가득 찬 상태를 구분할 수 없다.
그래도 과정을 그림으로 살펴보자.
front와 rear를 -1에서 시작하고, enqueue의 동작은 rear를 하나 증가시킨 뒤 해당 위치에 원소를 삽입한다고 가정하자.
1. Initial state (empty)
front = rear = -1
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
0 1 2 3 4
2. After five enqueues
front = -1 rear
|
v
+---+---+---+---+---+
| a | b | c | d | e |
+---+---+---+---+---+
0 1 2 3 4
3. After four dequeues
front rear
| |
v v
+---+---+---+---+---+
| x | x | x | x | e |
+---+---+---+---+---+
0 1 2 3 4
4. After four more enqueues (full)
front == rear
|
v
+---+---+---+---+---+
| f | g | h | i | e |
+---+---+---+---+---+
0 1 2 3 4
5. After five dequeues (empty)
front == rear
|
v
+---+---+---+---+---+
| x | x | x | x | x |
+---+---+---+---+---+
0 1 2 3 4처음 5개의 원소를 삽입하면 rear는 마지막 인덱스인 4번을 가리키므로, 초기 상태와 가득 찬 상태를 구분할 수 있다.
하지만 dequeue와 enqueue를 반복해 rear가 배열을 한 바퀴 돌면 front와 rear가 다시 같은 인덱스를 가리킨다.
이때 두 인덱스만으로는 큐가 비어 있는지 가득 찬 것인지 알 수 없다.
front와 rear를 같은 인덱스로 초기화한다고 가정하면, 초기값이 어떤 인덱스이든 두 인덱스만으로는 빈 상태와 가득 찬 상태를 구분할 수 없다.
배열 한 칸 비워 두기
이 문제를 해결하려면 원소 수를 관리하는 size 또는 count 변수를 둘 수도 있다.
이 글에서는 배열의 한 칸을 비워 두는 방법을 사용하겠다.
front와 rear는 모두 0번 인덱스에서 시작한다고 가정하자.
원소를 삽입한 뒤에는 rear를, 삭제한 뒤에는 front를 다음 인덱스로 옮긴다.
front와 rear가 같은 인덱스를 가리키면 빈 상태이고, rear의 다음 인덱스가 front이면 가득 찬 상태다.
따라서 길이가 5인 배열에서는 한 칸을 항상 비워 두므로 최대 4개의 원소만 저장할 수 있다.
아래 배열 그림에서 비워 두는 칸을 -로 표시하겠다.
1. After four enqueues (full)
front rear
| |
v v
+---+---+---+---+---+
| a | b | c | d | - |
+---+---+---+---+---+
0 1 2 3 4
2. After two dequeues
front rear
| |
v v
+---+---+---+---+---+
| x | x | c | d | - |
+---+---+---+---+---+
0 1 2 3 4
3. After two more enqueues (full)
rear front
| |
v v
+---+---+---+---+---+
| f | - | c | d | e |
+---+---+---+---+---+
0 1 2 3 41번 그림에서 rear가 가리키는 4번 인덱스는 비어 있지만, rear의 다음 인덱스가 front와 같으므로 가득 찬 상태다.
2번 그림에서 두 원소를 삭제하면 front는 2번 인덱스로 이동한다.
이후 두 원소를 더 삽입하면, 3번 그림처럼 rear는 4번과 0번 인덱스에 값을 차례로 저장한다.
중요한 점은 비워 두는 한 칸의 위치가 고정되어 있지 않다는 것이다.
front와 rear는 연산에 따라 계속 이동하므로, 비워 두는 한 칸의 위치도 함께 바뀐다.
따라서 rear의 다음 인덱스가 front를 가리키면 가득 찬 상태로 판단한다.
소스 코드
array_queue.h
#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H
#include <stdbool.h>
#define QUEUE_CAPACITY 5
typedef int Data;
typedef struct Queue
{
Data values[QUEUE_CAPACITY];
int front;
int rear;
} Queue;
bool queue_init(Queue* queue);
bool enqueue(Queue* queue, Data value);
bool dequeue(Queue* queue, Data* value);
bool queue_is_empty(const Queue* queue);
bool queue_is_full(const Queue* queue);
#endif /* ARRAY_QUEUE_H */array_queue.c
#include <stdlib.h>
#include "array_queue.h"
bool queue_init(Queue* queue)
{
if (queue == NULL)
return false;
queue->front = 0;
queue->rear = 0;
return true;
}
bool enqueue(Queue* queue, Data value)
{
if (queue_is_full(queue))
return false;
queue->values[queue->rear] = value;
queue->rear = (queue->rear + 1) % QUEUE_CAPACITY;
return true;
}
bool dequeue(Queue* queue, Data* value)
{
if (queue_is_empty(queue))
return false;
*value = queue->values[queue->front];
queue->front = (queue->front + 1) % QUEUE_CAPACITY;
return true;
}
bool queue_is_empty(const Queue* queue)
{
return queue->front == queue->rear
}
bool queue_is_full(const Queue* queue)
{
return (queue->rear + 1) % QUEUE_CAPACITY == queue->front;
}main.c
#include <stdio.h>
#include "array_queue.h"
int main(void)
{
Queue queue;
Data value;
queue_init(&queue);
for (int i = 0; i < 5; i++)
{
if (enqueue(&queue, i + 1))
printf("enqueue: %d\n", i + 1);
else
printf("enqueue failed: %d\n", i + 1);
}
while (!queue_is_empty(&queue))
{
dequeue(&queue, &value);
printf("dequeue: %d\n", value);
}
return 0;
}연결 리스트 기반 큐
배열 기반 큐에서는 구현 전에 고려할 부분이 많았다.
반면 연결 리스트 기반 큐는 배열 기반 큐보다 간단하며, 이전에 구현한 연결 리스트보다도 쉽게 구현할 수 있다.
큐에서는 중간에 노드를 삽입하거나 삭제할 필요가 없기 때문이다.
연결 리스트에서는 포인터 이름으로 head와 tail을 사용했지만, 연결 리스트 기반 큐에서는 각각 front와 rear를 사용하겠다.
삽입은 rear가 가리키는 마지막 위치에서, 삭제는 front가 가리키는 맨 앞 위치에서 수행한다.
소스 코드
linked_list_queue.h
#ifndef LINKED_LIST_QUEUE_H
#define LINKED_LIST_QUEUE_H
#include <stdbool.h>
typedef int Data;
typedef struct Node
{
Data value;
struct Node* next;
} Node;
typedef struct Queue
{
Node* front;
Node* rear;
} Queue;
bool queue_init(Queue* queue);
bool enqueue(Queue* queue, Data value);
bool dequeue(Queue* queue, Data* value);
bool queue_is_empty(const Queue* queue);
#endif /* LINKED_LIST_QUEUE_H */linked_list_queue.c
#include <stdlib.h>
#include "linked_list_queue.h"
bool queue_init(Queue* queue)
{
if (queue == NULL)
return false;
queue->front = NULL;
queue->rear = NULL;
return true;
}
bool enqueue(Queue* queue, Data value)
{
if (queue == NULL)
return false;
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->value = value;
new_node->next = NULL;
if (queue->front == NULL)
queue->front = new_node;
else
queue->rear->next = new_node;
queue->rear = new_node;
return true;
}
bool dequeue(Queue* queue, Data* value)
{
if (queue_is_empty(queue))
return false;
Node* del_node = queue->front;
*value = del_node->value;
queue->front = queue->front->next;
if (queue->front == NULL)
queue->rear = NULL;
free(del_node);
return true;
}
bool queue_is_empty(const Queue* queue)
{
return queue == NULL || queue->front == NULL;
}시간 복잡도
삽입
배열 기반 큐와 연결 리스트 기반 큐 모두 삽입에 O(1)이 걸린다.
배열 기반 큐에서는 rear 인덱스 위치에 원소를 저장한 뒤 rear를 다음 위치로 옮기기만 하면 된다.
연결 리스트 기반 큐에서는 rear 포인터가 가리키는 마지막 노드 뒤에 새 노드를 연결한 뒤 rear를 갱신하면 된다.
삭제
배열 기반 큐와 연결 리스트 기반 큐 모두 삭제에 O(1)이 걸린다.
배열 기반 큐에서는 front 인덱스의 원소를 반환한 뒤 front를 다음 위치로 옮기기만 하면 된다.
연결 리스트 기반 큐에서는 front를 다음 노드로 옮긴 뒤 기존 노드를 해제하면 된다.