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

题意思路：

输入:
["PSH1","PSH2","POP","POP"]
返回:
1,2
解析:
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

方法一:栈实现队列

push操作就直接往stack1中添加， pop操作需要分为两步：

如果stack2为空，那么需要将stack1中的数据转移到stack2中，

利用栈的先进后出的性质，通过两个栈的转移实现先进后出

然后在对stack2进行pop。

图解：

复杂度分析

时间复杂度：O(N)，N数组的长度，遍历数组；

空间复杂度：O(N)，栈的存储与读取数据。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);//push操作将元素压入栈1中
    }

    int pop() {
        if(!stack2.size()){//如果栈2为空 此时不能进行pop操作
           while(stack1.size()){//将栈1中所有元素压入栈2中
               stack2.push(stack1.top());
               stack1.pop();
           }
        }
        int res=stack2.top();
        stack2.pop();
        return res;//最后返回栈2第一个元素
    }

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

方法二：栈实现队列
利用栈的先进后出的性质，通过两个栈的转移实现先进后出

方法一是如果stack2为空，那么需要将stack1中的数据转移到stack2中，然后pop操作

方法二在push和pop操作时stack1与stack2同时交替进行。

stack1专门push操作

stack2专门pop操作

每次同时更新stack1与stack2中数据

复杂度分析

时间复杂度：O(N)，N数组的长度，遍历数组；

空间复杂度：O(N)，栈的存储与读取数据。

class Solution
{
public:
    void push(int node) {
        while(stack2.size()){//push操作 若stack2中有值加入stack1中存放.同时将stack2中值pop
            stack1.push(stack2.top());//
            stack2.pop();
        }
        stack1.push(node);//再将node push进stack1中
    }

    int pop() {
        while(stack1.size()){//pop操作 若stack1中有值加入stack2中存放，同时将stack1中值pop
            stack2.push(stack1.top());
            stack1.pop();
        }
        int res=stack2.top();//再将stack2第一个数 pop输出
        stack2.pop();
        return res;
    }

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