本文转载自微信公众号「Java中文社群」，算法作者磊哥 。图解转载本文请联系Java中文社群公众号。何用 

本文已收录至 https://github.com/vipstone/algorithm 《算法图解》系列。栈实

队列和栈是队列计算机中两个非常重要的数据结构，经过前面的算法学习(《队列》、《栈》)我们知道了它们各自的图解特点，队列是何用先进先出(FIFO)的，而栈是栈实先进后出(FILO)的，那如何用栈来实现队列呢?队列这可是一道经典的面试题，所以本文我们就来实现一下。算法

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

栈(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，这样会导致元素的执行顺序混乱。服务器托管

总结

本文我们通过两个先进后出的栈，通过“负负得正”的思路实现了队列先进先出的特性，但需要特别注意的是当第 2 个栈也就是出栈容器，在非空(栈)时不能将第 1 个栈中的元素添加到第 2 个栈中，以免造成程序执行顺序混乱。

原文链接：https://mp.weixin.qq.com/s/18GdYCCaaltx4ZMVkPsptg