同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-24
  • 题目序号:225
  • 难度:简单

问题描述

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

注意

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
来源:力扣(LeetCode)

示例

输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示

  • 1 <= x <= 9
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

解题思路

题解部分参考自代码随想录LeetCode题解。如有侵权,请联系进行删除~~
  • 本题和用栈模拟队列一样,都是重点在模拟过程,不在算法
  • 本题主要考察对栈和队列的掌握情况

    • 栈是一种只能在一端进行插入和删除的先进后出的线性表
    • 队列是在一端进行插入,在另一端进行删除的先进先出的线性表
  • 如果要用队列实现栈,主要就是改变队列中出队顺序问题,让它实现先进后出

225.用队列实现栈

双队模拟

  • 有了栈实现队列的经验,我们又会想到两个队列来模拟(que1que2
  • 但是和之前还是有差别的,两个队列模拟,一出一进的话,顺序还是没有改变的,所以另一个队列并不用来转换顺序,用来备份元素
  • 当元素进栈时,同时将元素入队que1,这里不变,主要是保存元素
  • 在元素出栈时,就该体现栈和队列的差别了,为了使先进的元素最后出,需要以下几个步骤:

    • 获取当前que1中的元素个数size
    • 因为栈是后进先出,也就是第一个出的应该是队列que1中本来最后一个出的元素
    • 因此,将que1队列中的size-1个元素全部出队,并暂时备份到que2中
    • 此时que1中仅剩一个元素,也就是按栈的顺序该弹出的元素,将其出队
    • 让que1等于que2,并且将que2清空,方便下次使用
  • 理解了pop之后,top和empty相对比较容易理解,可以直接看代码

单队模拟

fig2

  • 单队列模拟,因为只有一个队,无法备份元素,因此每次入栈时就要将其按照栈的顺序特点进行排序,分为以下步骤:

    • 获取原队中的元素个数size
    • 将要入栈的元素入队
    • 将前面队列中的size个元素出队,并重新入队(这里并不对刚入队的元素操作,也就是将原队中的元素重新入队)
  • 在入栈完成后,队中的元素顺序就已经符合栈的特点了
  • 弹栈只需要将队头元素出队即可

代码实现

双队模拟

class MyStack {
    private Queue<Integer> que1 = new LinkedList();
    private Queue<Integer> que2 = new LinkedList();
    public MyStack() {

    }

    public void push(int x) {
        que2.offer(x);  // 先放在辅助队列中
        while (!que1.isEmpty()){
            que2.offer(que1.poll());
        }
        Queue<Integer> queTemp;
        queTemp = que1;
        que1 = que2;
        que2 = queTemp; // 最后交换que1和que2,将元素都放到que1中
    }

    public int pop() {
        return que1.poll();
    }

    public int top() {
        return que1.peek();
    }

    public boolean empty() {
        return que1.isEmpty();
    }
}

单队模拟

class MyStack {
    private Queue<Integer> que = new LinkedList();
    public MyStack() {

    }

    public void push(int x) {
        int n = que.size();
        que.offer(x);
        for (int i = 0; i < n; i++) {
            que.offer(que.poll());
        }
    }

    public int pop() {
        return que.poll();
    }

    public int top() {
        return que.peek();
    }

    public boolean empty() {
        return que.isEmpty();
    }
}

总结

  • 栈:只能一端进出,先进后出,线性表
  • 队列:一端进,一端出,先进先出,线性表
  • 模拟题重点都不在算法,而在于代码执行流程,需要把握好这个
最后修改:2022 年 05 月 24 日
如果觉得我的文章对你有用,请随意赞赏