강의정리

[자료구조] 큐

i1hwan

2025년 4월 24일 • 17 min read

큐(Queue)의 개념과 구조

큐(Queue)란?

스택과 유사하게 삽입과 삭제의 위치가 제한된 유한 순서 리스트(List)이다.
데이터가 들어온 순서대로 처리되는 선입선출(FIFO: First-In, First-Out)의 특성을 갖는 자료구조이다.
- 먼저 들어온 데이터가 먼저 나간다.
- ex) 계산대의 대기열, 매표소 줄서기
스택과의 차이점: 스택은 한쪽 끝(top)에서만 삽입/삭제가 이루어지지만, 큐는 양쪽 끝에서 삽입과 삭제가 각각 이루어진다.

큐의 기본 구조 (FIFO)

삽입: 큐의 후단(rear)에서만 이루어진다.
삭제: 큐의 전단(front)에서만 이루어진다.
데이터 A, B, C를 순서대로 삽입하면, 삭제(꺼낼) 때도 같은 순서인 A, B, C로 나온다.

전단(Front)과 후단(Rear)

전단(front): 가장 먼저 삽입된 요소가 위치하는 곳으로, 삭제가 이루어지는 부분이다. (큐의 '머리')
후단(rear): 가장 마지막에 삽입된 요소가 위치하는 곳으로, 삽입이 이루어지는 부분이다. (큐의 '꼬리')

큐의 추상 자료형(ADT) 및 연산

큐의 ADT 정의

데이터: 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음
연산:
- init(): 큐를 초기화한다.
- enqueue(e): 요소 e를 큐의 맨 뒤(후단)에 삽입한다.
- dequeue(): 큐의 맨 앞(전단) 요소를 삭제하고 반환한다.
- is_empty(): 큐가 비어있으면 TRUE를, 아니면 FALSE를 반환한다.
- is_full(): 큐가 가득 차 있으면 TRUE를, 아니면 FALSE를 반환한다.
- peek(): 큐의 맨 앞(전단) 요소를 삭제하지 않고 반환한다. (내용 확인만)
- size(): 큐의 모든 요소들의 개수를 반환한다.

주요 연산 (enqueue, dequeue, peek 등)

enqueue(e): 큐의 후단(rear)에 요소 e를 추가한다. 큐의 상태를 변화시킨다.
dequeue(): 큐의 전단(front)에서 가장 오래된 요소를 제거하고 반환한다. 큐의 상태를 변화시킨다.
peek(): 큐의 전단(front) 요소를 제거하지 않고 값만 확인하여 반환한다. 큐의 상태를 변화시키지 않는다.

스택과의 연산 비교

자료구조	삽입 연산자	삽입 위치	삭제 연산자	삭제 위치
스택	`push`	`top`	`pop`	`top`
큐	`enqueue`	`rear`	`dequeue`	`front`

큐 연산 예시 (오버플로, 언더플로)

오버플로(Overflow): 큐가 가득 찬(포화) 상태에서 enqueue 연산을 시도할 때 발생하는 오류이다.
언더플로(Underflow): 큐가 비어있는(공백) 상태에서 dequeue 또는 peek 연산을 시도할 때 발생하는 오류이다.

큐의 활용

버퍼(Buffer)

갑자기 데이터가 몰려드는 경우, 이들을 임시로 보관하는 장소로 큐가 사용된다.
처리 속도가 다른 두 장치(ex: 빠른 CPU와 느린 프린터) 사이에서 데이터 처리 속도 차이를 극복하기 위해 사용된다.
- CPU는 데이터를 버퍼 큐에 빠르게 보내고 다른 작업을 수행할 수 있다.
- 프린터는 버퍼 큐에서 데이터를 순서대로 꺼내어 자신의 속도에 맞게 처리한다.
버퍼링(Buffering): 큐를 사용하여 버퍼를 구현하고 관리하는 기법이다.

시뮬레이션

컴퓨터로 현실 세계의 상황을 모방하는 분야에서 널리 사용된다.
- ex) 공항에서의 비행기 이착륙 대기열 관리
- ex) 은행 창구에서의 고객 대기열 관리

알고리즘

