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

用两个栈模拟队列
题解：模拟
原理：两次栈入栈相当于两次逆序可以恢复至原数组次序；
思路：
1.push操作将值放入栈A 。
2.pop操作前，先将栈A中除了栈底值的值push到栈B。
3.之后的pop操作直接在栈B上操作，直到栈B为空。在重复2操作。
图示：

复杂度分析:
时间复杂度：,push操作为O(1),pop操作为O(1)
空间复杂度：,需要2个stack来存一个序列,一共占用O(n)

实现如下:

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


    int pop() {
        int ans;
        if(!stack2.empty()) {ans = stack2.top(); stack2.pop();}//当栈B有值时，返回栈B的顶部
        else {//当栈B为空，先将栈A拷贝至栈B，只留一个值
            while(!(stack1.size()==1)){stack2.push(stack1.top()); stack1.pop();}
            ans = stack1.top(); stack1.pop(); //将栈A唯一的一个值返回;
    }
    return ans;
    }

private:
    stack<int> stack1;//栈A
    stack<int> stack2;//栈B

};