企业官网建设流程全解析

• 示例工程
• 教程

本文围绕《剑指 Offer（第 2 版）》面试题 09 展开，完整讲解如何仅用栈（LIFO）这一数据结构模拟出队列（FIFO）的入队与出队语义，并给出 doocs/leetcode 仓库中 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Swift 九种语言的实现细节。读完本文，你不仅能透彻理解「双栈倒序」这一经典数据结构的组合技巧，还能掌握其时间复杂度分析与边界处理，为面试中同类「用受限数据结构实现另一数据结构」的题目（如用两个队列实现栈、包含 min 函数的栈）打下基础。

题目背景与考点定位

本题出自《剑指 Offer（第 2 版）》，是栈与队列这对「语义相反」的数据结构最经典的组合题。题目要求实现一个队列类CQueue，对外提供两个方法：

• appendTail(value)：在队列尾部插入整数；
• deleteHead()：在队列头部删除整数，若队列为空则返回-1。

其核心考点是数据结构语义的转换：栈是后进先出（LIFO），队列是先进先出（FIFO），两者对元素的「取出顺序」完全相反。题目给出的约束是只能使用栈，不能直接使用队列或链表，因此必须通过两个栈的协作来「扭转」元素顺序。

在 doocs/leetcode 仓库中，本题收录于 lcof 系列目录，标签为栈、设计，难度为「简单」，同系列还有面试题 30（包含 min 函数的栈）等同类「栈 + 设计」题型，可作为练习延伸。

题目描述与输入输出约定

示例 1

输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1]

操作序列含义：创建队列 → 尾部插入 3 → 删除头部（得 3）→ 再次删除头部（队列已空，返回 -1）。

示例 2

输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]

操作序列含义：创建队列 → 删除头部（队列为空，返回 -1）→ 尾部插入 5 → 尾部插入 2 → 删除头部（按 FIFO 应返回先入队的 5）→ 删除头部（返回 2）。

数据约束

• 入队元素取值：1 <= values <= 10000；
• 对appendTail、deleteHead的调用次数最多为10000次。

从约束看，本题不要求刻意优化常数，但方法设计仍需保证在 10^4 次调用下整体高效，这引出了下文「摊销 O(1)」的分析。

解法思路：为什么两个栈能实现队列

核心直觉：单个栈只能在一端（栈顶）操作，天然是「后进先出」；而队列需要在两端操作——尾部进、头部出。如果只用一个栈，出队时拿到的永远是最后入队的元素，顺序完全颠倒。

破局点：引入第二个栈把顺序「倒回来」。

1. stk1负责接收入队元素：appendTail直接压入stk1，此时栈顶即队列尾部；
2. deleteHead出队时，若stk2为空，则把stk1中的元素逐个弹出并压入stk2——经过这一次倒序，stk1栈底（最先入队、队列头部）的元素被翻转到stk2的栈顶；
3. 之后每次出队直接从stk2弹出栈顶即可，直至stk2被取空后再进行下一次批量倒序；
4. 若两个栈均为空，说明队列中没有元素，返回-1。

为什么正确：栈的倒序操作相当于把「先进后出」抵消一次变成「先进先出」。入队顺序a, b, c压入stk1后栈内从上到下为c, b, a；全部倒入stk2后，stk2从上到下为a, b, c，恰好恢复为入队顺序，弹出时得到a（最先入队者），符合队列语义。

关键性质：每个元素至多被「进出」两次——一次压入stk1、一次从stk1转移到stk2、一次从stk2弹出。因此单次deleteHead虽在最坏情况下需要 O(n) 的搬运，但摊还到每个元素上仍为 O(1)。

多语言实现：仓库源码逐一拆解

以下实现与仓库 lcof/面试题09. 用两个栈实现队列 目录下的Solution.*文件一一对应，可对照阅读。

Python3（对应 Solution.py）

class CQueue: def __init__(self): self.stk1 = [] self.stk2 = [] def appendTail(self, value: int) -> None: self.stk1.append(value) def deleteHead(self) -> int: if not self.stk2: while self.stk1: self.stk2.append(self.stk1.pop()) return -1 if not self.stk2 else self.stk2.pop() # Your CQueue object will be instantiated and called as such: # obj = CQueue() # obj.appendTail(value) # param_2 = obj.deleteHead()