다양한 알고리즘 구현에 활용된다.
- 너비 우선 탐색(BFS, Breadth-First Search): 그래프나 트리 탐색 시 방문할 노드를 저장하는 데 사용된다.
- 레벨 순회(Level Order Traversal): 트리 구조에서 같은 레벨의 노드를 순서대로 방문할 때 사용된다.
- 기수 정렬(Radix Sort) 등

운영체제 작업 큐

프린터 버퍼 큐(Printer Buffer Queue): CPU에서 프린터로 보낸 인쇄 작업 데이터들을 순서대로(선입선출) 저장하고, 프린터가 처리할 수 있도록 관리한다.
스케줄링 큐(Scheduling Queue): 멀티태스킹 환경에서 CPU 사용을 요청한 프로세스(작업)들의 순서를 관리하고 스케줄링하는 데 사용된다.
- 준비 큐(Ready Queue), 대기 큐(Waiting Queue) 등 다양한 종류가 있다.

배열을 이용한 큐 구현

선형 큐 (Linear Queue)

1차원 배열을 이용하여 큐를 구현하는 가장 간단한 방법이다.
구조:
- data[MAX_SIZE]: 요소를 저장할 1차원 배열 (큐의 크기 = MAX_SIZE)
- front: 큐의 첫 번째 요소 바로 앞[[1]]의 인덱스를 저장하는 변수
- rear: 큐의 마지막 요소의 인덱스를 저장하는 변수

[[1]]: front를 첫 번째 요소의 인덱스로 정의시켜도 문제는 없다.

상태 표현:
- 초기 상태: front = rear = -1
- 공백 상태: front == rear
- 포화 상태: rear == MAX_SIZE - 1 (배열의 마지막 인덱스)
동작:
- 삽입(enqueue): rear를 1 증가시킨 후, data[rear] 위치에 요소를 저장한다.
- 삭제(dequeue): front를 1 증가시킨 후, data[front] 위치의 요소를 반환한다.
- 검색(peek): data[front + 1] 위치의 요소를 반환한다. (front는 첫 요소 바로 앞을 가리키므로)

// 선형 큐 생성 (초기화)
void Create_Queue() {
    int Queue[MAX_SIZE];
    front = -1;
    rear = -1;
}

// 공백 상태 검사
int is_empty() {
    if (front == rear) return 1; // TRUE
    else return 0; // FALSE
}

// 포화 상태 검사
int is_full() {
    if (rear == MAX_SIZE - 1) return 1; // TRUE
    else return 0; // FALSE
}

// 삽입 연산
void enqueue(Element e) {
    if (is_full()) {
        // 포화 상태 처리 (오류 또는 종료)
        exit(1);
    } else {
        rear = rear + 1;
        Queue[rear] = e;
    }
}

// 삭제 연산
Element dequeue() {
    if (is_empty()) {
        // 공백 상태 처리 (오류 또는 종료)
        exit(1);
    } else {
        front = front + 1;
        return Queue[front];
    }
}

// 검색 연산
Element peek() {
    if (is_empty()) {
        // 공백 상태 처리
        exit(1);
    } else {
        return Queue[front + 1];
    }
}

선형 큐의 문제점과 해결 방법

잘못된 포화 상태 인식 (False Overflow):
- 큐에서 삽입과 삭제를 반복하면 front와 rear가 계속 증가하여 배열의 뒤쪽으로 이동한다. (front와 rear가 증가하는 연산만 있으므로)
- rear가 배열의 끝(MAX_SIZE - 1)에 도달하면, 배열의 앞부분에 빈 공간이 있더라도 포화 상태로 잘못 인식되어 더 이상 삽입할 수 없게 된다.
해결 방법 1: 요소 이동:
- 삽입 시 포화 상태로 인식되면, 큐에 저장된 모든 요소를 배열의 앞부분으로 이동시키는 방법이다.
- 빈 공간을 확보하여 추가 삽입이 가능해진다.
- 단점: 요소 이동 작업은 많은 요소를 복사해야 하므로 연산이 복잡하고 비효율적이다. 삽입 연산의 시간 복잡도가 O(n)이 될 수 있다.
해결 방법 2: 원형 큐 사용:
- 1차원 배열을 사용하되, 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하는 방식이다. (더 효율적이고 일반적인 해결책)

