题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

算法设计

1. 使用双栈实习的队列，栈和队列不同的地方在于，栈是先进后出，队列是先进先出，解决问题的关键是使用栈能做到先进先出。
2. 一个栈的结构是固定的，这时候就可以使用两个栈。一个栈存储的是正常顺序的数据。另一个是个反顺序的数据。
3. stackPush中的数据必须一次性全部压入stackPop中
4. 如果stackPop栈不为空，绝不能将stackPush栈中的元素压入stackPop栈。
   • 例：stackPop有元素1,2,3，此时stackPush压入了4,5元素，只能Pop完1,2,3，才能Push 5,4元素。

时间复杂度

参考文献

C++ 代码

class MyQueue {
private:
    stack<int> stackPush;
    stack<int> stackPop;
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    void push(int node) {
        stackPush.push(node); 
    }

    int pop() {       
      if(stackPop.empty() && !stackPush.empty())
        {
            while(!stackPush.empty())
            {
                stackPop.push(stackPush.top());
                stackPush.pop();
            }
        }
       int result=stackPop.top();
       stackPop.pop();
       return result;
    }

    /** Get the front element. */
    int peek() {
        if(stackPop.empty() && !stackPush.empty())
        {
            while(!stackPush.empty())
            {
                stackPop.push(stackPush.top());
                stackPush.pop();
            }
        }
        return stackPop.top();
    }

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

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