温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

怎么用两个栈实现一个队列

发布时间:2021-10-26 09:21:08 来源:亿速云 阅读:134 作者:iii 栏目:web开发

这篇文章主要讲解了“怎么用两个栈实现一个队列”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“怎么用两个栈实现一个队列”吧!

在正式开始之前,我们先来回顾一下栈和队列的常用方法。

栈(Stack)的常用方法包含以下这些:

  • push():入栈方法,向栈顶添加元素;

  • pop():出栈方法,将栈顶的元素移除并返回元素;

  • peek():查询栈顶元素,并不会移除元素。

怎么用两个栈实现一个队列

队列(Queue)的常用方法包含以下这些:

  • offer():入队方法,向队尾添加元素;

  • poll():出队方法,从队头移除并返回元素;

  • peek():查询队头元素,并不会移除元素。

怎么用两个栈实现一个队列

有了这些前置知识,接下来我们来看今天的题目。

题目描述

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和  deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能,若队列中没有元素,deleteHead 操作返回 -1。

示例 1:

输入: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出:[null,null,3,-1]

示例 2:

输入: ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出:[null,-1,null,null,5,2]

提示:

1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用 leetcode:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解题思路

这道题目的意思其实很好理解,就是要将先进后出的栈改为先进先出的队列,其实问题中也给出了一些提示,“用两个栈来实现一个队列”。这道题实现的核心思想就是「负负得正」,我们先用一个栈来存入元素(这时最先进入的元素在栈底),然后再将第一个栈中的元素移动到新栈中,此时最先进入的元素就在栈顶了,然后在用第二个栈出栈时,整个执行的顺序就变成了先进先出。

接下来,我们用图解的方式来实现一下整个流程。

步骤一

先将元素入栈到第一个栈中,如下图所示:

怎么用两个栈实现一个队列

步骤二

将第一个栈中的元素都移动到第二个栈中,如下图所示:


怎么用两个栈实现一个队列

步骤三

所有元素从第二个栈中出栈,如下图所示:

怎么用两个栈实现一个队列

小结

从上述图片可以看出,元素添加顺序是 1、2、3,最终经过两个栈之后的出栈顺序也是 1、2、3,这样我们就通过两个栈实现了队列(先进先出)。

怎么用两个栈实现一个队列

实现代码

接下来我们就用代码来实现一下以上思路:

class CQueue {     Stack<Integer> inputStack; // 入栈的容器(添加时操作)     Stack<Integer> outputStack; // 出栈和查询的栈容器      public CQueue() {         inputStack = new Stack();         outputStack = new Stack();     }      // 添加操作     public void appendTail(int value) {         inputStack.push(value);     }      // 删除操作     public int deleteHead() {         if (!outputStack.isEmpty()) {             // 出栈容器不为空             return outputStack.pop();         } else if (!inputStack.isEmpty()) {             // 入栈 stack 全部转移到出栈 stack             while (!inputStack.isEmpty()) {                 outputStack.push(inputStack.pop());             }         }         return outputStack.isEmpty() ? -1 : outputStack.pop();     } }

我们在 LeetCode 中提交以上测试代码,执行结果如下:

怎么用两个栈实现一个队列

注意事项

在整个实现过程中有两个小细节需要特别注意一下:

第 1 个栈只负责入栈(暂存数据),第 2 个栈只负责出栈(最终的队列执行顺序);

每次栈 2 出栈时都要把所有的元素都出完之后,才能从栈 1 中追加(添加)新数据,当栈 2 的数据没有全部出栈完成时,不能将栈 1 的元素入栈到栈  2,这样会导致元素的执行顺序混乱。

感谢各位的阅读,以上就是“怎么用两个栈实现一个队列”的内容了,经过本文的学习后,相信大家对怎么用两个栈实现一个队列这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI