BM42. [用两个栈实现队列]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM42. 用两个栈实现队列

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=295&sfm=github&channel=nowcoder

题目主要信息:

• 队列：元素不可直接下标访问，先进先出
• 栈：元素不可直接访问，先进后出
• 使用两个栈模拟在队列中插入n个元素和弹出n个元素，顺序不定，但是保证操作都是合法的

具体思路:

元素进栈以后，只能优先弹出末尾元素，但是队列每次弹出的却是最先进去的元素，如果能够将栈中元素全部取出来，才能访问到最前面的元素，此时，另一个栈就起作用了。

• step 1：push操作就正常push到第一个栈末尾。
• step 2：pop操作时，优先将第一个栈的元素弹出，并依次进入第二个栈中。
• step 3：第一个栈中最后取出的元素也就是最后进入第二个栈的元素就是队列首部元素，要弹出，此时在第二个栈中可以直接弹出。
• step 4：再将第二个中保存的内容，依次弹出，依次进入第一个栈中，这样第一个栈中虽然取出了最里面的元素，但是顺序并没有变。

具体过程可以参考如下图：

代码实现:

class Solution
{
public:
    void push(int node) { //入队列就正常入栈
        stack1.push(node);
    }

    int pop() {
        while(!stack1.empty()){ //将第一个栈中内容弹出放入第二个栈中
            stack2.push(stack1.top()); 
            stack1.pop();
        }
        int res = stack2.top(); //第二个栈栈顶就是最先进来的元素，即队首
        stack2.pop(); 
        while(!stack2.empty()){ //再将第二个栈的元素放回第一个栈
            stack1.push(stack2.top());
            stack2.pop();
        }
        return res;
    }

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

复杂度分析：

• 时间复杂度：push的时间复杂度为，pop的时间复杂度为，push是直接加到栈尾，相当于遍历了两次栈
• 空间复杂度：，借助了辅助栈空间