[DS] 큐 - Queue (개념 및 배열로 큐 구현하기)

이미지 출처 : Pixabay

큐는 선입선출(FIFO, First-In, First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조입니다.

실생활의 모든 대기 줄 혹은 매장에서 음료를 판매하는 방식을 생각하면 됩니다.

다음 그림은 큐가 어떻게 동작하는지를 나타낸 것입니다.

큐의 동작

C++에서 배열을 사용하여 간단히 큐를 구현하겠습니다.

큐는 먼저 들어간 원소가 가장 먼저 삭제되기 때문에 스택과 같은 방법으로 배열을 사용한다면 원소가 하나 삭제될 때 마다 위 그림처럼 다른 원소들을 모두 이동시켜야 하므로 굉장히 비효율적인 방식으로 동작하게 됩니다.

이를 해결하기 위한 방법은 여러 가지가 있지만, 이 글에서는 배열을 환형 방식(Circular way)으로 사용하여 문제를 해결하겠습니다.

환형 배열(Circular array)을 활용한 큐

환형 배열을 사용하는 경우, 두 개의 인덱스 front와 rear이 필요합니다. (front는 자료의 삭제가 일어나는 곳의 인덱스이며, rear은 자료가 삽입되는 곳의 인덱스입니다.)

배열의 크기를 N이라고 할 때, 큐가 비어있는 상태(front == rear)와 포화상태(front == (rear + 1) % N)를 구분하기 위하여 원소를 최대 N-1개 삽입할 수 있도록 작성하는 방법을 사용합니다. 즉, rear 인덱스와 front 인덱스 사이에 빈 공간을 하나 만들어 두도록 합니다.

 

Queue 클래스를 작성하기에 앞서 지난번 글에서 작성한 커스텀 예외 처리 클래스를 상속받아 큐가 빈 상태와 포화상태인 경우를 처리하기 위한 QueueFullException 클래스와 QueueEmptyException클래스를 작성합니다.

[DS] 스택 - Stack (개념 및 배열로 스택 구현하기)

#include "runtime_exception.h"

class QueueFullException : public RuntimeException {
public:
	QueueFullException(const string& error_message) : RuntimeException(error_message) {}
};

class QueueEmptyException : public RuntimeException {
public:
	QueueEmptyException(const string& error_message) : RuntimeException(error_message) {}
};

그리고 Queue 클래스를 정의한 다음 두 핵심 함수를 작성합니다 : 

Enqueue(object) : 객체 object를 큐의 rear 위치에 삽입합니다. 큐가 포화상태인 경우 오류를 반환합니다.
Dequeue() : 큐의 front 위치에 있는 객체를 큐에서 제거하고 해당 객체를 반환합니다. 만약 큐가 비어있다면 오류를 반환합니다.

작성된 Queue 클래스는 다음과 같습니다.

template<typename Object>
class Queue {
private:
    Object * circular_array_;
    const int kQueueCapacity = 8;
    int front_;
    int rear_;

public:
    Queue() {
        front_ = 0;
        rear_ = 0;
        circular_array_ = new Object[kQueueCapacity];
    }
    int size() const {
        return (kQueueCapacity - front_ + rear_) % kQueueCapacity;
    }
    bool IsEmpty() {
        return (front_ == rear_);
    }
    bool IsFull() {
        return (((rear_ + 1) % kQueueCapacity) == front_);
    }
    void Enqueue(Object &object) throw(QueueFullException){
        if(IsFull()) {
            throw QueueFullException("Queue is Full!\n");
        }
        circular_array_[rear_] = object;
        rear_ = (rear_ + 1) % kQueueCapacity;
    }
    Object Dequeue() throw(QueueEmptyException){
        if(IsEmpty()) {
            throw QueueEmptyException("Queue is Empty!\n");
        }
        Object temp = circular_array_[front_];
        front_ = (front_ + 1) % kQueueCapacity;
        return temp;
    }
    Object& Front() throw(QueueEmptyException){
        if(IsEmpty()) {
            throw QueueEmptyException("Queue is Empty!\n");
        }
        return circular_array_[front_];
    }
};

스택을 구현할 때와 마찬가지로, 스택의 Top() 함수와 같은 동작을 수행하는 Front()함수는 레퍼런스 반환 함수로 작성합니다. 만일 데이터 무결성을 위하여 해당 원소의 변경을 허용하지 않을 경우 Front() 함수를 상수 멤버 함수로 변경하고 상수 참조를 반환(const Object& Front() const)하도록 작성합니다. 스택의 Pop() 함수와 같은 동작을 수행하는 Dequeue() 함수는 스택과 마찬가지로 참조자가 아닌 객체의 복사본을 반환하도록 작성합니다.