LCR 125.用队列实现栈
难度：🟢 简单
标签：栈、设计、队列
链接：LCR 125. 用队列实现栈 (剑指 Offer 09. 用两个栈实现队列)
题目描述
请用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
解题思路
核心思想
本题的核心挑战在于，栈是“后进先出”（LIFO），而队列是“先进先出”（FIFO）。我们需要通过组合两个栈的操作来模拟出 FIFO 的效果。关键在于如何将最早进入的元素移动到可以被访问的位置（栈顶）。
思路选择
双栈法（输入栈+输出栈） 是解决此问题的最优思路。
我们使用一个栈
inStack专门负责入队（appendTail）。我们使用另一个栈
outStack专门负责出队（deleteHead）。当
appendTail时，直接将元素压入inStack。当
deleteHead时，先检查outStack。如果outStack非空，其栈顶元素就是队首，直接弹出。如果outStack为空，则需要将inStack的所有元素依次弹出并压入outStack，这个过程会将inStack的元素顺序颠倒，使得最早进入的元素位于outStack的栈顶。完成“倒腾”后，再从outStack弹出。
这种方法通过 摊还分析，可以实现 deleteHead 的均摊时间复杂度为 O(1)。
关键步骤
初始化：创建两个空栈，
inStack和outStack。appendTail(value): 直接将value压入inStack。deleteHead(): a. 检查outStack是否为空。 b. 如果 不为空，直接pop并返回outStack的栈顶元素。 c. 如果 为空，再检查inStack是否也为空。如果都为空，说明队列为空，返回-1。 d. 如果inStack不为空，则将inStack的所有元素pop出来并push进outStack。 e. 完成元素转移后，pop并返回outStack的栈顶元素。
代码实现 (推荐)
var CQueue = function () {
this.inStack = []; // 输入栈
this.outStack = []; // 输出栈
};
/** * @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function (value) {
this.inStack.push(value);
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function () {
// 如果输出栈不为空，直接弹出
if (this.outStack.length) {
return this.outStack.pop();
}
// 如果输入栈也为空，则队列为空
if (!this.inStack.length) {
return -1;
}
// 将输入栈的元素全部转移到输出栈
while (this.inStack.length) {
this.outStack.push(this.inStack.pop());
}
// 从输出栈弹出
return this.outStack.pop();
};
原始代码分析 (用户提供)
您提供的解法可以正确工作，但效率有待优化。它在每次 deleteHead 时都进行了两次完整的数据迁移。
var CQueue = function () {
// 主栈，用于存储数据
this.valStack = [];
// 临时栈，仅在 deleteHead 时使用
this.tempStack = [];
};
/** * @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function (value) {
this.valStack.push(value);
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function () {
if (this.valStack.length === 0) return -1;
// 1. 每次都将 valStack 倒入 tempStack
while (this.valStack.length !== 0) {
this.tempStack.push(this.valStack.pop());
}
// 获取队首
let result = this.tempStack.pop();
// 2. 每次都将 tempStack 倒回 valStack
while (this.tempStack.length !== 0) {
this.valStack.push(this.tempStack.pop());
}
return result;
};
优点：逻辑简单，只用一个主栈和一个临时栈。
待改进：
deleteHead操作的时间复杂度总是 O(n)，因为它每次都需要将所有元素“倒腾”两遍。推荐解法通过维护一个专门的输出栈，避免了不必要的数据迁移，使得deleteHead的均摊复杂度更低。
复杂度分析
时间复杂度：
appendTail: O(1)deleteHead: 均摊 O(1)。虽然在某些情况下需要 O(n) 的时间来迁移元素，但每个元素最多只会被迁移一次（从inStack到outStack）。因此，n 次deleteHead操作的总时间与 n 成正比，均摊下来每次操作是 O(1)。
空间复杂度：O(n) 其中 n 是队列中元素的数量。两个栈最多需要存储所有 n 个元素。
相关题目
总结
本题是数据结构设计类的经典题目，旨在考察如何用 LIFO 的栈来模拟 FIFO 的队列。推荐的双栈法（输入/输出栈）通过“懒加载”的方式（仅在输出栈为空时才迁移数据），巧妙地实现了均摊 O(1) 的出队操作，是面试中期望的标准答案。