lambdagent/agentexample/sample_knowledge/数据结构讲义-第3章-栈与队列.md

第 3 章 栈与队列（示例讲义）

本文件是示例知识库的演示材料，为简化版讲义提纲。

3.1 栈（Stack）

栈是只允许在一端（栈顶）进行插入和删除的线性表， 后进先出（LIFO）。基本操作：push（入栈）、pop（出栈）、top（取栈顶）。

顺序栈

用数组 + 栈顶指针 top 实现。top = -1 表示空栈； 入栈 data[++top] = x；出栈 x = data[top--]。 上溢：满栈再入栈；下溢：空栈再出栈（必须判错）。

共享栈

两个栈共用一个数组，栈底分设两端、栈顶相向生长， top1 + 1 == top2 时栈满。提高空间利用率。

栈的典型应用

1. 括号匹配：遇左括号入栈，遇右括号弹栈比对。
2. 表达式求值：中缀转后缀（操作符栈），后缀求值（操作数栈）。
3. 递归与函数调用：系统用调用栈保存现场；递归可借助显式栈 改写为非递归。
4. 出栈序列计数：n 个元素的合法出栈序列数为卡特兰数 C(2n,n)/(n+1)（常考选择题：判断某序列是否可能的出栈序列）。

3.2 队列（Queue）

队列是只允许队尾插入、队头删除的线性表，先进先出（FIFO）。

循环队列

用数组实现时为避免「假溢出」，把数组看成首尾相接的环： rear = (rear + 1) % MaxSize。

• 牺牲一个单元区分队空/队满： 队空 front == rear；队满 (rear + 1) % MaxSize == front。
• 队列长度：(rear - front + MaxSize) % MaxSize（必考公式）。

链式队列

带头结点的单链表 + front/rear 两个指针；不存在溢出问题 （除非内存耗尽）。注意删除最后一个元素时 rear 要重新指向头结点。

双端队列（deque）

两端都可插入删除。受限双端队列（一端只进、一端只出等）的 合法输出序列判断是常考题型。

队列的典型应用

1. 层次遍历（树的按层访问、图的 BFS）。
2. 操作系统的任务调度、打印缓冲。
3. 用两个栈模拟队列 / 用两个队列模拟栈（经典面试题）。

本章要点（考试常考）

1. 循环队列队满/队空判定与长度公式（必考填空/计算）。
2. 出栈序列合法性判断（必考选择）。
3. 中缀表达式转后缀并求值（必考大题）。
4. 栈在递归消除中的作用（简答）。