波仔
💻 第六章 与数据结构成为好朋友的七个要点
📄 一句话概括

栈＝一个口进出、后进先出（push/pop）；队列＝两头进出、先进先出（入队/出队）——第四章的中断现场和打印任务全是它们。

📝 本节和前面几节的关系

四件套认全了，这一节把最常用的两件（栈、队列）拆开看实现，并回认第四章里的老朋友。

一、栈：一个口的塔

只有两个动作：push（压入，放塔顶）、pop（弹出，取塔顶）——进出同一个口。 规矩自然形成：最后放上去的最先被拿走——后进先出 LIFO。 回认老朋友：4.6 节中断保存现场用的就是栈（嵌套中断后进先出，正好配对）；函数调用也是栈（调谁压谁，返回弹谁）。

二、队列：两头开的管道

两个动作：入队（从队尾进）、出队（从队头出）——两头分工。 规矩：先来的先走——先进先出 FIFO。 回认老朋友：打印机排队、消息队列、操作系统调度——凡是【讲究先来后到】的场合都是它。

三、实现思路：数组就够

栈用数组实现最简单：留一个【栈顶下标】，push 就往那写、pop 就从那读——一动一下标。 队列用数组要两个下标（头、尾），或用环形数组（走到头绕回起点）避免空间浪费。 看，实现数据结构用的还是数组——【数据结构】是概念，【数组】是砖头。

四、动手 Demo：栈与队列的进进出出

模拟三个元素进栈出栈、三个人入队出队，看次序差别。

# 栈: 后进先出
stack = []
stack.append("A"); stack.append("B"); stack.append("C")
print("栈弹出顺序:", stack.pop(), stack.pop(), stack.pop())
# 队列: 先进先出
from collections import deque
q = deque(["甲", "乙", "丙"])
print("队列出队顺序:", q.popleft(), q.popleft(), q.popleft())

实跑输出：

--------------------------------------------------------------------
要点 5——栈和队列的实现方法
--------------------------------------------------------------------

[栈] 只有 push(进) 和 pop(出)，进出都在同一个口：
    push A -> 栈里(底->顶): ['A']
    push B -> 栈里(底->顶): ['A', 'B']
    push C -> 栈里(底->顶): ['A', 'B', 'C']
    pop C -> 弹出! 栈里剩: ['A', 'B']
    pop B -> 弹出! 栈里剩: ['A']
    pop A -> 弹出! 栈里剩: []

[队列] enqueue(入队) 在尾, dequeue(出队) 在头:
    甲 入队 -> 队伍: ['甲']
    乙 入队 -> 队伍: ['甲', '乙']
    丙 入队 -> 队伍: ['甲', '乙', '丙']
    甲 出队 -> 队伍剩: ['乙', '丙']
    乙 出队 -> 队伍剩: ['丙']
    丙 出队 -> 队伍剩: []

  对比     栈                           队列
  --------------------------------------------------------
  口子     一个口进出                   一头进另一头出
  次序     后进先出                     先进先出
  应用     撤销/函数调用/浏览器后退     打印队列/消息队列

第四章的中断（4.6）用栈保存现场——后进先出正好配嵌套。

同样的 ABC，栈弹出 CBA、队列弹出 ABC——一次实验记住两种次序。 栈溢出（Stack Overflow）＝压得太狠塔太高超出预留内存——那个著名程序员网站的 name 由来。

30 秒实验

  1. 连续按三次【撤销】，想清楚这是栈在弹三次。
  2. 打印三个文档再取消第二个——想想队列能实现【取消中间】吗？（要额外手段）

常见误区

  1. 以为栈是【随便取】——只能取塔顶，中间的够不着。
  2. 以为队列能插队——标准队列只有队尾进队头出，插队是别的结构的事。
自测三问（点开对答案） 1. 栈的两个动作与次序？ —— push 压入、pop 弹出，同一个口，后进先出。 2. 队列的两个动作与次序？ —— 队尾入队、队头出队，先进先出。 3. 哪些场景各用栈与队列？ —— 撤销、函数调用、中断现场用栈；打印、消息、排队用队列。

相关笔记