波仔
⚙️ 第四章 让内存化方为圆
📄 一句话概括

栈是后进先出（同一头进出），队列是先进先出（一头进一头出）；环形缓冲区是长度定死的队列，写满了回头从头上写。

📝 本节和前面几节的关系

4.4 有了数组这个地基，这一节看它在【进出顺序】上能摆出什么花样。

一、栈：后进先出

栈的规矩是同一头进出：最后压进去的，最先弹出来（LIFO）。 生活里的对应一抓一大把：叠盘子、弹夹、走进死胡同再原路退出来。 程序里更常见：函数调用就靠栈——return 弹的是最后一次 call 压下的返回地址。 别的用途还有撤销操作、括号匹配、表达式求值——它们的共同点是【必须先处理最近的】。

二、队列：先进先出

队列的规矩是一头进、另一头出：最先进去的，最先出来（FIFO）。 生活里就是排队：买票、打印任务、消息排队。 程序里也常见：消息队列、广度优先搜索、缓冲外设发来的数据。 栈和队列的差别只有一句话：从哪一头进出。 可这一句话就决定了它们能解决什么问题。

三、环形缓冲区：定长、转圈、不搬

队列有个麻烦：出队之后，后面的元素要不要往前挪？ 挪——每次出队都要搬一大串，太贵。不挪——前面的空位越攒越多，白浪费。 环形缓冲区的办法是两头相接：写指针走到底就回头从 0 号开始写，读指针跟在后面追。 于是既不用搬数据，也不浪费空间——只要缓冲区长度定死就行。

四、为什么偏偏要【定长】

因为出现这些场景的地方，内存往往很紧张，而且不允许临时申请和释放。 音视频流、串口数据、日志缓冲——数据是连续不断来的，攒多了就必须丢掉最老的。 定长还有个好处：永远不会有【申请不到内存】这种事，实时系统最喜欢这一点。 所以它不是偷懒的做法，是为【持续、稳定、可预期】这几个字专门设计的。

五、动手 Demo：栈、队列，以及环形缓冲区

三种容器，差别只在【从哪一头进出】。 环形缓冲区还要多一条规矩：长度定死，写满了就挤掉最老的。

from collections import deque
st = deque()
for x in (1, 2, 3):
    st.append(x)
print("栈：", list(st), "弹出", st.pop())
ring = deque(maxlen=4)
for x in range(1, 8):
    ring.append(x)
print("环形缓冲区：", list(ring))

实跑输出：

--------------------------------------------------------------------
栈、队列，以及环形缓冲区
--------------------------------------------------------------------

三种容器，差别只在【从哪一头进出】：

  容器           进出规则                           日常对应
  -------------------------------------------------------------------
  栈             后进先出（LIFO）：同一头进出       函数调用、撤销
  队列           先进先出（FIFO）：一头进一头出     打印排队、消息
  环形缓冲区     定长，写满就回头从头上写           缓冲区、音视频流

  栈：压入 1、2、3 之后——
    当前栈：[1, 2, 3]
    弹出的第一个是 3（最后进来的先走）
    再弹一个    是 2

  队列：依次排入 1、2、3 之后——
    当前队列：[1, 2, 3]
    离开的第一个是 1（最先进来的先走）
    再离开一个  是 2

  环形缓冲区：长度只有 4，塞第 5 个时把最老的那个挤掉——

    放入 1 后：[1]
    放入 2 后：[1, 2]
    放入 3 后：[1, 2, 3]
    放入 4 后：[1, 2, 3, 4]
    放入 5 后：[2, 3, 4, 5]
    放入 6 后：[3, 4, 5, 6]
    放入 7 后：[4, 5, 6, 7]

  **它不用搬数据，写指针转圈走就行**——处理连续不断的音视频流就靠这个。

栈弹 3 再弹 2（后进先出）；队列离开的是 1 再是 2（先进先出）。 环形缓冲区长度只有 4，塞到第 7 个时里面只剩 4、5、6、7——老数据自动被挤掉。

30 秒实验

  1. 用一叠纸或几本书实际做一遍栈的【压入】和【弹出】，感受后进先出。
  2. 想想浏览器的【后退】按钮是栈还是队列，为什么。

常见误区

  1. 把栈和队列记混。栈是同一头进出，队列是一头进一头出。
  2. 以为环形缓冲区可以随便变大。定长是它的前提，一变就不是它了。
自测三问（点开对答案） 1. 栈和队列的规则分别是什么？ —— 栈后进先出（同一头进出）；队列先进先出（一头进另一头出）。 2. 环形缓冲区解决了什么问题？ —— 队列出队后要不要搬数据的两难——两头相接，既不用搬也不浪费。 3. 为什么这些场合要用定长缓冲？ —— 内存紧张、数据持续到来，不允许临时申请释放，且要能自动丢掉最老的数据。

相关笔记