원형 큐 (Circular Queue)

선형 큐의 문제점을 해결하기 위해 배열을 원형으로 간주하여 사용하는 큐이다.
배열의 마지막 인덱스 다음에 다시 첫 번째 인덱스(0)가 오도록 인덱스를 순환시킨다.
인덱스 회전 (Modulo 연산 활용):
- front와 rear가 배열의 끝에 도달하면 다시 0으로 돌아가도록 나머지(modulo, %) 연산자를 사용한다.
- 전단 회전 (시계 방향): front = (front + 1) % MAX_SIZE
- 후단 회전 (시계 방향): rear = (rear + 1) % MAX_SIZE
구조:
- data[MAX_SIZE]: 요소를 저장할 배열
- front: 첫 번째 요소 바로 앞[[2]]의 인덱스
- rear: 마지막 요소의 인덱스

[[2]]: 선형 큐와 달리 원형 큐에서 front는 첫 번째 요소의 바로 앞을 가리켜야 한다. 공백 상태와 포화 상태가 구분되지 않기 때문이다.

상태 표현 (중요):
- 초기 공백 상태: front = rear = 0 (또는 특정 값, 구현에 따라 다를 수 있음)
- 공백 상태 구분: front == rear
- 포화 상태 구분: 공백 상태(front == rear)와 구별하기 위해 배열의 한 칸은 항상 비워두는 전략을 사용한다.
  - 즉, 큐에 최대 MAX_SIZE - 1개의 요소만 저장한다.
  - 포화 상태 조건: (rear + 1) % MAX_SIZE == front (rear 다음 칸이 front이면 포화)
연산:
- 초기화 init(): front = rear = 0;
- 공백 검사 is_empty(): return (front == rear);
- 포화 검사 is_full(): return ((rear + 1) % MAX_SIZE == front);
- 삽입 enqueue(e):
  1. 포화 상태(is_full())인지 검사한다.
  2. rear를 시계 방향으로 회전시킨다: rear = (rear + 1) % MAX_SIZE;
  3. data[rear] 위치에 요소 e를 저장한다.
- 삭제 dequeue():
  1. 공백 상태(is_empty())인지 검사한다.
  2. front를 시계 방향으로 회전시킨다: front = (front + 1) % MAX_SIZE;
  3. data[front] 위치의 요소를 반환한다.
- 검색 peek():
  1. 공백 상태(is_empty())인지 검사한다.
  2. front의 다음 위치인 data[(front + 1) % MAX_SIZE]의 요소를 반환한다. (front 자체는 비어있음)

// 원형 큐 구현 예시 (C 코드 스타일)
#define MAX_SIZE 8
typedef int Element;
Element data[MAX_SIZE];
int front = 0;
int rear = 0;

// 포화 상태 검사 (알고리즘 4.2와 동일)
int is_full() {
    return ((rear + 1) % MAX_SIZE == front);
}

// 삽입 연산 (알고리즘 4.4)
void enqueue(Element e) {
    if (is_full()) {
        error("overflow");
    } else {
        rear = (rear + 1) % MAX_SIZE;
        data[rear] = e;
    }
}

// 삭제 연산 (알고리즘 4.5)
Element dequeue() {
    if (is_empty()) {
        error("underflow");
    } else {
        front = (front + 1) % MAX_SIZE;
        return data[front];
    }
}

// 검색 연산 (알고리즘 4.6)
Element peek() {
    if (is_empty()) {
        error("underflow");
    } else {
        return data[(front + 1) % MAX_SIZE];
    }
}

💡

원형 큐에서 저장된 요소의 개수 구하는 방법
rear-front라고 생각할 수 있지만, 이 값은 음수가 될 수 있으므로 (rear - front + MAX_SIZE) % MAX_SIZE로 큐에 저장된 요소의 수를 구할 수 있다.

덱(Deque)

덱(Deque)이란?

