Stacks

基础数据结构：栈 (3.2.4)

欢迎来到迷人的数据结构世界！我们之前已经学习了数组（Arrays）和列表（Lists）等结构。现在，我们将深入探讨“栈”（Stacks）——这是计算机科学中最简单、同时也是最核心的数据结构之一。

理解栈不仅仅是记忆术语，更重要的是理解许多关键的计算机进程（从子程序管理到“撤销”功能的实现）是如何依赖这一简单概念的。如果刚开始觉得有些抽象也没关系，我们会通过日常生活中的类比来帮你拆解它！

1. 后进先出 (LIFO) 原则

栈最重要的一个特性就是其严格的顺序原则：后进先出 (Last-In, First-Out, LIFO)。

想象一下咖啡厅里自动餐盘机中那叠洗好的盘子：

• 当放入一个新盘子时，它会放在最上面。（后进，Last In）。
• 当厨师需要盘子时，他们会从最上面取走一个。（先出，First Out）。

如果你依次放入盘子 A、B、C：

[A 在最底部，C 在最顶部。]
当你取出一个盘子时，必须先取走 C，然后是 B，最后才能取到 A。

记忆技巧：LIFO

Last In, First Out（后进先出）。联想一下 Stack of Plates（一叠盘子，即 S & P）！

2. 核心栈操作

课程大纲要求你掌握并应用栈的三种主要操作，以及在实现这些操作时必须进行的必要检查。

入栈 (Push)

将新项添加到栈顶的操作称为入栈 (Push)。

具体步骤：
1. 检查栈是否已满（如果没有空间，就不能执行入栈操作！）。
2. 如果未满，将新项放入当前栈顶位置。
3. 更新用于追踪栈顶的指针或索引。

例子：将“苹果”入栈到一个水果栈中，意味着“苹果”现在成为了新的栈顶元素。

出栈 (Pop)

移除并返回栈顶元素的操作称为出栈 (Pop)。

具体步骤：
1. 检查栈是否为空（如果没有元素，就不能执行出栈操作！）。
2. 如果非空，获取栈顶的元素。
3. 更新指针或索引，将栈顶下移（即移除该元素）。

关键点：出栈操作会移除该项，从而缩小栈的大小。

查看 (Peek/Top)

查看 (Peek)（有时也称为 Top）操作返回栈顶元素的值，但不会将其从栈中移除。

类比：稍微提起最上面的盘子看一眼下面的标签，然后把它放回原处。

3. 使用一维数组实现栈

尽管现代编程语言通常内置了栈的类库，但你必须理解栈在“底层”是如何创建的，通常是通过一维数组来实现。

栈指针 (Stack Pointer)

使用数组（其大小是固定的）时，我们需要一个变量，通常称为栈指针 (Stack Pointer, SP) 或栈顶 (Top Of Stack)，来追踪 LIFO 操作（入栈/出栈）应该在哪里发生。

该指针保存了最近添加元素的索引（位置）。

检查栈空或栈满

由于数组具有固定容量，检查边界条件对于防止错误（例如尝试向已满的栈中入栈，即栈溢出，Stack Overflow）至关重要。

• 是否为空？：如果栈指针处于初始位置，则栈为空。如果我们将数组索引定义为从 0 开始，则当栈为空时，指针通常初始化为 -1。如果指针等于空索引，则栈为空。
• 是否已满？：如果栈指针已达到底层数组的最大允许索引，则栈已满。如果数组大小为 N，则最大索引为 \(N-1\)。

让我们跟踪一个最大容量为 5（索引 0 到 4）的栈。
初始状态：栈指针 (SP) = -1。

1. 入栈 A： SP 递增至 0。A 存储在索引 0 处。
2. 入栈 B： SP 递增至 1。B 存储在索引 1 处。
3. 入栈 C： SP 递增至 2。C 存储在索引 2 处。
4. (栈数组：[A, B, C, _, _]。SP = 2)
5. 出栈： 获取索引 2 处的项 (C)。SP 递减至 1。
6. (栈数组：[A, B, _, _, _]。SP = 1)
7. 查看： 获取索引 1 处的项 (B)。SP 保持为 1。

实现的关键总结

通过数组实现栈需要管理栈指针。入栈 (PUSH) 涉及增加指针并存储数据；出栈 (POP) 涉及检索数据并减少指针。必须进行关键检查，以确保指针不会低于最小索引（空栈）或高于最大索引（满栈）。

4. 栈在计算机科学中的应用

栈不仅仅是理论知识；它们是许多关键计算过程的基础构建模块。你必须能够描述在哪些情况下栈是合适的数据结构。

A. 子程序调用栈（最重要的用途！）

当程序执行时，系统使用栈（调用栈，Call Stack）来管理函数/子程序调用。

• 当子程序 A 调用子程序 B 时，系统必须记住 B 完成后返回 A 的位置。这些信息（返回地址），连同任何参数和局部变量（统称为栈帧，Stack Frame），会被入栈 (Push) 到调用栈中。（这直接关联到课程大纲的 3.1.2.7 部分！）
• 当子程序 B 完成后，它的栈帧会被出栈 (Pop)，程序利用存储的返回地址跳回到 A 中的正确位置。

这种 LIFO 过程确保了嵌套的子程序能够以它们被调用顺序的相反顺序完成。

B. “撤销” (Undo) 功能

在文字处理器（如 Microsoft Word）或图形编辑器（如 Photoshop）中，“撤销”功能依赖于栈。

• 你执行的每一个动作（输入、绘图、删除）都会被入栈 (Push) 到撤销栈中。
• 当你按下“撤销”时，最后添加的动作会从栈中出栈 (Pop) 并执行撤销操作。

C. 表达式求值

编译器和解释器使用栈来转换和计算数学表达式，特别是在处理后缀表达式（逆波兰表示法）或前缀表达式等不同格式时。操作数（数字）通常被入栈，当遇到运算符时，必要的操作数会被出栈，进行计算，并将结果重新入栈。

你知道吗？

术语“栈溢出 (Stack Overflow)”，常作为错误消息出现，或者作为著名编程网站的名字，指的是当计算机的内部调用栈因调用过多函数而没有及时返回（通常是由于编写糟糕的、没有基准条件的递归代码）导致内存耗尽时所发生的情况！

请继续练习这些概念，可以通过手动模拟栈操作或使用编程语言的库实现来加深理解！