想象你是餐厅后厨的总管。洗好的盘子被一只只摞在餐盘架上——新洗的盘子总是压在旧盘子上面，取用时却必须从最上面那一只开始拿。这就是「后进先出」。而取餐窗口的顾客们排成一条长队——先到的人先拿到餐食，没人能插队到最前面，这就是「先进先出」。这两种看似简单的规则，正是计算机世界里最基础、最强大的两种数据结构：栈（Stack）与队列（Queue）。后厨的餐盘架管理着每道菜的出品顺序，计算机的栈与队列则管理着每一段程序、每一个任务、每一份数据的流转节奏。从函数调用到浏览器回退，从打印任务到外卖派单，从AI请求排队到GPU算力调度，处处都是它们的身影。今天，我们就用这家「数字餐厅」的视角，把栈与队列的原理、实现、应用一次看透。

岗位关联

理解栈与队列是掌握一切算法大厦的基石。对AI从业者而言，无论是训练数据的流水线调度、推理服务的请求排队，还是Transformer中层层嵌套的计算追踪，本质上都是在驾驭这两种「顺序的艺术」。

目录
  1. 可视化演示
  2. 栈的原理：一摞刚洗好的餐盘
  3. 栈的应用：大厨的进阶菜谱
  4. 队列的原理：取餐窗口前的那条长队
  5. 顺序与链式：固定窗口与接龙队伍
  6. 循环队列：旋转寿司台的智慧
  7. 队列的应用：传菜流水线与叫号系统
  8. 双端与单调：贵宾通道与精英筛选
  9. 优先队列：急诊室的叫号系统
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示栈LIFO压栈弹栈操作与函数调用栈映射、队列FIFO入队出队与循环队列环形空间复用、优先队列最小堆结构与堆顶出队过程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

栈的后进先出(LIFO)模型 PUSH压入栈顶，POP弹出栈顶元素 函数调用栈：f3→f2→f1→main层级展开 push: stack[++top]=x; pop: return stack[top--]; O(1) 栈顶唯一操作端，push/pop均为O(1)，递归调用天然使用栈结构。

栈的原理：一摞刚洗好的餐盘

后厨的餐盘架前，洗碗工小张把洗好的盘子一只只往架上摞。他只会把新盘子放在最上面，取用时也只能从最上面拿——最底下那只「陈年餐盘」要等到上面所有盘子都用完才重见天日。这就是「后进先出」（Last In First Out, LIFO）。计算机里的栈就是这样一个餐盘架：只允许在一端（栈顶）放入或取出元素，另一端（栈底）被牢牢封死。

栈的极简规则带来极高的效率。数组实现时，我们只需维护一个 top 指针指向栈顶位置。「入栈」（push）把新元素写到 top 处并让指针向上移动一格，「出栈」（pop）则把指针向下移动一格并返回刚才指向的元素。无论是入栈还是出栈，都只触碰数组的一个位置，不需要移动其他任何元素——这正是栈的灵魂：专一而快速。

出栈操作则反向执行：先把 top 减一，再返回 data[top]。判断栈空只需检查 top == 0，判断栈满则检查 top == capacity。餐盘架的弹簧把每一只新盘子托到最顶，同样地，每一次入栈都把新元素托到「栈顶」这个唯一的入口。

push(x): data[top]=x,top←top+1\displaystyle \text{push}(x):\ \text{data}[\text{top}] = x,\quad \text{top} \leftarrow \text{top} + 1
入栈就是「把菜放到最上面的空位，并让标记指到新的最上面」。
  1. 定位栈顶位置data[top] 是数组中以 top 为下标的位置，也就是当前最顶上的空位。
    data[top]\text{data}[\text{top}]
  2. 写入新元素把 x 放到这个栈顶位置，相当于把新盘子摞到最上面。
    data[top]=x\text{data}[\text{top}] = x
  3. 移动栈顶指针top 加一，让它指向下一个空位，随时准备迎接下一个元素。
    top←top+1\text{top} \leftarrow \text{top} + 1

栈的应用：大厨的进阶菜谱

