# 剑指 Offer 09. 用两个栈实现队列
大家好，我是吴师兄。
今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。
# 一、题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用
# 二、题目解析
首先，我们来复习一下栈和队列的特点。
1、栈是一个先进后出的线性表。
2、队列是一个先进先出的线性表。
根据这两个特点，如果说想让栈实现队列的先进先出的功能，必须得先将栈中最开始进入的元素栈底元素第一个出栈，但由于上方有很多其它元素，无法出栈，所以第一步是需要将上方所有元素先出栈。
如图 1 所示，5 比 2 更早的加入到栈中，因此想要实现队列的先进先出的功能，5 应该比 2 更早的出栈，但它的上方有个其它元素 2。
因此，需要先将栈 stack1 中的元素逐个出栈加入到栈 stack2 中，这样原先 stack1 中的栈底元素变成了 stack2 中的栈顶元素，5 可以比后面加入的 2 更早的出栈，实现了队列的先进先出的功能。
接下来，再具体解析一下题目描述中所给的示例的含义。
# 1、CQueue
首先初始化，没有参数，所以是 []，然后我们注意到 CQueue() 函数是没有返回值的，用 null 来表示（不要问我为什么用 null 表示。。。）
# 2、deleteHead
删除操作，没有参数，所以是 []，根据题意若队列中没有元素，deleteHead 操作返回 -1 ，所以输出值为 -1 。
# 3、appendTail
插入操作，有参数，此时是 **5 **，并且 appendTail() 函数没有返回值的，用 null 来表示。
# 4、appendTail
插入操作，有参数，此时是 **2 **，并且 appendTail() 函数没有返回值的，用 null 来表示。
# 5、deleteHead
删除操作，没有参数，所以是 []，此时队列中有元素，先进入的是 5，后进入的是 2，根据队列先进先出的性质，元素 5 出列，所以返回值是 5 。
# 6、deleteHead
删除操作，没有参数，所以是 []，此时队列中有元素，只有元素 2，所以返回值是 2 。
基本上看完上面的大白话翻译就可以理解题意，解决问题也不难了。
# 入队操作
如果是栈的插入操作，那我们可以把元素都先插入到 stack1 中，也就实现了队列的 入队操作 。
# 出队操作
- 当 stack2 中不为空时，直接操作，此时在 stack2 中的栈顶元素是最先进入队列的元素，返回该元素即可；
- 如果 stack2 为空且 stack1 也为空，返回 -1；
- 如果 stack2 为空且 stack1 不为空，首先需要把 stack1 中的元素逐个弹出并压入到 stack2 中，然后返回 stack2 的栈顶元素即可。
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
# 三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀，微信 wzb_3377
// Java 中的 Stack 类设计有问题，大部分情况下是使用 LinkedList 来构建栈，但为了结合动画更好的理解这道题目，所以依旧使用 Stack
class CQueue {
// 队列的特点，先进先出
// 栈的特点是先进后出
// 创建两个栈
// 创建栈 stack1 用来充当队列
Stack<Integer> stack1;
// 创建栈 stack2 用来辅助 stack1 执行队列的一些复杂操作
Stack<Integer> stack2;
// 这个函数是 creat queue
// 意思就是初始化队列
// 由于题目要求我们用两个栈实现队列，所以在这个函数中初始化的是两个栈
public CQueue() {
// 初始化 stack1
stack1 = new Stack<Integer>();
// 初始化 stack2
stack2 = new Stack<Integer>();
}
// 这个函数的意思是在队列的尾部添加元素
// 使用栈来完成这个操作的话就是在 stack1 的后面添加元素就行
public void appendTail(int value) {
// 直接将元素存放到 stack1 中
// 比如原队列为
// -------------
// 队尾 1 2 3 4 5 队头
// -------------
// 当前 value 为 6
// 那么由 stack1 和 stack2 组成的队列就是
// ----------------
// 队尾 6 1 2 3 4 5 队头
// ----------------
stack1.push(value);
}
// 这个函数的意思是在队列的头部删除元素
// 由于队列的特点是先进先出，所以需要借助 stack1 和 stack2 去定位到之前存储进来的元素
public int deleteHead() {
// 1、如果 stack2 栈不为空，说明 stack2 里面已经存储了一些元素，
// 并且 stack2 的栈顶元素就是两个栈中最早加入的元素
if(!stack2.isEmpty()){
// 返回 stack2 的栈顶元素，满足了队列先进先出的特点
return stack2.pop();
}
// 2、如果 stack2 为空，并且发现 stack1 也为空，
// 说明 stack1 和 stack2 构建的队列中没有元素，
if(stack1.isEmpty()){
// 根据题意，直接返回 -1
return -1;
}
// 3、如果 stack2 为空，但 stack1 不为空
// 那么需要先将 stack1 中的元素依次【倒序】放入 stack2 中
// 对于 stack1 来说，越早加入的元素在【栈底】，越晚加入的元素在【栈顶】
// 由于队列是【先进先出】，所以删除的应该是 stack1 的【栈底】元素
while(!stack1.isEmpty()){
// 获取 stack1 的栈顶元素并将该元素从 stack1 中弹出
int topValue = stack1.pop();
// 把该元素加入到 stack2
// 这样 stack2 的栈顶元素就是 stack1 的栈底元素
stack2.push(topValue);
}
// 4、返回 stack2 的栈顶元素，满足了队列先进先出的特点
return stack2.pop();
}
}