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

이번 포스트에서는 어떠한 별도의 변수를 사용하지 않고 오로지 스택(Stack) 2개로 큐(Queue)의 기능을 구현하는 방법을 정리하고자 한다. 먼저, 두 개의 Data Structure에 대한 간단한 설명부터 하겠다.

 

1. 스택(Stack), 큐(Queue)

스택(Stack)은 top이라 불리는 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 Data Structure이다. 자료를 넣는 것을 push, 꺼내는 것을 pop이라 하며 가장 마지막에 넣은 자료가 먼저 나오는 Last-In-First-Out(LIFO) 구조이다.

 

큐는(Queue)는 rear라 불리는 한 쪽 끝에서만 자료를 넣고 front라 불리는 반대쪽 한쪽 끝에서만 자료를 뺄 수 있는 Data Structure이다. 자료를 넣는 것을 자료를 넣는 것을 enqueue, 꺼내는 것을 dequeue이라 하며 가장 먼저 넣은 자료가 먼저 나오는 First-In-First-Out(FIFO) 구조이다.

 

 

2. 두개의 스택으로 큐 구현하기

스택과 큐에서 자료가 어떠한 방식으로 들어오고(push) 나가는지(pop)만 이해하면 어려운 문제가 아니다. 위에서 설명한 것과 같이 스택은 LIFO, 큐는 FIFO 구조이다. 한 가지 예시를 들어보자. 스택과 큐에 각각 자료 1, 2, 3을 순서대로 넣어 보겠다. 스택에서는 3, 2, 1 순서로 자료가 나올 것이며, 큐에서는 1, 2, 3 순서로 자료가 나올 것이다. 그렇다. 같은 자료가 같은 순서로 스택과 큐에 각각 들어갔을 때 자료가 나오는 순서는 스택과 큐는 서로 역순(reverse)이다. 큐의 기능을 구현하기 위해서는 기존의 스택(Stack#1)에서 나오는 자료를 다시 역순으로 뒤집어 주면 되며 이때 사용할 것이 두번째 스택(Stack#2)이다. 단순히 Stack#1에서 나오는(pop) 자료를 Stack#2에 넣기(push)만 하면 되는 거이다. 아래 사진을 본다면 더 이해가 쉬울 것이다.

 

 

그렇다면, Queue의 Enqueue와 Dequeue Operation을 각각 수도 코드로 작성해 보자. 위에서 설명한 내용만 잘 이해했다면 쉽게 이해할 수 있을 것이다.

 

Enqueue Operation

 

Push every input element to the Stack#1

Dequeue Operation

 

If(Stack#2 is empty)

pop every element in the Stack#1

and push them to the Stack#2 until Stack#1 is Empty

pop from Stack#2

 

수도 코드를 기반으로 C++로 코드를 작성해 보았다.

 

template <typename Item>
class MyQueue {
private:
 stack<Item> stack1;
 stack<Item> stack2;
 int size = 0;

public:
  void enqueue(Item element) {
    stack1.push(element);
    size++;
  }

  Item dequeue() {
    if (stack2.empty()) {
      while (!stack1.empty()) {
        stack2.push(stack1.top());
        stack1.pop();
      }
    }

    Item temp = NULL;
    if (!stack2.empty()) {
      temp = stack2.top();
      stack2.pop();
      size--;
    }
    return temp;
  }
};

 

이번 포스트는 Stack OverFlow(https://bit.ly/2k5C92O)의 내용을 참고로 정리하고 코드를 작성한 것이다. 피드백은 종류를 막론하고 언제나 환영.