主厨王师傅要挑战一道「佛跳墙」，步骤多达十几步。他不会一股脑全部记在脑子里，而是把「做完这道菜要回到哪个步骤」写成一张张便签摞在灶台边。做到第5步需要去备料，就把「回到第5步」压到便签堆最上面；备料完成，取走最上面的便签，回到第5步继续。每层嵌套的步骤，恰好构成一个后进先出的小山——这正是计算机中函数调用栈的工作原理。程序调用函数 A，A 又调用 B，B 再调用 C，每个函数的信息像便签一样压栈；C 执行完返回 B，B 返回 A，逐层弹出。

这个机制最经典的应用之一是括号匹配。编译器检查 ([{}]) 是否合法时，遇到左括号就入栈，遇到右括号就弹出栈顶并检查是否配对。遍历结束时若栈为空，说明所有括号都找到了自己的另一半。

同样基于栈的还有表达式求值：将中缀表达式 3 + 4 × 2 转换为后缀表达式 3 4 2 × + 时，运算符要暂存进栈，等优先级更高的运算符先出栈计算。浏览器里的「后退」按钮也是栈——你访问过的每个页面被依次压栈，点后退就是弹出最近访问的那一页。便签山上的规则，从厨房灶台一路延伸到了整个计算机世界。

Snew={Sold∪{ch},ch 为左括号，入栈Sold∖{栈顶},ch 为右括号且与栈顶配对\displaystyle S_{new} = \begin{cases} S_{old} \cup \{\text{ch}\}, & \text{ch 为左括号，入栈} \\ S_{old} \setminus \{\text{栈顶}\}, & \text{ch 为右括号且与栈顶配对} \end{cases}
左括号进栈「暂存承诺」，右括号出栈「兑现承诺」，最终栈空代表所有承诺都已完成。
  1. 遇到左括号把它压入栈中暂存，等待对应的右括号。
    Sold∪{ch}S_{old} \cup \{\text{ch}\}
  2. 遇到右括号弹出栈顶元素，检查两者是否配对成功。
    Sold∖{栈顶}S_{old} \setminus \{\text{栈顶}\}
  3. 最终判定遍历完整个表达式后，如果栈为空则全部匹配，否则说明有括号「落单」。
    Sfinal=∅S_{final} = \varnothing

队列的原理：取餐窗口前的那条长队

正午十二点，取餐窗口前的队伍排到了门口。每个人都自觉站在队尾，拿到餐的人从队首离开。先来的先服务，后来的耐心等待，这就是「先进先出」（First In First Out, FIFO）。队列正是这条长队的精确建模：新元素从队尾（rear）进入，旧元素从队首（front）离开，绝无插队的可能。

队列用数组实现时，同样只需要两个指针：front 指向队首元素，rear 指向队尾的下一个空位。入队时在 rear 位置写入数据然后 rear++，出队时读取 front 位置的数据然后 front++。两队指针像餐厅的「叫号员」，一前一后地管理着整个队伍。

判断队列空的条件是 front == rear，判断队满则是 rear == capacity。生活中的「排队」无处不在：银行叫号、打印机任务、外卖配送顺序……队列用最简单直接的公平规则，保证了先到先得的确定性。

enqueue(x): data[rear]=x,rear←rear+1\displaystyle \text{enqueue}(x):\ \text{data}[\text{rear}] = x,\quad \text{rear} \leftarrow \text{rear} + 1
入队就是「新顾客站到队尾」，出队就是「队首顾客取餐离开」。
  1. 定位队尾空位data[rear] 是当前队尾的下一个空位。
    data[rear]\text{data}[\text{rear}]
  2. 写入新元素把 x 放到这个位置，新顾客站到队伍最后。
    data[rear]=x\text{data}[\text{rear}] = x
  3. 移动队尾指针rear 加一，队尾向后延伸一个位置。
    rear←rear+1\text{rear} \leftarrow \text{rear} + 1

顺序与链式：固定窗口与接龙队伍

同样是排队，餐厅有两种组织方式。一种是「固定窗口」：划好一片连续区域，每个位置固定编号，顾客按号码依次往前站（数组实现）。另一种是「接龙队伍」：每位顾客只知道自己后面是谁，整个队伍由一个个「节点 + 指针」串联而成（链表实现）。

数组实现的最大优势是随机访问——你知道第3个位置是谁，直接一步走到那里，复杂度 O(1)。但它的弱点是空间固定：队伍太长时只能整体搬迁到更大的区域（动态扩容），搬迁时要复制所有元素，开销不小。链表实现则没有这个烦恼：新的顾客来了，只需让最后一位顾客的指针指向新节点，队伍随时可以无限延长。但链表无法「一步跳到位」，想找第3个人必须从队首一个个数过去。

实际工程中两者各有拥趸：底层队列常用数组追求吞吐量，而需要频繁插入删除的场合则偏爱链表。固定窗口与接龙队伍各有各的节奏，关键看你的餐厅更在意哪种体验。

Sarray=n×size,Slink=n×(size+ptr)\displaystyle S_{\text{array}} = n \times \text{size},\qquad S_{\text{link}} = n \times (\text{size} + \text{ptr})
数组省掉指针的空间但扩容昂贵，链表灵活自由却要额外存放指针。
  1. 数组空间n 个元素紧密排列，每个占 size 字节，总空间为 n × size。
    n×sizen \times \text{size}
  2. 链表空间每个节点除了元素本身，还要一个指针字段（4或8字节），总空间为 n × (size + ptr)。
    n×(size+ptr)n \times (\text{size} + \text{ptr})
  3. 取舍权衡数组更省空间且缓存友好，链表更灵活但内存开销大。
    array≪link (空间上),array≫link (扩容上)\text{array} \ll \text{link}\ (\text{空间上}),\quad \text{array} \gg \text{link}\ (\text{扩容上})

循环队列：旋转寿司台的智慧

固定窗口式队列有个尴尬的问题：顾客取餐离开后，front 前面的位置就空了出来，但 rear 已经走到了数组末尾——明明前面有空位，新顾客却排不进来。这就是「假溢出」。聪明的餐厅老板改造了布局：把直线队伍弯成一个旋转寿司台。寿司盘转完一圈回到原点继续使用，座位不再分首尾，而是一个环形。

计算机里的解决方案同样优雅：用「取模运算」让 front 和 rear 指针在到达数组末尾后自动绕回开头。(rear + 1) % capacity 使得指针在 0 到 capacity-1 之间循环移动。这样一来，数组的空间被真正循环复用，不再有「前面空着却进不来」的悲剧。

旋转寿司台让每一寸空间都被反复使用，「假溢出」彻底消失。这个设计在操作系统缓冲区、网络数据包队列、音频流播放等场景中无处不在——循环数组是工程中最经典的「空间复用」智慧。

(rear+1) mod capacity=front⇒队列已满\displaystyle (rear + 1) \bmod capacity = front \quad \Rightarrow \quad \text{队列已满}
队尾指针向前绕一圈后追上队首，说明整圈都站满了人。
  1. 取模绕回(rear + 1) % capacity 让队尾指针加一后在数组范围内循环。
    (rear+1) mod capacity(rear + 1) \bmod capacity
  2. 队满条件当绕回的队尾指针等于队首指针时，环形队伍已经转满一圈，无法再入队。
    rear+1≡front(modcapacity)\text{rear} + 1 \equiv \text{front} \pmod{capacity}
  3. 牺牲一格队空条件是 front == rear，为了和队满区分，通常牺牲一个存储单元，让队满时 rear 恰好落后 front 一格。
    rear+1=front≠rearrear + 1 = front \neq rear

队列的应用：传菜流水线与叫号系统

后厨与前厅之间有一条传菜履带：厨师把做好的菜放在履带一端，服务员从另一端取走。履带上的菜按照放上去的顺序到达，谁也不能越过前面那份——这就是队列在生产中的角色：缓冲与解耦。厨房出菜速度和前厅上菜速度不必完全同步，中间的履带吸掉了速度波动。

在计算机系统中，这种「履带」无处不在。操作系统用任务队列管理等待 CPU 的进程，新进程排在队尾，CPU 空闲时从队首取一个执行；分布式系统用消息队列（如 Kafka、RabbitMQ）在服务之间传递数据，生产者只管放，消费者按序取，两边互不阻塞；深度学习的数据加载管线同样如此，DataLoader 用一个多进程队列源源不断地把处理好的数据喂给 GPU，让昂贵的算力永不停歇。

从传菜履带到 AI 推理服务中的请求排队，队列始终是系统「削峰填谷」的定海神针。它让生产者和消费者各干各的，彼此放心。

depth(v)=depth(u)+1,∀(u,v)∈E, u 先出队\displaystyle depth(v) = depth(u) + 1,\quad \forall (u,v) \in E,\ u \text{ 先出队}
广度优先搜索（BFS）中，从起点出发逐层扩展，每一层比上一层深度加一。
  1. 出队取点BFS 从队首取出当前节点 u，表示「这一层正在处理的位置」。
    u=dequeue()u = \text{dequeue}()
  2. 扩展邻居把 u 的所有未访问邻居 v 入队，每个邻居的深度在 u 的基础上加一。
    depth(v)=depth(u)+1depth(v) = depth(u) + 1
  3. 逐层推进队列保证了同一深度的节点先于下一层节点被处理，实现「层层扫描」。
    level1→level2→⋯→levelk\text{level}_1 \to \text{level}_2 \to \cdots \to \text{level}_k

双端与单调：贵宾通道与精英筛选

有的餐厅设置了一条贵宾通道：两头都能进出，VIP 可以从前面直接插队，也可以从后面提前离开。这就是双端队列（deque）。它能从两端插入和删除，是栈和队列的「自由合体」。Python 的 collections.deque 就是它的工业级实现，两端操作都是 O(1)。

双端队列最精彩的应用是单调队列——想象评委筛选「最佳菜品」：候选者排成一队，但规则很残酷——新来的候选者如果比队尾的更强，队尾那个就被当场淘汰（因为他在新候选者离开之前永远不可能是最佳）。这样整条队伍从队首到队尾始终保持「实力递减」的单调性。每轮只需要看一眼队首，就能知道当前窗口的最强者。

单调队列用「弱肉强食」的淘汰策略，把滑动窗口最值问题从 O(nk) 降到 O(n)。这道经典的 LeetCode 题目（滑动窗口最大值），正是每一位算法工程师必须掌握的「精英筛选术」。

T暴力(n,k)=O(nk),T单调队列(n,k)=O(n)\displaystyle T_{\text{暴力}}(n,k) = O(nk),\qquad T_{\text{单调队列}}(n,k) = O(n)
暴力法对每个窗口都重新比较 k 个元素；单调队列让每个元素最多进出队一次，效率碾压。
  1. 暴力复杂度n 个窗口，每个窗口内比较 k 次，总时间 O(nk)。
    O(nk)O(nk)
  2. 单调队列复杂度每个元素最多被入队一次、出队一次，总时间 O(n)。
    O(n)O(n)
  3. 核心思想淘汰掉「永远不可能成为最大值」的弱者，让队首始终是当前窗口的最佳答案。
    每步 O(1)×n 步=O(n)\text{每步 O}(1) \times n \text{ 步} = O(n)

优先队列：急诊室的叫号系统

普通队列讲先来后到，但急诊室不这么干：心跳骤停的病人即使刚进门，也必须排在感冒病人前面。这里的关键不是「到达顺序」，而是「病情优先级」。优先队列（Priority Queue）正是为这种场景而生——出队的元素永远是当前队列中优先级最高（或最低）的那个，而不是最早进来的那个。

优先队列最常见的底层结构是二叉堆（Binary Heap）：一种特殊的完全二叉树，堆顶永远是最大（或最小）元素。插入新元素时把它放到末尾然后向上「上浮」；弹出堆顶后把末尾元素放到堆顶再向下「下沉」。上浮和下沉每步跨越一层，而树的高度是 log n，因此插入和删除的复杂度都是 O(log n)。

基于优先队列的 TopK 问题是海量数据场景的常客：用大小固定的最小堆扫描一遍全量数据，堆里始终保留最大的 K 个，最终堆顶就是第 K 大的元素。从急诊分诊到推荐系统的热门榜单，优先队列让「最重要的事最先被处理」成为一条可计算的规则。

Tinsert(n)=TdeleteTop(n)=O(log⁡n)\displaystyle T_{\text{insert}}(n) = T_{\text{deleteTop}}(n) = O(\log n)
堆就像急诊分诊台：每次叫号都能立刻找到病情最重的病人，靠的是不断上浮、下沉维持秩序。
  1. 插入上浮新元素先放到堆的末尾，然后逐层与父节点比较，必要时交换向上。
    \text{bubbleUp}: \text{child} \leftrightarrow \text{parent},\ \text{直到父 \geq 子}
  2. 弹出下沉删除堆顶后，把末尾元素移到堆顶，再逐层与较大的孩子交换向下。
    \text{sinkDown}: \text{parent} \leftrightarrow \text{largest child},\ \text{直到父 \geq 子}
  3. 对数时间树高为 log n，每步至多跨越一整个树高，因此单次操作 O(log n)。
    log⁡2n\log_2 n

AI 应用场景

GPU推理服务的请求调度

阶段：模型部署与在线推理

解决的问题：大语言模型服务上线后，并发请求像潮水般涌来，GPU 算力却有限。如果直接让每个请求独占 GPU，超载时大量请求会排队超时甚至崩溃。用队列接收所有推理请求，按先进先出的顺序分批喂给 GPU 执行，既保证了请求的公平性，又让 GPU 像传菜履带一样保持满负荷运转，避免「厨师忙死、顾客饿死」的失衡。队列的缓冲作用把尖峰流量平滑成匀速水流，系统稳定性大幅提升。

具体案例：某 AI 公司部署 7B 参数对话模型，使用消息队列（Kafka）接收用户请求，后端消费者按序拉取并组 batch 送入 GPU。高峰期每秒 2000 个请求全部进入队列排队，GPU 利用率从 40% 提升到 85%，超时率从 15% 降到 0.5%。

自动求导中的调用栈追踪

阶段：模型训练与反向传播

解决的问题：训练 Transformer 时，损失函数对每个参数的梯度需要从输出层逐层回传。这种「从后往前」的计算顺序天然是一棵调用树——前向传播每执行一个张量操作，自动求导引擎（如 PyTorch 的 autograd）就把该操作的梯度函数压入栈中；反向传播时从栈顶依次弹出并执行，恰好按照「后计算的操作先求梯度」的 LIFO 顺序完成。如果没有栈，框架就无法记住复杂的嵌套计算路径。

具体案例：训练 GPT 模型时，一个 attention 层包含数十个张量操作，autograd 用调用栈记录每一步的操作与依赖。反向传播时逐层弹出梯度函数，从输出层一路计算到嵌入层，最终完成全部参数更新。这正是栈在 AI 框架底层最核心的工程应用。

Python 演示

python25 行
from collections import deque  def max_sliding_window(nums, k):    """单调队列求解滑动窗口最大值。     队列中保存下标，且对应数值从队首到队尾严格递减。    """    dq = deque()    result = []    for i, num in enumerate(nums):        while dq and nums[dq[-1]] <= num:            dq.pop()        dq.append(i)        if dq[0] <= i - k:            dq.popleft()        if i >= k - 1:            result.append(nums[dq[0]])    return result  if __name__ == "__main__":    nums = [1, 3, -1, -3, 5, 3, 6, 7]    k = 3    print("滑动窗口最大值:", max_sliding_window(nums, k))
目的：用双端队列实现的单调队列，在 O(n) 时间内求出数组每个长度为 k 的滑动窗口的最大值，是 LeetCode 239 题的标准解法。
  1. from collections import deque导入双端队列，两端增删都是 O(1)，这是单调队列的物理基础。
  2. while dq and nums[dq[-1]] <= num:把队尾所有「打不过新元素」的下标全部弹出，维持队列从队首到队尾单调递减。
  3. dq.append(i)当前元素的下标入队，它可能是未来窗口的最大值候选。
  4. if dq[0] <= i - k:队首下标已经滑出窗口范围，果断淘汰。
  5. result.append(nums[dq[0]])窗口形成后（i >= k-1），队首永远是当前窗口的最大值。

常见误区

误区用数组实现队列时，用 front++ 和 rear++ 移动两个指针就万事大吉了，数组前面空出来的位置不用管。

正解指针只增不减会让 front 和 rear 一直向右移动，当 rear 到达数组末尾时，即使 front 前面空着一大片位置，也无法再入队。这就是「假溢出」。真正的解法是循环队列——用取模运算让指针绕回数组开头，把闲置空间循环利用起来，就像旋转寿司台的轨道。

为何常见：一维数组给人「线性走到头」的直觉，容易忽略指针可以折返的设计空间。

误区循环队列中，front == rear 既可以表示队空也可以表示队满，只需要额外用一个变量记录元素个数就行。

正解如果 front == rear 同时代表两种状态，程序无法区分「空无一人的队伍」和「绕了一圈正好站满」的情况。经典的解决方法是牺牲一个存储单元：让队满条件变成 (rear + 1) % capacity == front，此时 rear 始终比 front 落后一格，两种状态彻底分离。用计数器是另一种方案，但要额外维护变量。

为何常见：认为「首尾相遇就是满了」是符合直觉的，却忽略了空队列也会首尾相等。

误区单调队列和优先队列都是能快速找最值的「队列」，本质是同一回事，可以互换使用。

正解两者机制完全不同。单调队列维护的是「窗口内按下标顺序排列、值单调的候选序列」，它只能访问窗口内的最值，且过期元素会自动滑出；优先队列用二叉堆维护的是「全局按优先级排序」的集合，每次出队的是全局最优，但无法处理滑动窗口的「过期」问题。滑动窗口最值用单调队列 O(n)，全局 TopK 用优先队列 O(n log K)。

为何常见：两个名字都带「队列」，又都能求最值，初学者极易混淆其适应场景。

误区Python 的 list 既能 append 又能 pop(0)，这不就是现成的队列吗？

正解list.pop(0) 要从队首删除元素，底层需要把后面所有元素整体前移一位，时间复杂度 O(n)。如果有 n 个元素依次入队出队，总时间会退化到 O(n²)。正确做法是用 collections.deque，它的 popleft() 是真正的 O(1) 操作。

为何常见：Python 的 list 用起来太顺滑了，掩盖了它底层是连续数组、头部删除成本极高的本质。

面试题

Q1. 栈最重要的特性是什么？

单选题 · easy

  • A.先进先出
  • B.后进先出← 正确答案
  • C.支持随机访问
  • D.两端都可以插入删除

答案：B。栈像一摞餐盘，后放上去的盘子总是在最上面，取用时也最先被拿走，这就是「后进先出」（LIFO）。队列才是先进先出，链表才支持灵活插入，双端队列才允许两端操作。

Q2. 以下哪种场景最适合使用队列？

单选题 · easy

  • A.函数调用的返回地址追踪
  • B.括号匹配检查
  • C.打印机任务按提交顺序输出← 正确答案
  • D.浏览器后退按钮

答案：C。打印任务讲究先到先打印，是典型「先进先出」场景，和取餐窗口前排队一模一样。函数调用追踪和浏览器后退都要「回到最近的状态」，属于栈；括号匹配是栈顶的配对验证，也是栈。

Q3. 栈的典型应用场景包括哪些？

多选题 · easy

  • A.函数递归调用← 正确答案
  • B.表达式求值← 正确答案
  • C.消息中间件的广播
  • D.浏览器前进后退← 正确答案

答案：ABD。函数递归调用时每层调用的返回地址压入调用栈，表达式求值的运算符需要暂存到栈中等待优先级处理，浏览器前进后退维护的是一份访问历史栈。消息广播是「一对多」的发布订阅模型，与栈的后进先出无关。

Q4. 对于一个容量为 5 的循环队列，当前 front = 2，rear = 1，队列中的元素个数是多少？

单选题 · mid

  • A.2
  • B.3
  • C.4← 正确答案
  • D.1

答案：C。循环队列元素个数公式为 (rear - front + capacity) % capacity，代入得 (1 - 2 + 5) % 5 = 4。就像旋转寿司台上从 front 位置顺时针数到 rear 位置经过的盘子数，答案是 4 个元素。

Q5. 判断循环队列已满的条件是（capacity 为数组长度）？

单选题 · mid

  • A.front == rear
  • B.rear == capacity - 1
  • C.(rear + 1) % capacity == front← 正确答案
  • D.front == (rear + 1) % capacity == 0

答案：C。为了区分队空（front == rear）和队满，循环队列牺牲一个存储单元。当 rear 再向前走一格就追上 front 时，说明整圈已经站满，即 (rear + 1) % capacity == front。选项 D 包含两个等号嵌套，语法都不成立。

Q6. 关于单调队列，下列说法正确的有？

多选题 · mid

  • A.它可以维护滑动窗口内的最大值← 正确答案
  • B.内部元素从队首到队尾单调递减时可以求窗口最大值← 正确答案
  • C.它利用堆结构保证元素有序
  • D.它的时间复杂度和暴力遍历相同

答案：AB。单调队列通过淘汰「永远不可能成为最大值」的弱元素，让队首始终保持当前窗口的最大值，因此 A、B 正确。它依赖的是双端队列而不是堆，C 错；暴力法是 O(nk)，单调队列是 O(n)，D 错。这就像精英筛选，弱者被当场淘汰，队首永远是最强者。

Q7. 用单调队列求解长度为 n 的数组、窗口大小为 k 的滑动窗口最大值，时间复杂度是？

单选题 · hard

  • A.O(nk)
  • B.O(n)← 正确答案
  • C.O(nlogn)
  • D.O(k)

答案：B。虽然外层循环有 n 次迭代，但每个元素最多被入队一次、出队一次，总操作次数是 O(n)。暴力法对每个窗口重新比较 k 次才是 O(nk)。单调队列的巧妙之处在于淘汰永远不会成为答案的元素，让每一轮都是 O(1) 摊还。

Q8. 优先队列（二叉堆实现）插入一个新元素的平均时间复杂度是？

单选题 · mid

  • A.O(1)
  • B.O(logn)← 正确答案
  • C.O(n)
  • D.O(nlogn)

答案：B。插入新元素时先放到堆末尾，然后不断和父节点比较并「上浮」。二叉堆是完全二叉树，高度为 log n，上浮最多跨越一个树高，因此复杂度 O(logn)，与急诊室分诊台每次调整的层级数对应。

Q9. 关于顺序实现（数组）与链式实现，下列说法正确的有？

多选题 · hard

  • A.数组支持 O(1) 的随机访问← 正确答案
  • B.链表在头部插入和删除是 O(1)← 正确答案
  • C.数组扩容时需要整体搬迁原有元素← 正确答案
  • D.链表在任何场景下都比数组快

答案：ABC。数组是一段连续内存，按下标一步定位，随机访问 O(1)；链表节点用指针串联，在已知节点的头部增删只需改指针，O(1)；数组扩容要申请更大内存并复制全部元素，C 正确。但链表需要额外指针空间且缓存不友好，并非任何场景都快，D 错。

Q10. 用大小为 K 的「最大堆」扫描 n 个元素求 TopK 最小元素，扫描结束后堆顶元素是什么？

单选题 · extreme

  • A.第 K 小的元素← 正确答案
  • B.第 K 大的元素
  • C.全局最小的元素
  • D.全局最大的元素

答案：A。维护大小为 K 的最大堆时，堆里始终保留「当前遇到的最小的 K 个元素」，堆顶是这 K 个里最大的那一个，所以堆顶恰是全体数据中第 K 小的元素。就像急诊室只保留病情最重的 K 个病人，分诊台上最轻的那个就是第 K 重。若求 TopK 最大则用最小堆，堆顶就是第 K 大。