方法一：利用两个栈，每次push都利用另一个栈倒一遍。其中push O(n)

class MyQueue {private:    stack
     
       s1; //the same order of queue    stack
      
        s2;public:    /** Initialize your data structure here. */    MyQueue() {    }        /** Push element x to the back of queue. */    void push(int x) {        while (!s1.empty()){            int tmp=s1.top(); s1.pop();            s2.push(tmp);        }        s2.push(x);        while (!s2.empty()){            int tmp=s2.top(); s2.pop();            s1.push(tmp);        }    }        /** Removes the element from in front of queue and returns that element. */    int pop() {        int tmp=s1.top(); s1.pop();        return tmp;    }        /** Get the front element. */    int peek() {        return s1.top();    }        /** Returns whether the queue is empty. */    bool empty() {        return s1.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(); */
      
     

 

方法二：同样是利用两个栈，但是不同于上一种方法每次push都要倒一次。两个栈记作in和out，out顺序与queue一致。每次push都放到in中，需要pop的时候才把in倒到out中执行。相当于in作为一个缓存，out没元素了才将in中的元素倒入out中。push-O(1); pop-Amortized O(1)。

详见 

class MyQueue {private:    stack
     
       in;    stack
      
        out;    int front;public:    /** Initialize your data structure here. */    MyQueue() {    }        /** Push element x to the back of queue. */    void push(int x) {        if (in.empty()) front=x;        in.push(x);    }        /** Removes the element from in front of queue and returns that element. */    int pop() {        if (out.empty()){ //move from in to out            while (!in.empty()){                out.push(in.top()); in.pop();            }        }        int tmp=out.top(); out.pop();        return tmp;    }        /** Get the front element. */    int peek() {        if (!out.empty()) return out.top();        else return front;    }        /** Returns whether the queue is empty. */    bool empty() {        return in.empty() && out.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(); */