小编给大家分享一下java中用两个栈实现一个队列的案例,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
Java基础教程栏目介绍如何用两个栈实现一个队列。
队列和栈是计算机中两个非常重要的数据结构,经过前面的学习(《队列》、《栈》)我们知道了它们各自的特点,队列是先进先出(FIFO)的,而栈是先进后出(FILO)的,那如何用栈来实现队列呢?这可是一道经典的面试题,所以本文我们就来实现一下。
在正式开始之前,我们先来回顾一下栈和队列的常用方法。
栈(Stack)的常用方法包含以下这些:
队列(Queue)的常用方法包含以下这些:
有了这些前置知识,接下来我们来看今天的题目。
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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:leetcode-cn.com/problems/yo…
这道题目的意思其实很好理解,就是要将先进后出的栈改为先进先出的队列,其实问题中也给出了一些提示,“用两个栈来实现一个队列”。这道题实现的核心思想就是「负负得正」,我们先用一个栈来存入元素(这时最先进入的元素在栈底),然后再将第一个栈中的元素移动到新栈中,此时最先进入的元素就在栈顶了,然后在用第二个栈出栈时,整个执行的顺序就变成了先进先出。
接下来,我们用图解的方式来实现一下整个流程。
先将元素入栈到第一个栈中,如下图所示:
将第一个栈中的元素都移动到第二个栈中,如下图所示:
所有元素从第二个栈中出栈,如下图所示:
从上述图片可以看出,元素添加顺序是 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 中提交以上测试代码,执行结果如下:
在整个实现过程中有两个小细节需要特别注意一下:
以上是java中用两个栈实现一个队列的案例的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。