要点：deleteHead中先检查stk2是否为空，空时才触发搬运；搬运后再次判空决定返回-1还是弹出栈顶。两行逻辑把「空队列」与「正常出队」两种分支合并处理。

Java（对应 Solution.java）

class CQueue { private Deque<Integer> stk1 = new ArrayDeque<>(); private Deque<Integer> stk2 = new ArrayDeque<>(); public CQueue() { } public void appendTail(int value) { stk1.push(value); } public int deleteHead() { if (stk2.isEmpty()) { while (!stk1.isEmpty()) { stk2.push(stk1.pop()); } } return stk2.isEmpty() ? -1 : stk2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

要点：使用ArrayDeque充当栈（push/pop均为栈顶操作），比java.util.Stack更推荐——Stack继承自Vector，方法带synchronized且有历史包袱；ArrayDeque底层为可扩容数组，栈操作 O(1) 且无锁开销。

C++（对应 Solution.cpp）

class CQueue { public: CQueue() { } void appendTail(int value) { stk1.push(value); } int deleteHead() { if (stk2.empty()) { while (!stk1.empty()) { stk2.push(stk1.top()); stk1.pop(); } } if (stk2.empty()) { return -1; } int ans = stk2.top(); stk2.pop(); return ans; } private: stack<int> stk1, stk2; }; /** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */

要点：注意 C++ 的std::stack没有「查看并弹出」的一步操作，需先top()取值再pop()弹出；deleteHead中把空判断拆成两段，先处理搬运，再统一判空返回-1，逻辑更清晰。

Go（对应 Solution.go）

type CQueue struct { stk1, stk2 []int } func Constructor() CQueue { return CQueue{[]int{}, []int{}} } func (this *CQueue) AppendTail(value int) { this.stk1 = append(this.stk1, value) } func (this *CQueue) DeleteHead() int { if len(this.stk2) == 0 { for len(this.stk1) > 0 { this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1]) this.stk1 = this.stk1[:len(this.stk1)-1] } } if len(this.stk2) == 0 { return -1 } ans := this.stk2[len(this.stk2)-1] this.stk2 = this.stk2[:len(this.stk2)-1] return ans } /** * Your CQueue object will be instantiated and called as such: * obj := Constructor(); * obj.AppendTail(value); * param_2 := obj.DeleteHead(); */

要点：Go 标准库没有专用栈类型，用切片模拟——append压栈、取len-1处元素为栈顶、切片缩容[:len-1]实现弹栈。Constructor显式初始化两个空切片。

TypeScript（对应 Solution.ts）

