3.3 堆栈与堆栈操作

本节介绍一种特殊的数据结构——堆栈，及其在计算机体系结构中的实现和应用。

3.3.1 堆栈结构

• 定义: 堆栈是一种按特定顺序进行存取的存储区，其遵循后进先出 (LIFO, Last-In First-Out) 的原则。

• 基本操作:

  • 进栈 (PUSH): 将数据存入堆栈。
  • 出栈 (POP): 从堆栈中取出数据。

• 堆栈指针 (Stack Pointer, SP): 一个专门的寄存器，始终指向栈顶。

• 堆栈的实现方式:

  1. 硬堆栈 (寄存器堆栈)：用一组专门的寄存器实现。
     • 优点: 速度极快。
     • 缺点: 容量受限，成本高。
  2. 软堆栈 (存储器堆栈)：在主存中划出一块区域作为堆栈。
     • 优点: 容量大，灵活。
     • 缺点: 速度较慢，因为每次操作都需要访问主存。
     • 这是现代计算机最常用的方式。

• 堆栈的生长方向:

  • 向上生长 (向高地址方向): 进栈时SP增加，出栈时SP减少。
  • 向下生长 (向低地址方向): 进栈时SP减少，出栈时SP增加。（更为常见）

3.3.2 堆栈操作

• 进栈 (PUSH A):

  1. SP - 1 -> SP （栈指针先移动，假设向下生长）
  2. (A) -> (SP) （数据存入新的栈顶单元）

• 出栈 (POP A):

  1. ((SP)) -> A （从栈顶单元取出数据）
  2. SP + 1 -> SP （栈指针后移动）

• 堆栈的应用:

  • 零地址指令运算: 算术和逻辑运算的两个操作数默认从栈顶弹出，运算结果压回栈顶。
  • 子程序调用和返回: 保存返回地址、传递参数、保存现场（寄存器状态）。
  • 中断处理: 保存断点和现场信息。

零地址指令与堆栈运算

零地址指令系统的操作数都隐含地存在堆栈中，运算时按如下步骤进行：

1. 弹出两个操作数
2. 进行运算
3. 将结果压入栈顶

表达式求值示例

以表达式 (A + B) * C 为例：

1. 中缀表达式转后缀表达式: (A + B) * C → A B + C *
2. 零地址指令序列:

   PUSH A    ; A入栈
   PUSH B    ; B入栈
   ADD       ; 弹出B和A，计算A+B，结果入栈
   PUSH C    ; C入栈
   MUL       ; 弹出C和(A+B)，计算(A+B)*C，结果入栈

堆栈在子程序调用中的应用

子程序调用过程

1. 调用前: 主程序将参数压入堆栈
2. 调用时: CALL指令将返回地址压入堆栈，跳转到子程序
3. 子程序入口: 保存寄存器状态（现场保护）
4. 子程序执行: 从堆栈获取参数，执行功能
5. 子程序出口: 恢复寄存器状态（现场恢复）
6. 返回: RET指令从堆栈弹出返回地址，跳转回主程序

堆栈帧结构

高地址 ←─── SP (栈顶)
├─ 局部变量
├─ 保存的寄存器
├─ 返回地址
├─ 参数n
├─ ...
├─ 参数1
└─ 参数0
低地址

易考点和难点

易考点

• 理解LIFO原则以及PUSH和POP操作如何改变堆栈指针SP
• 堆栈在子程序调用和中断处理中的作用，特别是如何保存和恢复现场（断点PC、寄存器内容）

核心考点

• 堆栈的生长方向对SP变化的影响
• 零地址指令的执行过程和堆栈状态变化

难点

• 结合零地址指令，将一个中缀表达式（如 (A+B)*C）转换为后缀表达式（逆波兰式 A B + C *），并用堆栈指令序列来实现计算。这是对堆栈理解深度的考验。
• 复杂表达式的堆栈求值过程，需要跟踪每一步的堆栈状态变化。