[자료구조 및 알고리즘] Queue (C++)

신동욱·2025년 1월 30일

자료구조 및 알고리즘

목록 보기

5/18

1. What is a Queue?

대기줄

여러분, 성심당을 가보셨나요? 성심당은 전국 각지의 사람들이 와서 줄을 서서 기다리는 대전에 있는 빵집입니다. 줄을 서는 이유는 매장의 수용 인원에 비해 더 많은 수요 인원들이 있기 때문입니다.

"오픈런"이라는 단어를 들어보셨을 겁니다. 가장 먼저 가게로 들어가기 위해, 가게 오픈 하기도 전에 그 앞에서 대기하는 것을 뜻합니다.

이처럼 우리 일상의 대기줄은 먼저 온 사람이 먼저 가게로 들어간다는 규칙을 갖고 있습니다. 이것이 바로 큐(queue)입니다.

큐(queue)

큐는 한 쪽 끝에서는 요소(item)의 추가(addition)만 일어나고, 다른 쪽 끝에서는 삭제(removal)만 일어나는 순서 있는 요소들의 집합(ordered collection of items)입니다.

이때 요소의 삽입만 일어나는 곳을 rear
삭제만 일어나는 곳을 front라고 부릅니다.

앞선 예시처럼, 큐는 먼저 온게 먼저 나간다는 규칙이 있습니다. 이를 FIFO, first-in first-out라고 부릅니다.

버퍼(buffer)

혹시 키보드를 쳤는데 화면에 바로 출력되지 않고 잠깐 멈칫한 경험을 하신적이 있나요? 이는 컴퓨터가 그 순간에 다른 작업을 수행하고 있기 때문입니다. 이러한 키 입력은 대기열과 같은 버퍼에 저장되어, 결국 올바른 순서로 화면에 표시됩니다.

정리

용어 내용
큐(queue) 한 쪽 끝에서는 요소의 삽입만 일어나고, 다른 쪽 끝에서는 삭제만 일어나는 자료구조
rear 요소의 삽입만 일어나는 곳
front 요소의 삭제만 일어나는 곳
FIFO first-in first-out, 선입선출

용어	내용
큐(queue)	한 쪽 끝에서는 요소의 삽입만 일어나고, 다른 쪽 끝에서는 삭제만 일어나는 자료구조
rear	요소의 삽입만 일어나는 곳
front	요소의 삭제만 일어나는 곳
FIFO	first-in first-out, 선입선출

2. Queue ADT(Abstract Data Type)

리스트나 스택처럼, 큐를 구현하는데는 크게 두 가지가 있습니다.

Array-based Queue : 배열로 구현하는 방법
Linked Queue : 리스트로 구현하는 방법

입니다. 무엇으로 구현하든, 큐가 제공하는 기능은 동일해야 합니다.

큐는 rear에서 요소(element)의 삽입이 일어나고, front에서 삭제가 일어납니다. 삽입과 삭제의 빠른 동작을 위해 이 둘의 위치를 기억하고 있어야 합니다.

큐에 요소(item)를 삽입(enqueue)하고 삭제(dequeue)하는 기능은 필수적이며, 이 외의 부가적인 기능을 제공하여 사용의 편의성을 증가시킬 수 있습니다.

Queue의 ADT는 다음과 같이 정리할 수 있습니다.

데이터(Data):

front : 삭제 위치
rear : 삽입 위치
size : 큐에 들어있는 요소 개수

기능(Operations):

clear() : 큐 초기화
enqueue() : rear에 삽입
dequeue() : front로부터 요소를 리턴하고 제거
frontValue() : front 요소를 리턴
length() : 큐 사이즈 리턴
isEmpty() : 큐가 비었는지 리턴

3. Array-based Queue

3-1. 배열에서의 enqueue, dequeue

Array-based Queue에서는 요소들이 미리 할당된 배열(pre-allocated array)에 저장됩니다. 배열에서 삽입(enqueue)과 삭제(dequeue)는 어떻게 이루어질까요?

dequeue를 수행하면 front에 있던 값을 리턴하고, 삭제 후 front의 위치를 최신화해야 합니다. front의 다음 위치는 그림에서 20 다음으로 들어온 5가 되어야 합니다.

