Stacks

欢迎来到堆栈（Stack）的世界！

你好！今天，我们要探索程序员工具箱中最基础且实用的工具之一：堆栈（Stack）。这种数据结构属于你 Oxford AQA 课程大纲中「基础数据结构」的部分。

你可以把堆栈想象成现实生活中餐厅里的餐盘堆，或是叠在一起的书本。如果你在最上面放了一本新书，这本书就是你必须先取走，才能拿到下面其他书的第一本书。这听起来很简单，但这个概念能帮助计算机管理从「撤销（Undo）」按钮到复杂数学计算等所有事务！

什么是堆栈？

堆栈是一种线性数据结构，它遵循一条非常明确的规则，称为 LIFO。
LIFO 代表 后进先出（Last-In, First-Out）。

想象一个糖果分配器（Pez dispenser）。你最后放进顶部的糖果，就是你使用时最先弹出来的那一颗。这正是计算机科学中堆栈的运作方式：最后加入的项目，就是最先被移除的项目。

需要记住的关键术语：

• LIFO：后进先出。这是堆栈的核心规则。
• 静态数据结构：如果我们使用数组（Array）来实现堆栈，它会有一个固定大小，在程序执行期间无法改变。
• 动态数据结构：如果堆栈的大小可以随需求增加或减少，它就被视为动态的。

快速复习：为什么它被称为 LIFO？因为最后（Last）进去的项目，就是最先（First）离开的！

标准堆栈操作

为了使用堆栈，我们主要会用到三种「动作」或操作。如果这些名字听起来很高级，别担心；它们只是计算机的简单指令而已。

1. 推入 (Push)

Push 操作会在堆栈的顶端加入一个新项目。
比喻：将一个新盘子放到一叠餐盘的最上方。

2. 弹出 (Pop)

Pop 操作会移除目前位于堆栈顶端的项目。
比喻：从那一叠盘子中取走最上方的那一个来使用。

3. 查看 (Peek / Top)

Peek 操作让你查看位于堆栈顶端项目的值，但不会将其移除。
比喻：看一眼堆栈中最上方那本书的封面，而不把它拿起来。

常见错误：学生经常误以为 pop 只是查看项目。请记住：pop 会将项目移除；而 peek 只是看一眼！

关键总结：使用 push 来新增，pop 来移除，以及 peek 来查看顶端内容。

如何使用数组实现堆栈

在考试中，你需要了解如何使用一维数组来建立堆栈。

为了追踪我们目前的位置，我们使用一个特殊的变量，称为顶端指针（Top Pointer）。这个指针会储存目前堆栈顶端项目的索引（即位置编号）。

步骤拆解：新增项目 (Pushing)

1. 检查堆栈是否已满（以避免发生「堆栈溢出 Stack Overflow」）。
2. 将顶端指针加 1：\( top = top + 1 \)。
3. 将新项目插入到数组中新的 \( top \) 位置。

步骤拆解：移除项目 (Popping)

1. 检查堆栈是否为空（以避免发生「堆栈下溢 Stack Underflow」）。
2. 读取或传回目前 \( top \) 位置的项目。
3. 将顶端指针减 1：\( top = top - 1 \)。

检查「已满」或「为空」

• 空堆栈：通常，顶端指针会被设定为 \( -1 \)（或 \( 0 \)，取决于起始索引），以表示目前尚无项目。
• 满堆栈：如果顶端指针等于数组的最大容量，则堆栈已满。此时尝试 push 更多数据会导致堆栈溢出 (Stack Overflow) 错误！

关键总结：基于数组的堆栈使用顶端指针来进行操作。在 push 前务必检查是否已满，在 pop 前务必检查是否为空！

堆栈有什么用途？

计算机非常爱用堆栈！以下是堆栈成为绝佳工具的几个真实世界场景：

• 「撤销 (Undo)」按钮：你的文字处理软件会保留一份你所做过的每一次变更的堆栈。当你按下撤销时，它会并将最后一次变更从顶端「弹出 (pop)」，让你回到过去的操作状态。
• 网页浏览器记录：当 the 你按下「上一页」按钮时，浏览器会将你最后浏览的网址从堆栈中弹出。
• 子程序调用 (Stack Frames)：这对你的课程大纲来说是一个非常重要的概念！当程序调用子程序（函数）时，它会使用堆栈框架 (Stack Frame) 来储存：
    1. 返回地址 (Return address)（函数结束时要返回哪里）。
    2. 参数 (Parameters)（传入函数的数据）。
    3. 局部变量 (Local variables)（仅在函数内部使用的数据）。

你知道吗？如果递归函数无穷无尽地执行导致计算机「崩溃」，通常是因为这些堆栈框架占满了内存——这正是知名网站「Stack Overflow」名称的由来！

总结检查清单

在结束之前，请确保你能回答以下问题：
• 我能解释 LIFO 是什么意思吗？（后进先出）
• 我知道 push、pop 和 peek 之间的差别吗？
• 我能描述顶端指针在 push 或 pop 期间如何变化吗？
• 我了解什么是堆栈溢出 (Stack Overflow) 和堆栈下溢 (Stack Underflow) 吗？
• 我能列举两到三个堆栈的真实应用吗？

如果觉得内容很多也不用担心！只要记住「餐盘堆」的比喻，其他的概念就会慢慢融会贯通。你一定没问题的！