189 8069 5689

队列实现栈的方法有哪些

本篇内容介绍了“队列实现栈的方法有哪些”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

我们提供的服务有:网站设计制作、成都网站建设、微信公众号开发、网站优化、网站认证、桥西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 中提交,执行结果如下:

队列实现栈的方法有哪些

“队列实现栈的方法有哪些”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!


网页题目:队列实现栈的方法有哪些
当前URL:http://cdxtjz.cn/article/gjdpdj.html

其他资讯