enqueue를 수행하면 rear가 가리키는 17 다음으로 붙어야 합니다. 이를 위해 rear를 하나 움직여서 빈공간을 가리키고 여기에 값을 입력합니다.

rear가 배열의 끝에 도달한 경우를 생각해봅시다. 더 이상 enqueue를 할 수 없는 건가요? 아직 배열에는 사용할 수 있는 노란색 공간이 있습니다. 그런데 이 공간을 어떻게 사용할 수 있을까요?

3-2. Array of ring shape

만약 배열이 원형(ring shape)으로 생겼으면, rear의 다음으로 노란색 공간으로 넘어갈 수 있습니다.

원형은 나머지 연산(modulus operation)으로 구현할 수 있습니다. 위 그림은 길이가 12인 배열입니다. dequeue()를 하면 front가 가리키는 인덱스보다 한 칸 다음으로 넘어가야 합니다. 이 인덱스를 front = (front + 1) % 12로 업데이트하면, 10 > 11 > 0 > 1 ... > 11 > 0... 이렇게 계속 반복할 수 있는 것이죠.

원형 큐에서는 다음과 같이 rear와 front를 업데이트해야 합니다.

enqueue() : rear = (rear + 1) % 최대 길이
dequeue() : front = (front + 1) % 최대 길이

*참고 : full or empty( size + 1 방법 )
그런데, 이러한 원형 큐에서는 어떻게 비었거나 가득 찬 것을 알 수 있을까요? 물론 요소의 개수를 관리하는 size 변수를 하나 두면 됩니다. 하지만 rear와 front의 상대적인 위치 관계를 통해서도 가능합니다.

front와 rear가 같은 인덱스를 가리키고 있다고 해봅시다. 이 상태는 원형 큐에 값이 있는 상태일까요? 값이 있는 상태여야 합니다. 이 상태가 비어있는 상태라고 해봅시다. rear는 한 칸 움직여서 값을 입력합니다. 그리고 front는 현재 위치에 있는 값을 리턴하고 한 칸 움직이는데, 값이 없기 때문에 리턴할 수 없습니다.

따라서 원형 큐가 비어있다면, 위 그림처럼 front - rear = 1이어야 합니다. enqueue()를 하면, rear에서 한 칸 이동하여 front가 위치한 곳에 삽입합니다. 그리고 dequeue()를 하면 front 위치에 있는 값을 리턴하고 front는 한 칸 이동하게 됩니다.

가득 찬 건 어떻게 알까요? 사실 위 그림만으로는 비어있는 것과 가득 차 있는 것을 구분할 수 없습니다. 위 그림에서 모든 칸에 값이 쓰여 있어도, dequeue()의 동작에 아무 문제가 없기 때문입니다. 그래서, 원래 입력받은 큐의 사이즈보다 +1 증가한 크기만큼의 배열을 할당합니다.

이렇게 하면 비어있을 때는 항상front가 rear보다 +1칸 앞선 모습이고, 큐가 가득 차 있어도 한 칸은 항상 비어있도록 할 수 있기 때문에front는 rear보다 +2칸 앞선 모습이 됩니다.

정리 : Array-based Queue(Ring Shape)

enqueue() : rear = (rear+1) % maxSize

dequeue() : front = (front+1) % maxSize

empty : front == (rear+1) % maxSize

full : front == (rear+2) % maxSize

maxSize = 입력받은 큐의 크기 + 1

3-3. Array-based queue 구현

#include <iostream>
#include "Queue.h"
using namespace std;

template <typename T>
class AQueue : public Queue<T> {
private:
    T* queueArray;                        // 배열 : queue 요소들을 갖고있는
    static const int DEFAULT_SIZE = 10; // 디폴트 배열 크기
    int maxSize;                        // 크기 파악
    int front;                            // 인덱스 : front 가리키는거
    int rear;                            // 인덱스 : rear 가리키는거

public:
    // 생성자1
    AQueue() {
        this(DEFAULT_SIZE);
    }
    // 생성자2
    AQueue(int size) {
        rear = 0; front = 1;            // empty == (front - rear = 1)
        maxSize = size + 1;                // One extra space is allocated
        queueArray = new T[maxSize];    // size 크기로 T형 배열 동적 할당
    }
    // 소멸자 : 소멸하기 전에 동적 할당한거 반납해야 함
    ~AQueue() { delete[] queueArray; }

