题解 | #用两个栈实现队列#

解题方法：

• 如下图所示，我们使用将push操作放到stack1中，将pop操作放到stack2中，当pop操作且stack2为空时，将stack1中所有元素转入stack2中即可。图解如下：

代码如下：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {        
        if(stack2.empty()){
            //pop时 stack2为空，将stack1中所有元素转入到stack2中
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }        
        int ans=stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

复杂度分析：

时间复杂度：对于每个元素的push和pop操作时间复杂度都为O(1)，push显然，pop时由于每个元素都只进入stack2一次，并且只删除一次，所以均摊时间复杂度为O(1)。
空间复杂度：O(n),两个栈，每个栈的空间至多为n。