[자료구조] 두 개의 스택으로 하나의 큐를 구현해보자(향상된 성능으로)

스택은 LIFO, 큐는 FIFO 자료구조이다.

어떻게 하면 두 개의 스택으로 하나의 큐를 구현하는데, 대부분의 경우에서 O(1)으로 구현할 수 있을까?

 

하나를 입력용 스택, 하나를 출력용 스택이라고 해보자.

입력용 스택은 입력만 받는다.

출력용 스택은 출력만 한다.

 

단, 출력용 스택이 empty인 경우, 입력용 스택의 원소들을 pop하여 출력용 스택에 push하면 된다.

이때 출력용 스택에는 입력의 역순으로 들어오게 되어 기존의 출력 순서가 반대로 되어 FIFO가 된다.

이 경우만 제외하고는, O(1)의 시간복잡도를 가진다.

 

 

class MyQueue {
    stack<int> i,o;
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        i.push(x);
    }
    
    int pop() {
        int x;
        if(o.empty()) {
            while(!i.empty()) {
                o.push(i.top());
                i.pop();
            }
        }
        x = o.top();
        o.pop();

        return x;
    }
    
    int peek() {
        int x;
        if(o.empty()) {
            while(!i.empty()) {
                o.push(i.top());
                i.pop();
            }
        }
        x = o.top();
        return x;
    }
    
    bool empty() {
        return i.empty() && o.empty();
    }
};