자료구조 - Queue

Queue는 Stack과 동일하게 원소가 더해질 때는 뒤쪽으로 더해지지만 원소를 출력하게 될 때는 Stack과 다르게 앞쪽으로 원소를 출력한다.

 

따라서 Queue의 특징은 원소의 추가와 삭제가 서로 다른 방향에서 발생한다는 것인데 결과적으로 가장 처음에 추가된 원소가 가장 먼저 빠지기 때문에 FIFO(first in first out) 구조를 가진다.

 

 Queue에서도 Stack과 유사하게 push와 pop이 있는데 stack에서는 원소를 제거한 위치에 다시 원소를 집어넣기 때문에 처음 MAX_ITEMS만 정해주면 메모리 문제없이 범위 내에서 무한정으로 원소를 삽입하고 제거할 수 있었다.

 

하지만 Queue의 경우 이처럼 무작정 원소를 넣고 빼고 한다면 전체 queue의 길이는 MAX_ITEMS를 넘지 않더라도 pop을 하면 할수록 점점 오른쪽으로 이동하게 되어 메모리 공간을 벗어날 가능성이 생긴다. 

 

따라서 이러한 문제를 해결하기 위해서 가장 간단한 방법은 pop할 때마다 모든 queue를 한 칸씩 당겨서 항상 queue의 첫 번째 원소가 같은 주소값을 가지게 할 수 있다.

 

하지만 이러한 방식은 큐가 매우 클 경우 시간이 오래 걸리게 비용이 매우 비싸게 되어 좋지 못한 방법이다.

 

그래서 MAX_ITEMS을 정해두고 해당 범위를 벗어나게 되는 부분은 circular structure을 활용하여 다시 앞에서부터 채우는 방식을 사용하면 된다.

 

다만 이러한 경우 큐의 제일 앞을 가리키고 있는 front포인터와 제일 뒤를 가리키고 있는 rear포인터가 원소가 큐에 가득 차있을 때와 큐가 비어있을 때 나란히 위치하게 되어 포인터 만으로는 두 상태를 구분할 수 없다.

비어있는 큐와 가득찬 큐를 구분할 수 없는 경우

따라서 front포인터를 실제 큐에서 가장 앞의 주소의 이전 영역을 가리키게 하여 만약 rear포인터의 주소의 다음 영역이 front포인터의 위치이면 큐가 가득 찼다는 것을 표현해 주고 만약 rear포인터의 주소와 front포인터의 주소가 같을 경우를 큐가 비어있다고 해주면 된다.

비어있는 큐와 가득찬 큐가 구분되는 경우

 

이러한 사실을 바탕으로 큐를 짜보면 다음과 같이 짤 수 있다.

class QueType {
    int front;
    int rear;
    ItemType* items;
    int maxQue;
public:
    QueType();
    QueType(int max);
    ~QueType();
    
    void MakeEmpty();
    void Enqueue(ItemType newItem);
    void Dequeue(ItemType& item);
    
    bool IsEmpty() const;
    bool IsFull() const;
};

 

queue의 경우 사용자가 얼마나 큰 범위를 사용할지 개발하는 단계에서는 알 수 없으므로 생성자를 통해 입력을 할 수 있게 하여 메모리 효율성을 늘리는 것이 좋다.

 

여기서 MakeEmpty, Enqueue, Dequeue는 Transformer에 해당하는 부분으로 각각 큐를 비우거나, 큐에 새로운 원소를 삽입, 큐의 가장 앞의 원소를 제거하는 과정을 수행한다.

 

IsEmpty, IsFull은 Observers로 각각 큐가 비어있는지 그리고 큐가 가득 찼는지 확인한다.

 

이제 Queue를 실제로 구현해 보면 다음과 같이 짤 수 있다.

#include "QueType.h"

QueType::QueType(int max) {
    maxQue = max + 1;
    front = maxQue - 1;
    rear = maxQue - 1;
    items = new ItemType[maxQue];
}
QueType::QueType() {
    maxQue = 501;
    front = maxQue - 1;
    rear = maxQue - 1;
    items = new ItemType[maxQue];
}
QueType::~QueType() {
    delete[] items;
}

void QueType::MakeEmpty() {
    front = maxQue - 1;
    rear = maxQue - 1;
}

void QueType::Enqueue(ItemType newItem) {
    if (IsFull())
        throw FullQueue();
    else {
        rear = (rear + 1) % maxQue;
        items[rear] = newItem;
    }
}

void QueType::Dequeue(ItemType& item) {
    if (IsEmpty())
        throw EmptyQueue();
    else {
        front = (front + 1) % maxQue;
        item = items[front];
    }
}

bool QueType::IsEmpty() const {
    return (rear == front);
}

bool QueType::IsFull() const {
    return ((rear + 1) % maxQue == front);
}

 

만약 사용하는 사람이 queue의 크기를 따로 지정한다면 QueueType(int max) 생성자를 통해서 입력받은 크기로 큐를 생성할 수 있고, 별도의 입력이 없다면 개발자가 사전에 정한 크기로 큐를 구성하게 된다.

 

이 과정에서 new를 통해 동적으로 메모리를 할당해 주어서 사용이 끝나면 delete로 지워줘야 하기 때문에 소멸자를 사용하여 메모리 누수를 방지하였다.

 

Enqueue를 할 때는 마지막을 가리키고 있는 포인터를 다음 위치를 바꾸게 한 다음 해당 위치에 새로운 값을 대입한다.

 

이때 다음 위치가 사전에 지정한 범위를 넘는지 확인해 주고 만약 범위를 넘어가게 될 경우 다시 앞에서부터 넣어주면 된다.

 

Dequeue의 경우는 front가 현제 가리키고 있는 값은 큐의 첫 번째 원소의 앞부분의 위치임으로 이 위치를 큐의 첫 번째 원소의 위치로 변경 후 해당 값을 가져오면 된다. 

 

파이썬으로는 다음과 같이 구현할 수 있다.

 

class QueueType():
    def __init__(self):
        self.info = []

    def enqueue(self, data):
        self.info.append(data)

    def dequeue(self):
        if not self.is_empty():
            return self.info.pop(0)

    def is_empty(self):
        return len(self.info) == 0
       
    def is_full(self):
        return len(self.info) == MAX_ITEMS

    def make_empty(self):
        self.info.clear()