如何用两个栈实现一个队列算法,如何用两个栈实现一个队列,完成队列中的offer操作

　　Java基础教程栏目介绍如何用两个栈实现一个队列。

　　如何解决写爬虫IP受阻的问题？立即使用。

　　队列和堆栈是计算机中两个非常重要的数据结构。经过前面的研究(《队列》，《栈》)，我们知道了它们各自的特点。队列是FIFO，而堆栈是FILO。那么如何用栈实现队列呢？这是一个经典的面试问题，所以我们会在本文中实现。

　　在开始之前，让我们回顾一下堆栈和队列的常用方法。

　　常见的堆叠方法包括以下几种：

　　Push (): Stack方法，将元素添加到栈顶；pop():pop-out方法，移除堆栈顶部的元素并返回该元素；Peek():查询栈顶元素不会删除该元素。

　　常见的排队方法包括以下几种：

　　Offer (): enqueue方法，将元素添加到队列末尾；Poll (): dequeue方法，它从队列的头部移除并返回元素；Peek():查询队列头元素不会删除该元素。有了这些预备知识，我们再来看今天的话题。

题目描述

　　实现具有两个堆栈的队列。队列的声明如下。请实现它的两个函数appendTail和deleteHead，分别在队列末尾插入整数和在队列头删除整数。如果队列中没有元素，deleteHead操作将返回-1。

　　示例1:

　　示例2:

　　提示：

解题思路

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

　　接下来，我们来举例说明整个过程。

步骤一

　　首先将元素堆栈到第一个堆栈中，如下图所示：

步骤二

　　将第一个堆栈中的所有元素移动到第二个堆栈中，如下图所示：

步骤三

　　从第二个堆栈中弹出所有元素，如下图所示：

小结

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

实现代码

　　接下来，我们将使用代码来实现上述想法：

　　类队列{

　　StackInteger输入stack；//堆叠容器(添加时的操作)

　　StackInteger输出stack；//弹出和查询的堆栈容器

　　公共CQueue() {

　　input Stack=new Stack()；

　　output Stack=new Stack()；

　　}//添加操作

　　public void appendTail(int value){

　　inputStack.push(值)；

　　}//删除操作

　　public int deleteHead() { if(！output stack . isempty()){///堆栈容器不为空。

　　返回output stack . pop()；

　　} else if(！input stack . isempty()){///所有传入堆栈都转移到传出堆栈。

　　而(！inputStack.isEmpty()) {

　　output stack . push(input stack . pop())；

　　}

　　} return outputStack.isEmpty()？-1:output stack . pop()；

　　}

　　}复制代码我们在LeetCode中提交上述测试代码，执行结果如下：

注意事项

　　在整个实施过程中，有两个小细节需要特别注意：

　　第一个栈只负责堆栈(临时存储数据)，第二个栈只负责弹出(最后的队列执行序列)；每次堆栈2离开堆栈时，在可以从堆栈1添加新数据之前，必须检查所有元素。当栈2的所有数据都离开栈时，栈1的元素就无法放入栈2，这会导致元素执行顺序的紊乱。

总结

　　在本文中，我们通过“负-负-正”的思想，通过两个栈实现了队列的先进先出特性。但需要注意的是，当第二个栈，即栈外容器不为空(stack)时，第一个栈中的元素不能添加到第二个栈中，以免程序执行顺序混乱。

　　这就是如何实现具有两个堆栈的队列。更多详情请关注我们的其他相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。