232. Implement Queue using Stacks

两个栈，s相当于queue的后半部分，q相当于queue的前半部分，amortized O(1)

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        adjust();
        int res = q.top();
        q.pop();
        return res;
    }

    /** Get the front element. */
    int peek() {
        adjust();
        return q.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s.empty() && q.empty();
    }

    void adjust() {
        if (q.empty()) { // 这行很重要，不需要每次都调整
            while (!s.empty()) {
                q.push(s.top());
                s.pop();
            }
        }
    }

    stack<int> s;
    stack<int> q;
};

/**
 * 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();
 */