题意分析

  • 需要我们使用两个栈来模拟队列的操作，比如入队和出队的操作。
  • 前置知识，首先，我们来介绍一下栈和队列。
    • 栈是一个先进后出的数据结构。
    • 队列是一个先进先出的数据结构。

图片说明

思路分析

写法一 C++版

  • 现在，题目要我们用两个栈来模拟一个队列的入队和出队的操作。那么我们可以先看一下一个队列想要入队，那么就可以需要将这个数字保存到队伍的尾部。我们可以这样来看，当我们出队的时候，我们需要将目前队伍中最早入队的弹出去。我们规定两个栈，一个stack1,另一个是stack2,当我们入队的时候，我们先将数字正常放入我们的stack1里面，然后当我们出队的时候，那么此时我们的stack1的最下面的那个数字就需要弹出去，那么我们怎么弹出去呢？我们就需要将这个数字上面的所有的数字从栈里面弹出保存起来。我们可以将这些数字弹出保存到另外一个栈里面。这样这个栈的出栈的顺序就是我们的队列出队的顺序。
    所以，我们遇到出队的情况，我们就判断stack2里面是否为空，如果不为空那么直接抛出栈顶的就可以了，否则，我们将stack1里面的数字先放入stack2里面，然后再抛出栈顶的。这里的stack1我理解的是一个缓冲区的功能，只有遇到stack2为空的时候才需要弹出元素。
  • 代码如下
    • 入栈的时间复杂度为O(1),因为只要进行一个push操作就行了，但是出栈的时间复杂度为时间复杂度为O(n)，因为当我们的stack2为空的时候，需要将stack1的所有的结点都进行一个出栈。
    • 需要开stack存储暂时入栈的所有的数字,空间复杂度为O(n) 
class Solution
{
public:
    // stack1用来存储我们的入栈的数字
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        // 先判断stack2里面是否有可以出栈的数字了，没有的话那么就直接从stack1里面弹出
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ans=stack2.top();
        stack2.pop();
        return ans;
    }

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

写法二 Go语言版

  • 思路和上面的一样

  • 代码如下

    • 入栈的时间复杂度为O(1),因为只要进行一个push操作就行了，但是出栈的时间复杂度为时间复杂度为O(n)，因为当我们的stack2为空的时候，需要将stack1的所有的结点都进行一个出栈。
    • 需要开stack存储暂时入栈的所有的数字,空间复杂度为O(n) 
package main

var stack1 [] int
var stack2 [] int

func Push(node int) {
    // 将数字放入stack1里面
    stack1=append(stack1,node);
}

func Pop() int{
    // 判断stack2里面还有数字
    if len(stack2)==0 {
        // 将stack1里面的数字都放到stack2里面
        for len(stack1) != 0 {
            stack2 = append(stack2,stack1[len(stack1)-1])
            stack1 = stack1[:len(stack1)-1]
        }
    }
    // 将stack2里面的最后一个元素拿出
    ans := stack2[len(stack2)-1]
    stack2 = stack2[:len(stack2)-1]
    return ans;
}