Double-Ended Queue의 줄임말이다.
큐의 양쪽 끝, 즉 전단(front)과 후단(rear) 모두에서 삽입과 삭제가 가능한 큐이다.
- 큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조로 생각할 수 있다.
큐의 확장된 형태이며, 스택과 큐의 특징을 모두 갖는다.
제한: 양쪽 끝에서의 연산만 가능하며, 여전히 중간에 요소를 삽입하거나 삭제하는 것은 허용되지 않는다.

덱의 추상 자료형(ADT)

데이터: 전단과 후단을 통한 접근을 허용하는 요소들의 모음
연산:
- init(): 덱을 초기화한다.
- is_empty(): 덱이 비어 있으면 TRUE, 아니면 FALSE 반환. (큐와 동일)
- is_full(): 덱이 가득 차 있으면 TRUE, 아니면 FALSE 반환. (큐와 동일)
- add_front(e): 맨 앞(전단)에 새로운 요소 e를 추가한다. (큐에는 없는 연산)
- delete_front(): 맨 앞(전단)의 요소를 꺼내서 반환한다. (큐의 dequeue와 동일)
- get_front(): 맨 앞(전단)의 요소를 꺼내지 않고 반환한다. (큐의 peek와 동일)
- add_rear(e): 맨 뒤(후단)에 새로운 요소 e를 추가한다. (큐의 enqueue와 동일)
- delete_rear(): 맨 뒤(후단)의 요소를 꺼내서 반환한다. (큐에는 없는 연산)
- get_rear(): 맨 뒤(후단)의 요소를 꺼내지 않고 반환한다. (큐에는 없는 연산)
- size(): 덱 내의 모든 요소 개수를 반환한다.

💡

덱의 연산 중 add_rear, delete_front, get_front는 큐의 enqueue, dequeue, peek과 기능적으로 동일하다. 또한, 덱의 후단을 스택의 top으로 간주하면 add_rear, delete_rear, get_rear는 스택의 push, pop, peek과 같다.

덱의 구현 (원형 덱 활용)

덱은 양쪽 끝에서 삽입/삭제가 빈번하므로, 순차 자료구조(배열)보다는 이중 연결 리스트(Doubly Linked List)를 사용하는 것이 구조적으로 더 효율적일 수 있다. (크기 변화, 순서 변화에 유연)
하지만 배열을 이용한다면, 원형 큐와 유사하게 원형 덱(Circular Deque)으로 구현하는 것이 좋다.
원형 덱의 특징:
- 원형 큐의 구조와 연산을 기반으로 한다.
- 추가 연산 구현: add_front(), delete_rear(), get_rear() 구현이 필요하다.
- 반시계 방향 회전 필요: add_front()와 delete_rear() 연산은 인덱스를 감소시켜야 하므로 반시계 방향 회전 로직이 필요하다.[[3]]
  - 전단 회전 (반시계): front = (front - 1 + MAX_SIZE) % MAX_SIZE
  - 후단 회전 (반시계): rear = (rear - 1 + MAX_SIZE) % MAX_SIZE

[[3]]: 원형 큐에서 시계 방향 회전과 다르게 인덱스가 음수가 되지 않도록 덱 사이즈를 더해준다.

원형 덱 연산:
- add_rear(e): 원형 큐의 enqueue(e)와 동일.
- delete_front(): 원형 큐의 dequeue()와 동일.
- get_front(): 원형 큐의 peek()와 동일.
- add_front(e):
  1. 포화 상태(is_full()) 검사.
  2. data[front] 위치에 요소 e를 저장한다. (front는 현재 비어있는 위치)
  3. front를 반시계 방향으로 회전시킨다: front = (front - 1 + MAX_SIZE) % MAX_SIZE;
- delete_rear():
  1. 공백 상태(is_empty()) 검사.
  2. 현재 rear 위치의 요소를 임시 변수(prev)에 저장한다. (또는 data[rear]를 바로 반환)
  3. rear를 반시계 방향으로 회전시킨다: rear = (rear - 1 + MAX_SIZE) % MAX_SIZE;
  4. 저장해둔 prev 위치의 요소 (또는 data[prev])를 반환한다.
- get_rear():
  1. 공백 상태(is_empty()) 검사.
  2. data[rear] 위치의 요소를 반환한다. (덱 상태 변경 없음)

큐와 덱의 응용: 미로 탐색

미로 탐색 문제

