【每日一题】用队列实现栈

九思.

2022 年 05 月 24 日

710 次浏览

暂无评论

1027字数

每日一题

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

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

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

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

发表评论时请填写正确邮箱，以便于接收通知【推荐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
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

解题思路

题解部分参考自代码随想录和LeetCode题解。如有侵权，请联系进行删除~~

本题和用栈模拟队列一样，都是重点在模拟过程，不在算法
本题主要考察对栈和队列的掌握情况
- 栈是一种只能在一端进行插入和删除的先进后出的线性表
- 队列是在一端进行插入，在另一端进行删除的先进先出的线性表
如果要用队列实现栈，主要就是改变队列中出队顺序问题，让它实现先进后出

双队模拟

有了栈实现队列的经验，我们又会想到两个队列来模拟（que1，que2）
但是和之前还是有差别的，两个队列模拟，一出一进的话，顺序还是没有改变的，所以另一个队列并不用来转换顺序，用来备份元素
当元素进栈时，同时将元素入队que1，这里不变，主要是保存元素
在元素出栈时，就该体现栈和队列的差别了，为了使先进的元素最后出，需要以下几个步骤：
- 获取当前que1中的元素个数size
- 因为栈是后进先出，也就是第一个出的应该是队列que1中本来最后一个出的元素
- 因此，将que1队列中的size-1个元素全部出队，并暂时备份到que2中
- 此时que1中仅剩一个元素，也就是按栈的顺序该弹出的元素，将其出队
- 让que1等于que2，并且将que2清空，方便下次使用
理解了pop之后，top和empty相对比较容易理解，可以直接看代码

单队模拟

单队列模拟，因为只有一个队，无法备份元素，因此每次入栈时就要将其按照栈的顺序特点进行排序，分为以下步骤：
- 获取原队中的元素个数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();
    }
}