算法图：如何实现一个有两个栈的队列？_0

本文转载自微信公众号“Java中文社区”，作者雷哥。转载本文请联系Java中文社区公众号。本文已收录在https://github.com/vipstone/algorithm《算法图解》系列中。队列和栈是计算机中两个非常重要的数据结构。经过前面的学习（《队列》，《栈》），我们知道了它们各自的特点。队列是先进先出（FIFO），栈是先进后出（FILO），如何用栈来实现队列呢？这是一个经典的面试问题，所以我们将在本文中实现它。在正式开始之前，我们先来回顾一下栈和队列的常用方法。栈（Stack）的常用方法有以下几种：push()：压入方法，将元素添加到栈顶；pop()：pop方法，取出栈顶元素并返回该元素；peek()：查询栈顶元素，不移除元素。队列（Queue）的常用方法有以下几种：offer()：enqueue方法，向队列尾部添加元素；poll()：dequeue方法，从队头取出并返回元素；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/解题思路这道题的意思其实很好理解。就是把先进后出的栈改成先进先出的队列。其实题中也给出了一些提示，“用两个栈实现一个队列”。这道题的核心思想是“负转正”。我们先用一个栈来存放元素（此时第一个进入的元素在栈底），然后将第一个栈中的元素移动到新的栈中，此时第一个进入的元素为在栈顶，然后在用第二个栈出栈的时候，整个执行顺序就变成了先进先出。接下来，我们将以图形化的方式实现整个过程。Step1：先将元素压入第一个栈，如下图：Step2：将第一个栈中的所有元素移动到第二个栈中，如下图：Step3：将第二个栈中的所有元素stack是从一层入栈出栈，如下图：总结从上图可以看出，添加元素的顺序是1、2、3，两次入栈后出栈的顺序也是1，2、3，所以我们通过这两个栈实现了一个队列（先进先出）。实现代码下面我们就用代码来实现上面的思路：classCQueue{StackinputStack;//栈容器（添加时操作）StackoutputStack;//出栈和查询的栈容器publicCQueue(){inputStack=newStack();outputStack=newStack();}//添加操作publicvoidappendTail(intvalue){inputStack.push(value);}//删除操作publicintdeleteHead(){if(!outputStack.isEmpty()){//弹出容器不为空{outputStack.push(inputStack.pop());}}returnoutputStack.isEmpty()?-1:outputStack.pop();}}我们在LeetCode中提交上面的测试代码，执行结果如下：注意有整个实现过程中有两个小细节需要特别注意：第一个栈只负责push（暂存数据），第二个栈只负责forpopping（最终队列执行顺序）；每次出栈2时，必须将所有元素出栈完成后，才能从栈1追加（追加）新数据。当栈2中的数据还没有完全出栈时，栈1的元素不能被压入栈2，会导致元素的执行顺序被打乱。综上所述，在本文??中，我们通过两个先进先出的栈和“负为正”的思想实现了队列的先进先出特性。(stack)不能将第一个栈中的元素添加到第二个栈中，以免造成程序执行顺序的混乱。原文链接：https://mp.weixin.qq.com/s/18GdYCCaaltx4ZMVkPsptg