Stack Queue

Stack / Queue

两种"有规则"的容器 / Two Rule-Based Containers

vector、set、map 是通用容器。stack 和 queue 是专门按访问顺序设计的容器：元素怎么进去、怎么出来，有严格规则。

vector, set, map are general-purpose. stack and queue are designed around access order: how elements enter and exit follows strict rules.

• Stack —— 后进先出（LIFO）。

• Queue —— 先进先出（FIFO）。

• Stack — last in, first out (LIFO).

• Queue — first in, first out (FIFO).

---

Stack：后进先出 / Stack: Last In, First Out

想象一摞盘子：最后放上去的，最先被拿走。

Picture a stack of plates: the last placed on top comes off first.

创建与操作 / Creating and Operating

var s = stack();

s.push("A");
s.push("B");
s.push("C");

现在栈里从底到顶是 A, B, C。

Now the stack holds A, B, C from bottom to top.

查看栈顶 / Peeking

peek() 返回栈顶元素，不移除：

peek() returns the top element without removing:

string top = s.peek();      // "C"

弹出栈顶 / Popping

pop() 返回并移除栈顶：

pop() returns and removes the top:

string a = s.pop();         // "C"，栈变 A, B
string b = s.pop();         // "B"，栈变 A
string c = s.pop();         // "A"，栈空

空判断 / Empty Check

空栈上 pop 或 peek 会报错。操作前先检查：

Calling pop or peek on an empty stack errors. Check first:

if (!s.isEmpty()) {
    string top = s.pop();
}

---

Queue：先进先出 / Queue: First In, First Out

想象排队买票：最先来的先被服务。

Picture a queue at a ticket booth: first come, first served.

创建与操作 / Creating and Operating

var q = queue();

q.offer("A");
q.offer("B");
q.offer("C");

队列从头到尾是 A, B, C。

The queue holds A, B, C from front to back.

查看队首 / Peeking

peek() 返回队首元素，不移除：

peek() returns the front element without removing:

string front = q.peek();    // "A"

出队 / Polling

poll() 返回并移除队首：

poll() returns and removes the front:

string a = q.poll();        // "A"，队列变 B, C
string b = q.poll();        // "B"
string c = q.poll();        // "C"

空判断 / Empty Check

和栈一样，空队列上 poll 或 peek 会报错：

As with stacks, poll or peek on an empty queue errors:

if (!q.isEmpty()) {
    string front = q.poll();
}

---

对比表 / Comparison

操作	Stack	Queue
添加	push(x)	offer(x)
取出	pop()	poll()
查看	peek()	peek()
空判断	isEmpty()	isEmpty()
取出顺序	后进先出	先进先出

Operation	Stack	Queue
Add	push(x)	offer(x)
Remove	pop()	poll()
Peek	peek()	peek()
Empty check	isEmpty()	isEmpty()
Removal order	LIFO	FIFO

注意添加方法名不同：栈用 push，队列用 offer。写错会报"找不到方法"。

Note the different add methods: stacks use push, queues use offer. A mismatch errors as "method not found".

---

什么时候用 / When to Use

用 Stack 的场景 / When to Use a Stack

• 撤销 / 重做：把每一步操作压入栈，撤销时弹出。

• 深度优先遍历：处理嵌套结构时逐个深入。

• Undo / redo: push each operation; pop to undo.

• Depth-first traversal: descend into nested structures.

var history = stack();

// 记录一次操作
history.push("玩家 Steve 使用了传送");

// 撤销
if (!history.isEmpty()) {
    string last = history.pop();
    runcmd("CONSOLE", "say 已撤销: " + last);
}

用 Queue 的场景 / When to Use a Queue

• 任务队列：按提交顺序处理。

• 广播排期：按顺序依次发送。

• 广度优先遍历：逐层处理。

• Task queue: process in submission order.

• Broadcast scheduling: send in order.

• Breadth-first traversal: process level by level.

var tasks = queue();
tasks.offer("给 Steve 发奖励");
tasks.offer("给 Alex 发奖励");
tasks.offer("给 Herobrine 发奖励");

while (!tasks.isEmpty()) {
    string task = tasks.poll();
    runcmd("CONSOLE", "say 处理: " + task);
}

---

常见错误 / Common Mistakes

错误一：在空容器上操作

var s = stack();
string x = s.pop();         // ✗ 报错：栈为空

总是先 isEmpty() 检查。

错误二：把 pop 当 poll 用

var q = queue();
q.push("A");                // ✗ 队列没有 push
q.pop();                    // ✗ 队列没有 pop

队列用 offer / poll。

错误三：误以为栈也能 get(i)

Stack 和 Queue 没有下标，不能 s.get(0)。要按下标访问，用 vector。

Mistake 1: Operating on an empty container

Always isEmpty() first.

Mistake 2: Confusing push/pop with offer/poll

Queue uses offer / poll.

Mistake 3: Expecting index access

Stacks and queues have no indices. Use vector for indexed access.

---

小结 / Summary

• stack() 后进先出，push / pop / peek。

• queue() 先进先出，offer / poll / peek。

• 空容器上 pop、poll、peek 会报错，先检查。

• 栈适合撤销、深度优先；队列适合任务、广度优先。

• 需要按下标访问时，用 vector。

• stack() LIFO, with push / pop / peek.

• queue() FIFO, with offer / poll / peek.

• pop / poll / peek on empty containers error.

• Stacks: undo, DFS. Queues: tasks, BFS.

• Need indexed access? Use vector.

---

下一步 / Next Steps

下一章 JSON 介绍如何把容器转成字符串、以及如何从字符串还原容器。

Next, JSON covers converting containers to strings and back.

---