    void clear() { rear = 0; front = 1; }

    bool enqueue(T it) {
        if ((rear + 2) % maxSize == front)
            return false; // Full

        rear = (rear + 1) % maxSize; // Circular increment
        queueArray[rear] = it;
        return true;
    }

    T dequeue() {
        if (isEmpty()) {
            cout << "큐가 비었음\n";
            return T();
        }
        T it = queueArray[front];
        front = (front + 1) % maxSize;
        return it;
    }

    T frontValue() {
        if (isEmpty()) {
            cout << "큐가 비었음\n";
            return T();
        }
        return queueArray[front];
    }

    int length() {
        return (maxSize + rear - front + 1) % maxSize;
    }
    bool isEmpty() {
        return front == (rear + 1) % maxSize;
    }
};

4. Linked Queue

4-1. Linked Queue에서의 enqueue, dequeue

링크드 큐(linked queue)는 싱글 링크드 리스트(single linked list)를 구현할 때 사용했던 Link 클래스를 활용하면 됩니다.

초기에는 위와 같이 null 값을 갖는 노드 하나를 front와 rear가 함께 가리키고 있습니다. 이제 여기서는 front와 rear는 인덱스가 아니라 포인터겠네요. 3번의 enqueue를 진행해보겠습니다.

어떻게 진행되는지 느낌이 오시나요? enqueue를 위해서는 먼저 새로운 노드를 생성해야 합니다. 그리고 노드에 값을 입력합니다. rear가 가리키던 노드의 next가 새로운 노드를 가리키기만 하면 되겠네요. 그리고 나서 rear는 rear가 가리키는 곳의 next를 가리키도록 업데이트 하면 될 것 같습니다. size를 늘려주는 것을 잊으면 안되겠죠?

dequeue는 front에서 일어납니다. front는 항상 null을 가리키고 있어야합니다. 그래서 front의 next를 삭제하는 것이지요. 그 전에 front의 next 노드의 next가 가리키던 포인터를 복사해둡니다. 그리고 front의 next를 삭제하고, front의 next를 복사해둔 next로 바꾸기만 하면 끝입니다.

정리 📄

enqueue()

Step 1. 새로운 노드를 rear 뒤에 생성한다

Step 2. rear를 새로운 노드를 가리키도록 옮긴다

Step 3. size = size + 1

dequeue()

Step 1. front의 next 노드를 삭제한다

Step 2. front의 next를 다음 노드에 연결한다

Step 3. size = size - 1

4-2. Linked Queue 구현

#include <iostream>
#include "Queue.h"
using namespace std;

template <typename T>
class AQueue : public Queue<T> {
private:
    T* queueArray;                        // 배열 : queue 요소들을 갖고있는
    static const int DEFAULT_SIZE = 10; // 디폴트 배열 크기
    int maxSize;                        // 크기 파악
    int front;                            // 인덱스 : front 가리키는거
    int rear;                            // 인덱스 : rear 가리키는거

public:
    // 생성자1
    AQueue() {
        this(DEFAULT_SIZE);
    }
    // 생성자2
    AQueue(int size) {
        rear = 0; front = 1;            // empty == (front - rear = 1)
        maxSize = size + 1;                // One extra space is allocated
        queueArray = new T[maxSize];    // size 크기로 T형 배열 동적 할당
    }
    // 소멸자 : 소멸하기 전에 동적 할당한거 반납해야 함
    ~AQueue() { delete[] queueArray; }

    void clear() { rear = 0; front = 1; }

    bool enqueue(T it) {
        if ((rear + 2) % maxSize == front)
            return false; // Full

        rear = (rear + 1) % maxSize; // Circular increment
        queueArray[rear] = it;
        return true;
    }

    T dequeue() {
        if (isEmpty()) {
            cout << "큐가 비었음\n";
            return T();
        }
        T it = queueArray[front];
        front = (front + 1) % maxSize;
        return it;
    }

    T frontValue() {
        if (isEmpty()) {
            cout << "큐가 비었음\n";
            return T();
        }
        return queueArray[front];
    }

    int length() {
        return (maxSize + rear - front + 1) % maxSize;
    }
    bool isEmpty() {
        return front == (rear + 1) % maxSize;
    }
};