堆栈操作

堆栈 (Stack) 是一种后进先出 (LIFO) 或先进后出 (FILO) 的数据结构，在计算机硬件中有两种主要的实现方式。

硬件实现方式

硬堆栈 (寄存器堆栈)

• 实现：使用一组专用的寄存器构成。
• 特点：
  • 栈顶位置固定（通常指向寄存器 0）。
  • 寄存器之间具有自动推移功能（如移位寄存器）。
  • 优点：处理速度极快。 重点
  • 缺点：存储空间有限，超出容量会导致数据丢失。

软堆栈 (存储器堆栈)

• 实现：在主存空间中划出一段区域进行管理。
• 特点：
  • 栈底固定，栈顶动态变化。
  • 使用 栈指针 (SP) 指向栈顶。
  • 优点：空间大，不易丢失数据。 重点
  • 缺点：速度慢于硬堆栈（需访存）。

栈指针 (SP)

• 指向规则：教材中通常约定 SP 指向存有数据的栈顶单元（满栈），而非空单元。 重点
• 生成方向： 注意：本课程（蒋本珊教材）对于生成方向的命名可能与部分资料不同，请以操作逻辑为准。
  • 自底向上生成（本课程定义）：栈底在高地址，栈顶向低地址增长。
    • 入栈 (Push)：先 $SP\leftarrow SP-1$，再写入数据。
    • 出栈 (Pop)：先读出数据，再 $SP\leftarrow SP+1$。
    • 示例：若当前 $SP=2000H$，执行 push 操作后，$SP$ 变为 $1FFFH$。
  • 自底向下生成：栈底在低地址，栈顶向高地址增长。
    • 入栈：先 $SP\leftarrow SP+1$，再写入数据。
    • 出栈：先读出数据，再 $SP\leftarrow SP-1$。

堆栈指令应用实例

堆栈常配合 零地址指令 使用。例如计算 $Z=A\times B+C$：

1. PUSH A：将 A 压入栈顶。
2. PUSH B：将 B 压入栈顶。
3. MUL：弹出栈顶两个元素 (A, B)，计算 $A\times B$，将结果压回栈顶。
4. PUSH C：将 C 压入栈顶。
5. ADD：弹出栈顶两个元素 (Product, C)，计算和，将结果压回栈顶。
6. POP Z：将栈顶结果弹出并存入 Z。

• 访存分析：
  • PUSH/POP 指令通常需访存 3次（取指 + 读/写数据? 实际上可能是取指+读指令+写数据? 或者是取指+读操作数+写堆栈? Transcript says “缓存三次” → likely Fetch Instruction, Read Operand, Write Stack）。
  • 算术逻辑指令（如 ADD 零地址）需访存 4次（取指 + 读栈顶1 + 读栈顶2 + 写回栈顶）。