[자료구조] Queue

Queue는 FIFO(First-In First-out, 선입선출) 원칙에 따라 element를 insert/remove 하는 자료구조이다. stack이 패스트푸트점 컵 놓는 곳이라면, queue는 놀이동산이나 카페의 줄을 생각하면 될 것이다. 실제로 모 학교의 교내 카페 이름이 queue라고 하던데, 우리 학교가 아니라 확실한지는 모르지만 재미있는 작명이라 생각한다.

 

Queue는 다음 연산을 수행할 수 있어야 한다.

Enqueue(e) : element를 queue의 맨 끝에 삽입. 

Dequeue(): 맨 앞의 element를 반환하고 제거.

First(): 맨 앞의 element를 제거하지 않고 참조.

Size()/isEmpty() : stack의 그것과 동일.

 

사실 stack과 마찬가지로, 코딩을 어느 정도 해 본 분들이라면 이 두 자료구조는 상당히 익숙할 것이라고 생각한다. 그만큼 굉장히 자주 쓰이는 자료구조이기 때문이다. Queue의 경우, graph에서 BFS연산을 할 때 사용되기 때문에 나 역시 상당히 많이 이용해 본 자료구조이다. 

Array-Based Queue

stack에서 다뤘던 것과 같이, array를 기반으로 queue를 구현한 것이다. 고정된 자료구조인 array를 기반으로 구현했기 때문에 만약 크기를 늘려줘야 될 경우 새로운 array 를 만들고 O(n) 시간 걸리는 연산을 통해 기존 array에 있던 element들을 옮겨 써 주는 과정이 필요할 것이다.

차이가 있다면 stack은 우리의 인식상으로 맨 위 - 실제 array에서는 맨 끝 - 에 있는 element를 추적하기 위해 top이라는 변수를 사용했지만 queue 에서는 맨 앞에 있는 element를 추적하기 위해 front라는 변수를 사용하고, 맨 끝 지점을 파악하기 위해 rear 변수를 도입할 것이다.

다음은 교재 내용을 기반으로 내가 재구성한 array-based queue이다.

class CustomQueue
{
private:
    int front;
    int rear;
    int maxSize;
    int size;
    int *storage;

public:
    CustomQueue()
    {
        front = 0;
        rear = 0;
        size = 0;
        maxSize = 10000;
        storage = new int[maxSize];
    }

    ~CustomQueue()
    {
        delete[] storage;
    }

    void Enqueue(int e)
    {
        if (size == maxSize)
        {
            // resizing
        }

        rear = (rear + 1) % maxSize;
        storage[rear] = e;
        size++;
    }

    int Dequeue()
    {
        if (IsEmpty())
            return;

        int result = storage[front];
        front = front + 1 % maxSize;
        size--;
        return result;
    }

    int Front()
    {
        return storage[front];
    }

    bool IsEmpty()
    {
        if (size == 0)
            return true;
        else
            return false;
    }

    int Size()
    {
        return size;
    }
};

왜 그냥 front++, rear++ 이런 식으로 postfix 연산을 하지 않고 (front+1)%maxSize 의 연산을 하는지 알아보았는데, 이것이 storage를 재사용할 가능성을 올려 주기 때문이다.

가령 단순히 postfix 연산을 이용하면 storage가 한 번 가득 차면 얄짤없이 resizing을 해야 한다. 하지만 modulo 연산을 사용하면 storage를 재활용할 가능성이 올라간다. 

 

가령 maxSize = 5이고, 5번의 enqueue를 통해 현재 storage가 가득 찬 상황이라고 생각하자. 이 경우 front=0, rear =4일 것이다. 여기서 한 번 더 enqueue를 시도하면 이 때는 resizing이 강제되지만, 만일 그 전에 dequeue를 한 번 수행하게 된다면
front = 1, rear = 4
가 되고, 
여기서 다시 enqueue를 시도하면
front = 1, rear = 0

이 되어서, resizing을 할 필요가 없어진다. 

마지막으로  C++ STL을 사용할 때, queue의 .pop() 연산은 return&remove 연산이 아니라 그냥 remove 연산이다. 그래서 앞서 공부한 Dequeue 기능을 사용하고 싶다면 다음과 같이 해야 한다.

int e = queue.front();
queue.pop();

Unity에서 사용하는 C#의 경우에는 그냥 Dequeue를 사용해도 된다.