第三章 栈和队列 · 速览

数据结构目录阅读详版下载 Markdown

一、栈（Stack）

定义与操作

• 栈：操作受限的线性表，只在表尾（栈顶）做插入/删除；LIFO 后进先出。插入=入栈 Push，删除=出栈 Pop。
• 基本操作：Push（加到栈顶）、Pop（移除并返回栈顶）、Top（返回栈顶不移除）、isEmpty（判空）。
• 术语：栈底 bottom（最早到达）；栈顶 top（最晚到达）；插入/删除都必须在栈顶；元素个数为零时为空栈。
• ADT 复杂度：initialize / isEmpty / top / push / pop 均 $O(1)$；抽象表中 destroy 为 $O(n)$，但具体顺序栈析构本页标 $O(1)$、链式栈析构 $O(N)$。
• 出栈序列：按 A、B、C 入栈并非所有排列都合法；如无法得到 CAB（C 先出则 A 在 B 之下，A 不能早于 B 出）。

顺序栈（seqStack，动态数组）

• 连续空间；栈底在 0 下标；栈空 top = -1，栈满 top = maxSize-1。
• push：满则 doubleSpace()，elem[++top_p]=x；pop：return elem[top_p--]。
• doubleSpace() 容量翻倍，$O(N)$；均摊后 push/pop/isEmpty/top 均 $O(1)$（均摊法）。构造/析构本页标 $O(1)$。
• 不做自动扩容则需 isFull()；isEmpty/top 不改成员，用 const。

链式栈（linkStack，单链表）

• top_p 指栈顶=单链表首结点；结点类为私有内嵌类。
• push：top_p = new node(x, top_p)（一行：建结点+指向原顶+顶移到新结点）。
• push/pop/isEmpty/top 均 $O(1)$；构造 $O(1)$、析构 $O(N)$（逐结点释放）。

栈的应用：表达式求值

• 三式：中缀（符人类、不符计算机）、后缀/逆波兰（符计算机、无需括号）、前缀/波兰。
• 中缀→后缀：操作数直接输出；( 入栈；) 弹栈输出直到 (（括号都不输出）；普通左结合运算符弹出栈顶优先级≥当前者再入栈，右结合运算符例外；扫描完弹出剩余。
• 易错：( 入栈时优先级最高、在栈内时最低（仅遇 ) 才弹）。例 a*(b+c)/d→a b c + * d /。
• 后缀计算：操作数入栈；遇运算符弹两个计算后入栈；最终栈顶为结果。例 5 7 2 3 * - * 8 2 / +=9。
• 两步（转换+计算）可合并为一次扫描。
• calc：枚举顺序 OPAREN,ADD,SUB,MULTI,DIV,EXP,CPAREN,VALUE,EOL 蕴含优先级比较（opStack.top()>=MULTI）；EXP 直接入栈，连续乘方按右结合；BinaryOp 先弹 num2(右)后弹 num1(左)。

栈小结

• 栈=操作受限线性表；用于符号匹配、表达式计算、函数调用/递归；顺序存储最常用。

---

二、队列（Queue）

定义与操作

• 队列：一端插入（enQueue 队尾）、另一端删除（deQueue 队首）；FIFO 先进先出。
• ADT：initialize / isEmpty / getHead（队首非空）/ enQueue（非满）/ deQueue（非空）/ destroy。

顺序队列与顺序循环队列（seqQueue）

• 三种组织：队头固定（出队大量移动）、队头不固定（全 $O(1)$ 但浪费空间）、循环队列（取模复用空间）。
• 入队 rear=(rear+1)%MaxSize; elem[rear]=x；出队 front=(front+1)%MaxSize。
• 牺牲一个单元：front 指向的单元不存元素（其后一个才是队首）。队空 rear==front，队满 (rear+1)%maxSize==front。
• 动态数组 + doubleSpace()；构造/判空/出队/取队首 $O(1)$，析构 $O(N)$，进队均摊 $O(1)$。

链式队列（linkQueue，单链表）

• 单链表即可（不需双链表）；front 指队首、rear 指队尾。队空 front==rear==NULL，不存在队满。
• 判空/取队首/入队/出队均 $O(1)$；构造 $O(1)$、析构 $O(N)$。
• 边界：入队若 rear==NULL 须同设 front=rear；出队后若 front==NULL 须把 rear 置 NULL。

优先队列（Priority Queue）

• 带优先数（一般越小优先级越高），高优先级先出，同级 FIFO。
• 顺序：策略一 进队 $O(1)$/出队找最高 $O(n)$（出队用末元素填空，无需循环；严格同级 FIFO 需额外稳定处理）；策略二 进队按序插入 $O(n)$/出队取队首 $O(1)$。
• 链式：策略一 进队尾 $O(1)$/出队找最高 $O(n)$；策略二 有序链表（首结点优先级最高）出队 $O(1)$/进队找位插入 $O(n)$（不移动原有元素）。
• 进队/出队复杂度为 $O(1)$、$O(n)$ 或 $O(n)$、$O(1)$；用堆（二叉树）可降到 $O(\log_2 n)$。

队列的应用：排队系统模拟

• 模拟=计算机仿真现实系统收集统计；优点：无需真实顾客、速度快、结果可重现。
• 事件驱动：事件按时间排队，处理完直接拨到下一事件；到达间隔 $[a,b]$、服务时间 $[c,d]$ 均匀分布；统计平均等待时间/队列长度/利用率。
• 单服务台：一个队列；① 生成全部到达事件入队；② 队头服务前累计等待时间；③ 返回累计/顾客数。用 rand()。

单调队列

• 满足单调性的双向队列；新元素破坏单调性就从队尾弹出直到满足再入队；用于滑动窗口每 k 个连续数的最值。
• 求最小值时队列对应值单调递增、队首即窗口最小值；队中存下标，队首下标 ≤ i-k 则出队。

队列小结

• 队列=两端分别插入/删除的线性表；用于打印队列、进程队列等。
• 顺序循环存储（进队按动态扩容作均摊分析）与链式存储常见操作均 $O(1)$；考虑链式结点额外开销，顺序循环队列最常用。