class CQueue { private stk1: number[]; private stk2: number[]; constructor() { this.stk1 = []; this.stk2 = []; } appendTail(value: number): void { this.stk1.push(value); } deleteHead(): number { if (this.stk2.length == 0) { while (this.stk1.length) { this.stk2.push(this.stk1.pop()); } } return this.stk2.length == 0 ? -1 : this.stk2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */

要点：利用数组push/pop天然符合栈语义；while (this.stk1.length)利用数值 0 的假值特性作为循环终止条件。

Rust（对应 Solution.rs）

struct CQueue { s1: Vec<i32>, s2: Vec<i32>, } /** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */ impl CQueue { fn new() -> Self { CQueue { s1: Vec::new(), s2: Vec::new(), } } fn append_tail(&mut self, value: i32) { self.s1.push(value); } fn delete_head(&mut self) -> i32 { match self.s2.pop() { Some(value) => value, None => { while !self.s1.is_empty() { self.s2.push(self.s1.pop().unwrap()); } self.s2.pop().unwrap_or(-1) } } } }

要点：Rust 版本借助Option的pop()返回值做模式匹配：stk2非空直接取栈顶；为空则先搬运再弹出，并用unwrap_or(-1)优雅处理「搬运后仍为空」的情况，全程无 panic 风险。

JavaScript（对应 Solution.js）

var CQueue = function () { this.stk1 = []; this.stk2 = []; }; /** * @param {number} value * @return {void} */ CQueue.prototype.appendTail = function (value) { this.stk1.push(value); }; /** * @return {number} */ CQueue.prototype.deleteHead = function () { if (!this.stk2.length) { while (this.stk1.length) { this.stk2.push(this.stk1.pop()); } } return this.stk2.length ? this.stk2.pop() : -1; }; /** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */

要点：采用构造函数 + 原型方法的写法，与 LeetCode 判题器的实例化约定一致；判空同样借助数组length的真假值。

C#（对应 Solution.cs）

public class CQueue { private Stack<int> stk1 = new Stack<int>(); private Stack<int> stk2 = new Stack<int>(); public CQueue() { } public void AppendTail(int value) { stk1.Push(value); } public int DeleteHead() { if (stk2.Count == 0) { while (stk1.Count != 0) { stk2.Push(stk1.Pop()); } } return stk2.Count == 0 ? -1 : stk2.Pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.AppendTail(value); * int param_2 = obj.DeleteHead(); */

要点：直接使用 .NET 的Stack<int>泛型栈，Push/Pop/Count语义清晰，与题目描述一一对应。

Swift（对应 Solution.swift）

class CQueue { private var stk1: [Int] = [] private var stk2: [Int] = [] init() { } func appendTail(_ value: Int) { stk1.append(value) } func deleteHead() -> Int { if stk2.isEmpty { while !stk1.isEmpty { stk2.append(stk1.removeLast()) } } return stk2.isEmpty ? -1 : stk2.removeLast() } } /** * Your CQueue object will be instantiated and called as such: * let obj = CQueue(); * obj.appendTail(value); * let param_2 = obj.DeleteHead(); */

要点：Swift 中数组的append/removeLast天然构成栈操作；removeLast()返回被移除的元素，与stk2.isEmpty判断配合即完成出队。

边界条件与正确性论证

实现虽短，但有三个必须正确处理的分支：

1. 连续出队直到stk2取空：一旦stk2非空，deleteHead必须直接弹stk2，绝不能重复搬运stk1——否则会把已在stk2中排好序的元素重新打乱。
2. stk2空但stk1非空：此时才触发批量倒序，倒序完成后stk2栈顶即队列头部。
3. 双栈皆空：队列中无元素，按题目约定返回-1（与「合法的入队元素1 <= values <= 10000」相呼应，-1不会与真实数据冲突）。

正确性的核心在于倒序操作的时机：入队永远压入stk1，出队永远来自stk2。stk1的栈顶方向是「新」，stk2的栈顶方向是「旧」，两者各自职责单一，互不干扰。

复杂度分析

理解摊还分析是本题的加分项：虽然单次deleteHead可能触发 O(n) 的搬运，但 10^4 次操作的总代价仍为 O(n) 级别（每个元素进出栈共 3 次常数操作），平均下来每次操作 O(1)。

扩展：同类题型的迁移思路

双栈模拟队列的核心方法论「用两个语义相反的结构互相倒序抵消」可以推广到一系列题目：

• 用两个栈实现队列（本题）：入栈栈 + 出栈栈，出队时倒序；
• 用队列实现栈：入队栈用普通队列，出栈时把前 n-1 个元素轮转到队尾，剩余队首即栈顶；
• 面试题 30 包含 min 函数的栈（仓库同系列，见 lcof/README.md）：用辅助栈记录历史最小值，本质也是「主结构 + 辅助结构」协同。

在 doocs/leetcode 仓库中，这类「数据结构设计」题的完整题解均位于 solution 目录 与 lcof 目录 下，同一题目通常配有README.md（含思路讲解与多语言标签页）和独立Solution.*源码文件，便于对照学习。

总结

「用两个栈实现队列」是一道信息密度极高的经典面试题：它同时考察对栈/队列语义的深刻理解、对操作时机的把握，以及摊还复杂度的分析能力。doocs/leetcode 仓库 面试题 09 题解 提供了九种主流语言的完整实现，读者可直接对照本文逐步推演「入栈 → 倒序 → 出栈」的完整数据流，将这套方法论内化为解决数据结构设计类题目的通用武器。

• 示例工程
• 教程