두개의 스택으로 하나의 큐 만들기

Intuition

using two stack for make queue

Approach

queue first in first out 
stack first in last out
then push first and pop ? 
first replace to end 
and last pop  

스택은 처음 들어온것이 마지막에,
큐는 처음 들어온것이 처음 나가도록 동작한다.
따라서, 빠질때, 처음 스택을 다 뺏을때, 마지막으로 나온 데이터가 queue의 결과와 동일한 값을
준다.

Complexity

• Time complexity:
  O(1) for push, empty
  O(N) for pop, peek,
• Space complexity:
  O(N)

  Code

C++

#include <stack>

class MyQueue {
    std::stack<int> first;
public:
    MyQueue() {}

    void push(int x) {
        first.push(x);
    }

    int switching(bool pop)
    {
        std::stack<int> second;
        while (!first.empty())
        {
            int p = first.top();
            first.pop();
            second.push(p);
        }
        int ret = second.top();
        second.pop();
        if (pop == false) {
            first.push(ret);
        }
        while (!second.empty()) {
            int p = second.top();
            second.pop();
            first.push(p);
        }
        return ret;
    }

    int pop() {
        return switching(true);    
    }

    int peek() {
        return switching(false);
    }

    bool empty() {
        return first.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */