建站
咨询
售后
建站咨询
本篇内容介绍了“队列实现栈的方法有哪些”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
我们提供的服务有：网站设计制作、成都网站建设、微信公众号开发、网站优化、网站认证、桥西ssl等。为1000多家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的桥西网站制作公司
先来回顾一下栈(Stack)和队列(Queue)的特性和常见方法。
栈是后进先出(LIFO)的数据结构，常见方法如下：
push()：入栈方法，向栈顶添加元素;
pop()：出栈方法，将栈顶的元素移除并返回元素;
peek()：查询栈顶元素，并不会移除元素。
队列是先进先出(FIFO)的数据结构，常见方法如下：
offer()：入队方法，向队尾添加元素;
poll()：出队方法，从队头移除并返回元素;
peek()：查询队头元素，并不会移除元素。
知道了这些基础内容之后，就来看今天的问题吧。
题目描述使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的;
你所使用的语言也许不支持队列。你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可;
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。
LeetCode 225：https://leetcode-cn.com/problems/implement-stack-using-queues/
题目解析
这道题的题目很好理解：只需要将先进先出的队列，转换为后进先出的“栈”就可以了，我们可以从多个方向入手来实现此功能，比如使用两个队列插入并交换的方式，或者是一个队列插入再交换的方式，或双端队列的方式来实现此功能，具体实现方法和代码如下。
实现方法 1：两个队列实现栈
之前我们用两个栈实现了一个队列的文章中，主要使用的是「负负得正」的思想，那么当看到此道题时，首先应该想到的是用两个队列来实现一个栈，但这里的实现思路和用栈实现队列的思路又略有不同，因为队列都是先进先出的，我们可以把它理解为「正数」，那么也就不能用「负负得正」的思想了，我们这里使用两个队列来实现栈，主要的操作思路是先将元素插入一个临时队列中，然后再将另一个队列的所有元素插入到临时队列的尾部，从而实现后进先出功能的，具体的实现步骤如下。
步骤一
添加首个元素，入列到临时队列 queue2：
步骤二
因为正式队列中无元素，因此无需将 queue1 中的元素移动到临时队列 queue2 的尾部，直接将临时队列和正式队列互换即可：
步骤三
添加第二个元素，先入列到临时队列 queue2：
步骤四
再将 queue1 中的元素移动到 queue2 的尾部，如下所示：
步骤五
再将 queue1 和 queue2 进行互换：
步骤六
执行出队操作：
最终效果
从最终的效果图我们可以看出，通过两个队列已经实现了后进先出的特性，也就是完成了从队列到栈的转换，实现代码如下：
import java.util.Queue; class MyStack { Queue queue1; Queue queue2; public MyStack() { queue1 = new LinkedBlockingQueue(); queue2 = new LinkedBlockingQueue(); } /** * 入栈 */ public void push(int x) { // 1.入列临时队列二 queue2.offer(x); // 2.将队列一的所有元素移动到队列二 while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } // 3.队列一和队列二互换 Queue temp = queue1; queue1 = queue2; queue2 = temp; } /** * 出栈并返回此元素 */ public int pop() { return queue1.poll(); } /** * 查询栈顶元素 */ public int top() { return queue1.peek(); } /** * 判断是否为空 */ public boolean empty() { return queue1.isEmpty(); } } 我们在 LeetCode 中提交以上测试代码，执行结果如下：
此方法很稳，竟然击败了 100% 的用户。
实现方法 2：一个队列实现栈
那我们可以不可以用一个队列来实现栈呢?答案是肯定的。
我们只需要执行以下两个步骤就可以实现将队列转换为栈了，具体实现步骤如下：
将元素入列到队尾;
再将除队尾之外的所有元素移除并重写入列。
这样操作之后，最后进入的队尾元素反而变成了队头元素，也就实现了后进先出的功能了，如下图所示。
步骤一
元素 1 入列：
步骤二
元素 2 入列：
步骤三
将最后一个元素之前的所有元素，也就是元素 1，出列重新入列：
步骤四
执行出队操作：
最终效果
以上思路的实现代码如下：
import java.util.Queue; class MyStack { Queue queue1; public MyStack() { queue1 = new LinkedBlockingQueue(); } /** * 入栈 */ public void push(int x) { // 获取原队列长度（要移动的次数） int count = queue1.size(); // 将元素放入队尾 queue1.offer(x); // 将除最后一个元素外，其他的元素重新入队 for (int i = 0; i < count; i++) { System.out.println("for"); queue1.offer(queue1.poll()); } } /** * 出栈并返回此元素 */ public int pop() { return queue1.poll(); } /** * 查询栈顶元素 */ public int top() { return queue1.peek(); } /** * 判断是否为空 */ public boolean empty() { return queue1.isEmpty(); } } 我们把以上代码在 LeetCode 我们把以上代码在 LeetCode 中提交，执行结果如下：
此方法依旧很稳，也是同样的击败了 100% 的用户，只不过此方法在内存方面有更好的表现。
实现方法 3：双端队列实现栈
如果觉得以上方法比较难的话，最后我们还有一个更简单的实现方法，我们可以使用 Java 中的双端队列 ArrayDeque 来实现将元素可以插入队头或队尾，同样移除也是，那么这样我们就可以从队尾入再从队尾出，从而就实现了栈的功能了。
双端队列结构如下：
我们来演示一下用双端队列实现栈的具体步骤。
步骤一
元素 1 入队：
步骤二
元素 2 入队(队尾)：
步骤三
再从队尾出队：
最终效果
以上思路的实现代码如下：
import java.util.ArrayDeque; class MyStack { ArrayDeque deque; public MyStack() { deque = new ArrayDeque<>(); } /** * 入栈 */ public void push(int x) { deque.offer(x); } /** * 出栈并返回此元素 */ public int pop() { return deque.pollLast(); } /** * 查询栈顶元素 */ public int top() { return empty() ? -1 : deque.peekLast(); } /** * 判断是否为空 */ public boolean empty() { return deque.isEmpty(); } } 我们把以上代码在 LeetCode 中提交，执行结果如下：
“队列实现栈的方法有哪些”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
文章题目：队列实现栈的方法有哪些
标题路径：http://scgulin.cn/article/gjdpdj.html
