Stacks

堆栈 (Stack) 简介

欢迎！在本章中，我们将探讨计算机科学中最基础且使用最频繁的数据结构之一：堆栈 (Stack)。堆栈在追踪任务、反转数据，甚至是协助计算机执行子程序（subroutine）方面都非常有用。读完这些笔记后，你将会明白它们的运作原理、如何使用它们，以及为什么它们对于你的 AQA A Level 考试如此重要。

如果数据结构起初看起来有点抽象，不用担心——我们会用大量的日常例子来让你清楚理解！

什么是堆栈？

堆栈是一种抽象数据类型 (Abstract Data Type, ADT)。这意味着它是一个关于数据应如何组织和存取的概念模型。它遵循一条非常明确的规则，称为 LIFO，即 后进先出 (Last-In, First-Out)。

类比：想象一个自助餐厅的托盘堆。
1. 你把一个新托盘放到这堆东西的最顶端。
2. 如果你想拿一个托盘，你只能拿最顶端的那一个。
3. 第一个放下的托盘（最底部的那个）必须等到它上面所有的托盘都被移走后，才能被取走。

关键术语：LIFO

在堆栈中，你添加的最后一个项目，就是你必须移除的第一个项目。你永远只能与堆栈的「顶端」进行互动。

快速回顾：LIFO 规则

• Last In (后进)
• First Out (先出)
• 把它想象成一罐品客薯片——工厂最后放进去的薯片，就是你第一个吃到的！

基本的堆栈运算

根据你的课程大纲，你需要确切知道如何描述和应用这五种运算：

1. Push (推入)

Push 运算会将新项目添加到堆栈的顶端。
步骤如下：
1. 检查堆栈是否已满（以避免堆栈溢出 Stack Overflow）。
2. 增加顶端指针 (top pointer)（将其向上移动一个位置）。
3. 将新数据插入该位置。

2. Pop (弹出)

Pop 运算会从堆栈的顶端移除该项目，并通常会回传其值。
步骤如下：
1. 检查堆栈是否为空（以避免堆栈下溢 Stack Underflow）。
2. 存取目前顶端指针处的数据。
3. 减少顶端指针（将其向下移动一个位置）。

3. Peek (查看) 或 Top

Peek 运算会回传顶端元素的值但不会将其移除。就像看一眼最上面的托盘是什么颜色，而不用把它拿起来一样。

4. Test for Empty Stack (isEmpty)

这会检查堆栈中是否有任何项目。如果顶端指针处于起始位置（根据实现方式通常为 -1 或 0），则堆栈为空 (empty)。

5. Test for Stack Full (isFull)

如果堆栈是使用固定大小的数组（静态数据结构）来实现的，它可能会空间不足。此运算会检查顶端指针是否已达到最大容量。

重点总结

Push 用于添加，Pop 用于移除，Peek 用于查看。在 Push 之前务必检查堆栈是否已满 (Full)，在 Pop 之前检查是否为空 (Empty)！

实现：内存中的运作方式

在考试中，你可能会被问到堆栈实际上是如何构建的。最常见的情况是，堆栈是使用数组 (array) 和顶端指针 (top pointer) 来实现的。

• 数组 (Array)：存储数据的连续内存位置。
• 顶端指针 (Top Pointer)：存储目前顶端元素索引（位置）的变量。

你知道吗？
当我们在 Pop 运算中「移除」一个项目时，数据并不会立即从内存中删除。我们只是简单地将顶端指针向下移动。计算机会将该「弹出」的空间视为空白，尽管旧的位（bits）仍然存在，直到它们被新的 Push 运算覆盖为止！

常见错误

• 指针位置：有些程序员将顶端指针设定在 \( -1 \)（表示堆栈为空），而有些则从 \( 0 \) 开始。请务必仔细阅读考试题目，看看它是如何定义「空」的。
• 运算顺序：Push 时，你必须在添加数据之前增加指针。而 Pop 时，你通常在减少指针之前获取数据。

堆栈的实际应用

堆栈不仅存在于教科书中；它们几乎被用于你使用的每一款软件中！

1. 撤销 (Undo) 按钮

每次你在文字处理软件中输入一个字母，它都会被 Push 到一个堆栈中。当你按下「撤销」时，计算机会从堆栈中 Pop 出最后的操作来将其撤销。

2. 浏览器中的「返回」按钮

当您浏览网站时，每个网址（URL）都会被 Push 到一个堆栈中。当你点击「返回」时，目前的页面会从堆栈中 Pop 出，显示出前一个页面。

3. 子程序调用 (堆栈帧 Stack Frames)

这是 AQA 课程大纲（4.1.1.15 节）的一个特定部分。当程序调用一个函数（子程序）时，它会使用堆栈帧 (stack frame) 来存储：
• 返回地址 (Return addresses)：函数结束后要返回哪里。
• 参数 (Parameters)：传递给函数的数据。
• 区域变量 (Local variables)：仅在该函数内部存在的变量。

4. 逆波兰表示法 (Reverse Polish Notation, RPN)

堆栈被用于评估 RPN 中的数学表达式（4.3.3.1 节）。例如，\( 3 + 4 \) 写作 \( 3 \ 4 \ + \)。计算机将 3 和 4 Push 到堆栈中，然后当它看到 \( + \) 时，它会将两者 Pop 出来，将它们相加，然后将结果再 Push 回堆栈。

快速回顾：堆栈的用途

• 回溯 (Backtracking)（撤销/返回按钮）
• 函数调用（递归和堆栈帧）
• 反转数据
• 表达式评估 (RPN)

摘要表

运算 | 说明
Push | 将项目添加到顶端。增加指针。
Pop | 移除并回传顶端项目。减少指针。
Peek | 回传顶端项目但不移除它。
isEmpty | 如果堆栈中没有项目，回传 True。
isFull | 如果静态堆栈达到最大容量，回传 True。

考试重点总结

如果你看到关于堆栈的问题，请记住 LIFO。永远要检查溢出 (Overflow)（向已满的堆栈 Push）和下溢 (Underflow)（从空的堆栈 Pop）。如果你能描述这些运算并画出一个带有移动指针的简单数组，那么你离获得高分就不远了！