2개의 스택(Stack)으로 큐(Queue) 구현하기

스택(Stack)과 큐(Queue)는 대표적인 자료구조 중 하나입니다.

스택은 후입선출(Last In First Out) 방식이며 큐는 선입선출(First In First Out) 방식입니다.

일반적으로 스택은 접시 쌓기로 비유하고 큐는 은행 등의 대기열에 비유됩니다.

스택과 큐는 다음과 같은 방향으로 데이터를 입력하고 출력합니다.

스택은 1 -> 2 -> 3 -> 4 순서로 넣고 4 -> 3 -> 2 -> 1의 순서로 꺼낼 수 있습니다.

큐는 1 -> 2 -> 3 -> 4 순서로 넣고 1 -> 2 -> 3 -> 4의 동일한 순서로 꺼낼 수 있습니다.

꺼낼 때의 순서가 완전히 반대인 것을 확인할 수 있습니다.

2개의 스택으로 큐를 구현하는 것은 면접 등에서 자주 볼 수 있는 알고리즘 문제 중 하나입니다.

스택에 입력했을 때 출력이 정반대인 성질을 활용하면 되는 문제입니다.

다음과 같이 큐와 동일하게 동작하는 것을 확인할 수 있습니다.

1. 스택에 입력한 데이터를 다른 스택으로 옮기면서 순서가 반대로 변경

2. 그 상태에서 꺼내면 입력한 순서로 출력

구현시의 주의할 점은 두 번째 스택이 비었을 때만 데이터를 이동해야 한다는 부분입니다.

스택을 사용하기 때문에 데이터가 있는 상태에 추가하면 순서가 꼬이게 됩니다.

그렇기 때문에 두 번째 스택이 완전히 비었을 때만 데이터를 첫 번째 스택에서 가져오는 정책을 사용해야 합니다.

다음과 같이 해당 내용을 구현할 수 있습니다.

template <typename T>
class MyQueue
{
private:
        std::stack<T> inputStack;
        std::stack<T> outputStack;

        void ShiftInToOut()
        {
                if (outputStack.empty())
                {
                        while (!inputStack.empty())
                        {
                                outputStack.push(inputStack.top());
                                inputStack.pop();
                        }
                }
        }

public:
        MyQueue() {}
        ~MyQueue() {}
        void Push(T newOne)
        {
                inputStack.push(newOne);
        }
        T Pop()
        {
                ShiftInToOut();
                T item = outputStack.top();
                outputStack.pop();
                return item;
        }
        int Size()
        {
                return inputStack.size() + outputStack.size();
        }
        bool Empty()
        {
                return Size() == 0;
        }
};

int main(int argc, char* argv[])
{
        MyQueue<int> queue;
        queue.Push(1);
        queue.Push(2);
        std::cout << queue.Pop() << std::endl;
        queue.Push(3);
        queue.Push(4);
        std::cout << queue.Pop() << std::endl;
        std::cout << queue.Pop() << std::endl;
        std::cout << queue.Pop() << std::endl;

        return 0;
}

먼저 입력을 받고 있을 스택과 출력에 사용할 스택을 선언합니다.

그리고 출력 스택이 빈 상태일 때 입력 스택에 있는 데이터를 가져오기 위한 ShiftInToOut()을 추가합니다.

나머지 구현에 특이사항은 없지만 Pop()의 경우 ShiftInToOut()을 호출해서 항상 순서를 보장합니다.

스택의 입력과 출력의 순서가 반대인 특징을 활용한 큐 구현입니다.