Stack 두 개로 Queue 처럼 활용하기

Stack

스택은 선입후출(FILO: First in, Last out)이다. 

4 3 2 1 순서대로 push 된다면, pop 연산시 맨 마지막으로 들어온 1이 제거된다.

 

Queue

큐는 선입선출(FIFO: First in, First out)이다.

4 3 2 1 순서대로 push 된다면, pop 연산시 맨 처음으로 입력된 4가 제거된다.

 

Stack 두 개로 Queue 처럼 활용하기

두 개의 스택을 inbox, outbox로 나누어 사용한다.

• inbox : push 연산시 원소를 추가
• outbox : pop 연산시 원소를 제거

c++ 코드

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
struct Queue {
    stack<int> inbox;
    stack<int> outbox;
 
    void push(int x) {
        inbox.push(x);
    }
 
    int pop() {
        int ret = -1;
        if (outbox.empty()) { // outbox 가 비어있다면
            while (!inbox.empty()) { // inbox에서 가져옴
                int top = inbox.top();
                inbox.pop();
                outbox.push(top);
            }
        }
        if (!outbox.empty()) { // outbox에 원소가 하나라도 있으면 pop();
            ret = outbox.top(); 
            outbox.pop();
        }
        return ret;
    }
};
 
int main() {
    Queue q;
    printf("%d\n", q.pop()); // -1
    q.push(4);
    q.push(3);
    q.push(2);
    q.push(1);
    printf("%d\n", q.pop()); // 4
    q.push(5);
    q.push(6);
    q.push(7);
    printf("%d\n", q.pop()); // 3
    printf("%d\n", q.pop()); // 2
    printf("%d\n", q.pop()); // 1
    printf("%d\n", q.pop()); // 5
    printf("%d\n", q.pop()); // 6
    printf("%d\n", q.pop()); // 7
 
    return 0;
}

구현

• 내부에 스택 inbox, outbox를 인자로 갖는 구조체 Queue를 만든다.
• push연산을 할 때는 원소를 inbox에 넣는다.
• pop연산을 할 때 outbox가 empty 라면 inbox의 원소를 제거하여 outbox에 쌓는다.
  • inbox의 원소를 pop할 때 stack이기 때문에 선입후출로 top에 있는 원소가 제거되어 outbox에 차례로 쌓이게 된다.
  • 따라서 16번 while문이 끝났을 당시에는 pop()연산으로 제거할 원소가 outbox의 top에 존재하게 된다.
  • c++ 의 stack은 pop()일 때 반환값이 없기 때문에 pop 전에 stack.top()을 사용해 원소를 변수에 저장해야 한다.
  • inbox, outbox 모두 empty일 때 -1을 반환한다.
• pop연산시 outbox가 empty가 아니라면
  • outbox의 원소를 바로 pop()하며 반환하면 된다.

결과

입력: 4 3 2 1 pop() 5 6 7 pop() ...

stack이었다면 pop 되는 순서대로 출력해보면, 1 7 6 5 2 3 4 이겠지만

Queue 구조체에서 스택 두 개로 큐 처럼 구현했기 때문에 결과는 입력받은 그 순서대로 4 3 2 1 5 6 7 이 된다.