三、栈和队列

本章导览

共 5 个小节：栈、队列、栈的应用、队列的应用、特殊矩阵 & 压缩存储

本章重点

• 栈 LIFO（一端进出）、队列 FIFO（一端进一端出）
• 循环队列用取模复用空间
• 栈→括号匹配/表达式/递归；队列→层次遍历/调度

栈

关键点

• 仅栈顶进出，LIFO；顺序栈（数组+top）、链栈（无容量限制），均 O(1)
• 易错：判空 top==-1、判满 top==n-1

顺序栈

链栈

关键点

头插法建立单链表对应进栈操作。 单链表的删除操作对应出栈操作。

队列

关键点

• FIFO，front 出、rear 入
• 顺序队列用循环队列避免假溢出
• 牺牲一个单元判断：(rear+1)%n==front 满、rear==front 空

顺序队列

关键点

其他出题方式：注意尾指针指向的是下一个插入位置还是队尾元素位置。 如果只想队尾元素位置，插入时如下图所示，需要先位移指针再插入，初始化时可以把尾指针放在头指针的前一格。

链表队列

双端队列

栈的应用

关键点

• 栈的 LIFO 适合嵌套 / 回溯类问题
• 括号匹配（左入右弹）、表达式求值（中缀转后缀）、递归（系统调用栈）

括号匹配

表达式求值

递归

队列的应用

关键点

• 队列 FIFO 适合按顺序 / 讲公平
• 树的层次遍历（BFS 雏形）、操作系统调度（就绪队列 FCFS、缓冲区）

树的层次遍历

操作系统中的应用

关键点

多个进程争抢着使用有限的系统资源时，FCFS（先来先服务）是一种常用策略。 Eg：打印数据缓冲区。

特殊矩阵 & 压缩存储

关键点

• 相同 / 零元素只存一份
• 对称、三角矩阵用一维映射公式；稀疏矩阵用**三元组 (行,列,值)**或十字链表
• 易错：映射下标推导（行/列优先、起始 0 还是 1）