栈和队列的基本操作（剑指Offer09-用两个栈实现队列）

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

我们先来分析下栈和队列这两种数据结构的特点：

数据结构	常用方法	特点
栈	入栈 - push 出栈 - pop 查看栈顶元素，不会删除 - peek	先进后出
队列	入队 - offer 出队 - poll 查看队列头元素，不会删除 - peek	先进先出

假设我们有1，2，3三个元素，按照顺序进行添加，我们来看看栈和队列获取元素时的顺序：

栈和队列

可以得到：

• 栈 - 先进后出，出栈顺序为3，2，1
• 队列 - 先进先出，出队顺序为1，2，3

可以看出来出栈顺序是出队顺序的倒序，由栈先进后出的特点，其实可以实现元素的倒序输出，两次倒序其实就可以实现顺序不变：

• 入栈1，2，3 -> 出栈3，2，1
• 入栈3，2，1 -> 出栈1，2，3

两个栈组成队列

那么什么时候s0出栈，s1入栈呢？

当s1栈内没有元素，还需要删除头节点时，执行s0出栈，s1入栈

因为如果s1栈内还有元素，这个时候执行s0出栈，s1入栈，那么就会覆盖一些s1已有的元素，不满足队列先进先出的特点

解题步骤：

1. 定义两个栈s0，s1，其中s0栈负责添加元素，s1栈负责删除元素
2. 尾部添加元素，直接入栈s0
3. 头部删除元素

先判断s1栈是否还有元素，如果有则直接将s1栈顶元素出栈

如果s1栈没有元素，则判断s0栈是否还有元素

如果s0栈也没有元素，则说明栈内没有元素，直接返回-1

如果s0栈内有元素，则把s0元素全部出栈，入栈s1，然后将s1栈顶元素出栈

代码

class CQueue { // 声明两个栈，s0负责添加，s1负责删除 private Stack<Integer> s0; private Stack<Integer> s1; public CQueue() { // 初始化栈 s0 = new Stack<>(); s1 = new Stack<>(); } public void appendTail(int value) { // 尾部添加元素，直接入栈s0 s0.push(value); } public int deleteHead() { // 头部删除元素，先判断s1是否有元素 if (s1.size() == 0) { // 若s1栈内没有元素，则判断s0是否有元素 if (s0.size() == 0) { // 如果s0也没有元素，则说明两个栈内都没有元素，直接返回-1 return -1; } // s1没有元素，s0有元素，则把s0元素全部出栈，入栈到s1 while (s0.size() != 0) { s1.push(s0.pop()); } } // s1有元素，直接出栈 return s1.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

复杂度：

• 空间复杂度：栈内最多存在的元素为N，所以空间复杂度为O(N)
• 时间复杂度：appendTail的时间复杂度为O(1)；deleteHead方法内，第一次调用会把s0栈内所有元素出栈，然后入栈到s1，元素最多为N，时间复杂度为O(N)

,