미로에 갇힌 상태에서 출구를 찾는 문제이다.
시행착오법(Trial and Error): 하나의 경로를 선택해 시도하고, 막다른 길에 도달하면 왔던 길을 되돌아가 다른 경로를 시도하는 방식이다.
핵심: 시도 중 막혔을 때, 다시 시도할 수 있는 다른 경로(갈림길 정보)들을 저장해 두어야 한다.
자료구조 활용: 경로 정보를 저장하고 다음에 시도할 경로를 선택하는 방식에 따라 다른 자료구조를 사용한다. 스택과 큐가 대표적이다.

깊이 우선 탐색 (DFS, Depth First Search)

방식: 가장 최근에 저장한 경로(갈림길)를 우선적으로 선택하여 탐색을 계속 진행하는 방법이다. (파고드는 방식)
자료구조: 스택(Stack)을 사용하여 구현한다. (LIFO: Last-In, First-Out)
덱을 스텍처럼 활용: 덱의 후단(rear)에서 삽입(add_rear)과 삭제(delete_rear)를 모두 수행하면 스택처럼 동작한다.
알고리즘 (덱 활용):
1. 덱을 초기화하고, 시작 위치를 add_rear로 덱에 넣는다.
2. 덱이 비어있지 않은 동안 반복:
  a. delete_rear로 현재 위치를 꺼낸다. (스택의 pop)
  b. 현재 위치가 출구이면 탐색 성공.
  c. 현재 위치를 방문했다고 표시한다.
  d. 현재 위치에서 갈 수 있는 이웃 위치들(방문하지 않은 길)을 탐색 순서(ex: 상하좌우)에 따라 add_rear로 덱에 넣는다. (스택의 push)
3. 덱이 비었는데 출구를 못 찾으면 탐색 실패.

너비 우선 탐색 (BFS, Breadth First Search)

방식: 가장 먼저 저장된 경로(갈림길)를 우선적으로 선택하여 탐색을 진행하는 방법이다. (넓게 퍼져나가는 방식)
자료구조: 큐(Queue)를 사용하여 구현한다. (FIFO: First-In, First-Out)
덱 활용: 덱의 후단(rear)에서 삽입(add_rear)하고 전단(front)에서 삭제(delete_front)하면 큐처럼 동작한다.
알고리즘 (덱 활용):
1. 덱을 초기화하고, 시작 위치를 add_rear로 덱에 넣는다. (큐의 enqueue)
2. 덱이 비어있지 않은 동안 반복:
  a. delete_front로 현재 위치를 꺼낸다. (큐의 dequeue)
  b. 현재 위치가 출구이면 탐색 성공.
  c. 현재 위치를 방문했다고 표시한다.
  d. 현재 위치에서 갈 수 있는 이웃 위치들(방문하지 않은 길)을 탐색 순서에 따라 add_rear로 덱에 넣는다. (큐의 enqueue)
3. 덱이 비었는데 출구를 못 찾으면 탐색 실패.

DFS와 BFS 경로 비교

DFS는 한 경로를 깊게 파고들기 때문에 운이 좋으면 출구를 빨리 찾을 수 있지만, 경로가 매우 길거나 무한 루프에 빠질 위험이 있다(방문 표시 안 할 경우).
BFS는 시작점으로부터 가까운 곳부터 넓게 탐색하므로, 최단 경로를 찾는 데 유리하다.
탐색 속도는 미로의 구조나 이웃 탐색 순서에 따라 달라질 수 있다. 특정 방법이 항상 더 효율적이라고 단정할 수는 없다.
덱(Deque) 자료구조 하나로 delete_rear를 사용하면 DFS, delete_front를 사용하면 BFS를 구현할 수 있다.

레퍼런스

“이 글은 『쉽게 배우는 C 자료구조』(최영규 및 천인국, 2024)의 내용을 토대로 재구성된 자료입니다.”

Programiz: Learn to Code for Free

Learn to code in Python, C/C++, Java, and other popular programming languages with our easy to follow tutorials, examples, online compiler and references.

💻 이 글은 자료구조 시리즈의 일부입니다.

← 이전글: 스택 | 다음글: 포인터와 연결된 구조 →