Appearance
6. 撤销魔法（栈）
知识点：栈（stack）—— 后进先出
项目：魔法记事本（撤销功能）+ 括号配对检查
故事开场：手滑写错了，怎么办？
你正在做一个"魔法记事本"程序：可以往里面写笔记，也可以撤销上一步操作。
第一版很容易：用一个变量记住"上一次的内容"：
ts
let current = ""
let last = "" // 记住上一次的笔记
function input(text: string): void {
last = current // 写之前，先存个备份
current = text
}
function undo(): void {
current = last // 撤销：把备份拿回来
last = "" // 备份用完就没了
}运行一下试试：写"早上好"，再写"中午好"，然后撤销——变回"早上好"，成功了！
可是老师过来一看，说："只能撤销一次？我在写长作文，要能撤销十次！ 写错了三次才反应过来，结果只能退回一步，前面的错字怎么办？"
你想了想：用一个变量不够，那就用一个数组，把每一次的备份都存下来？ 可是——该从数组的哪一头拿"最近的一次"呢？
笨办法先行：一摞纸
想清楚这个问题，先做一个生活实验。
拿一叠白纸，一张一张往上放：第一张放"早上好"，第二张放"中午好"， 第三张放"晚上好"。
现在，你要撤销——回到"最近一次"的状态。哪一张是最新的？ 当然是最上面那一张（最后放上去的）。
如果继续撤销呢？拿走最上面那张，露出来的就是"中午好"；再拿一张，是"早上好"。
发现规律了吗？
最后放上去的，最先被拿走。
我们想想用数组怎么写。如果你用 push 把每一次的备份依次放进数组：
[第一版, 第二版, 第三版] ← 第三版在最后，也就是"最上面"那么"拿最近的一份"，就是拿走数组的最后一个——用 pop！ push（放上去）和 pop（拿下来），天生就是一对。
引出知识点：栈——"后进先出"的一摞盘子
在计算机里，这种"只能从同一头放、从同一头拿"的结构，叫做栈（stack）。
栈有个响亮的规则：后进先出（LIFO，Last In First Out）—— 最后进来的，最先出去。
生活中的栈到处都是：
- 叠盘子：最后洗好的盘子放在最上面，用的时候先拿最上面的
- 饼干罐：你把饼干一块块放进去，拿的时候先从最上面拿
- 浏览器后退按钮：你逛了 A → B → C 三个网页，点"后退"回到哪个？ 当然是最后去的 C 回 B，再回 A——这正是栈！
- 撤销功能：编辑器、画图软件里的"撤销"，都是一摞操作记录
栈只有两个基本动作：
| 动作 | 名字 | 干什么 |
|---|---|---|
push | 压栈 | 把东西放到最上面 |
pop | 出栈 | 把最上面的东西拿走 |
在 TypeScript 里，数组自带 push 和 pop——数组就是我们现成的栈！
动手实现：可以撤销十次的魔法记事本
现在重写记事本：不用一个变量，用一摞"备份"：
ts
const history: string[] = [] // 一摞备份，新的备份放在最上面
let current = "" // 现在的笔记
// 写笔记：先把当前内容存进备份摞，再写新的
function input(text: string): void {
history.push(current)
current = text
console.log("笔记：" + current)
}
// 撤销：把最上面的备份拿下来
function undo(): void {
if (history.length === 0) {
console.log("没有可以撤销的了")
return
}
const last = history.pop() // 拿走最上面的备份
if (last !== undefined) {
current = last
}
console.log("撤销后：" + current)
}
input("早上好")
input("中午好")
input("晚上好")
undo()
undo()
undo()
undo()输出：
笔记：早上好
笔记：中午好
笔记：晚上好
撤销后：中午好
撤销后：早上好
撤销后：
没有可以撤销的了撤销到底，一路退回到空白（"撤销后："后面什么都没写）， 再撤就提示"没有可以撤销的了"。想撤销一百次？只要备份摞里还有， 就能一直撤——写一百次笔记，就有一百份备份。一个 push 一个 pop， 全部搞定。
跑起来：括号配对检查员
栈最经典的用法，是检查括号配不配对。
写数学式子时，我们规定：每个 ( 都要有一个 ) 和它配对， 而且后写的括号要先闭合——就像套娃，先打开的最后关上：
((1+2)×(3+4)) ✅ 配对
(1+2 ❌ 少了一个右括号
)(1+2( ❌ 反了：右括号跑到了前面怎么让程序来检查？用栈：
- 看到
(：压栈（打开一个盒子） - 看到
)：先检查栈里有没有(——有，就出栈（关上一个盒子）； 没有，说明这个右括号是"孤儿"，配对失败 - 全部看完：栈里还有没关上的
(？配对失败；栈空空的？配对成功！
ts
// 检查括号是否配对
function checkBrackets(text: string): boolean {
const stack: string[] = [] // 打开的盒子摞
for (const ch of text) { // 把每个字符轮流拿出来
if (ch === "(") {
stack.push(ch) // 看到左括号：打开一个盒子
} else if (ch === ")") {
if (stack.length === 0) {
return false // 右括号来了，盒子摞却是空的！
}
stack.pop() // 关上一个盒子
}
}
return stack.length === 0 // 全部关上了才算配对成功
}
console.log(checkBrackets("((1+2)×(3+4))")) // true
console.log(checkBrackets("(1+2")) // false
console.log(checkBrackets(")(1+2(")) // false（for (const ch of text) 是"把字符串里的每个字符轮流拿出来"的新写法—— 比用下标省事，以后会经常用到。）
输出：
true
false
false看，短短几行代码，配对检查就完成了。这就是栈：打开关上的顺序，天然由 "后进先出"管着——后打开的盒子必须先关上，栈顶永远是最新打开的那个。
小挑战
- 三种括号：把检查员升级成能处理
()、[]、{}三种括号混用的版本 （提示：)必须和栈顶的(配对，]必须和栈顶的[配对—— 遇到右括号时，检查栈顶是不是对应的左括号，不是就失败）。 - 后退按钮：用数组模拟浏览器的后退功能：依次"访问"5 个网页， 后退 3 次，打印当前所在的网页。
- 反过来的密信：还记得密信章吗？用一个栈，把"放学后一起玩游戏" 一个字一个字压栈，再一个个弹出来——你会发现弹出来的顺序正好倒过来了！ 用代码验证一下这个"栈版加密器"。
课后练习
第 1 题（动手题）：魔法记事本实战
给记事本加一个"清空"按钮逻辑：把备份摞全部清空，笔记设为空字符串。 然后按下面的顺序测试：写"1"、写"2"、清空、撤销——会发生什么？为什么？
参考答案（点开查看）
ts
function clearAll(): void {
history.length = 0 // 清空备份摞
current = ""
console.log("已清空")
}测试结果：写"1"、写"2"、清空、撤销 → 提示"没有可以撤销的了"。
因为清空把备份摞清掉了，history.length === 0，撤销自然没有东西可用。 这很合理：清空 = 放弃所有历史，想撤销也撤销不回来了。
第 2 题（思考题）：只能看见最上面的
栈有一个特点：你只能看见最上面的一层，看不见下面的。 想一想，为什么栈不让你"直接拿走最底下的盘子"？如果允许随便拿， 它还是栈吗？
参考答案（点开查看）
因为栈的规则就是"后进先出"——只能从最上面放、从最上面拿。
如果允许随便拿中间的、最底下的，那结构就不是栈了（可以拿中间的 是"数组"，可以两头拿的是"双端队列"）。
正是这个"只能从上面拿"的规矩，保证了撤销永远拿的是最近一次的备份。 规矩越严格，用起来越不容易出错——这是数据结构的通用道理： 每个结构把一两条规矩管死，程序就不容易乱。
第 3 题（思考题）：数组就是栈？
我们说"数组自带 push 和 pop，就是现成的栈"。那么问题来了： 数组还允许 arr[3] = "任意位置" 这样直接改中间的格子——这是栈不允许的。
那么：程序用数组模拟栈，会不会有人偷偷"从中间拿盘子"？ 这算不算破坏栈的规矩？
参考答案（点开查看）
算！用数组模拟栈，只是"借用"了数组的 push/pop，规矩靠写程序的人自觉。
如果程序里别的地方不小心用了 arr[3] = ...，栈的"后进先出"就被破坏了， 撤销功能就会出错。
所以真正的程序里，会把栈封装成一个"只提供 push/pop"的小盒子， 把数组藏起来不让别人碰——以后学到"类"和"封装"时，你会明白怎么做。 （还记得魔法函数章吗？函数盒子也是这个思路：把内部藏起来，只留入口。）
下一课预告：打印店的叫号机"滴——请 3 号到柜台"。 栈是"后进先出"，可是排队明明应该是先来的先办事啊？那是什么结构？