大学数据结构《栈和队列》课堂讲授课件

数据结构·课堂讲授数据结构《栈和队列》课堂讲授课件后进先出·先进先出·顺序存储·链式存储课程：数据结构

讲授人：任课教师课程导览01栈与队列入门受限线性表的概念与特性02栈的存储实现顺序栈与链栈的构造03队列的存储实现循环队列判空判满突破04典型应用与考点经典案例与考研高频栈与队列入门受限的线性表一端进出的艺术，从栈开始01栈：限定一端的线性表栈是限定仅在表尾进行插入或删除操作的线性表栈是一种操作受限的线性表，逻辑结构仍是一对一的线性关系栈的核心要素操作受限仅允许在表尾进行插入或删除栈顶（Top）允许插入和删除的一端，位置动态变化栈底（Bottom）另一端，固定不动空栈不含任何元素的空表栈S=(a1,a2,...,an)01栈底元素a102栈顶元素an03操作端

插入

删除

读取所有操作只能在栈顶完成后进先出特性详解最后入栈的元素最先出栈后进先出（LastInFirstOut，简称

LIFO）LIFO核心理解最早进入栈的元素最晚离开，最早被压在栈底。元素的进出顺序由操作时机决定，因此入栈序列与出栈序列并不一一对应。LIFO两种基本动作2项入栈（Push）把新元素放到栈顶元素的上面，使之成为新的栈顶元素。出栈（Pop）删除栈顶元素，使其相邻元素成为新的栈顶元素。栈的基本操作与边界状态一套完整的栈操作接口，两种必须掌握的边界状态所有插入、删除、读取操作仅在栈顶完成，其余位置不可访问写代码时必须先判空或判满，才能安全调用入栈与出栈。基本操作初始化判空判满入栈出栈取栈顶销毁两种边界状态上溢(Overflow)错误状态栈已满仍要入栈下溢(Underflow)正常操作但无效栈已空仍要出栈队列：两端分工的线性表队列是先进先出的线性表区别于栈，队列在两端分工：一端插入、一端删除队尾（Rear）允许插入的一端，元素由此入队。入队Rear队头（Front）允许删除的一端，元素由此出队。出队FIFO队列的基本操作队列操作仅在队尾插入、队头删除队列操作仅在队尾插入、队头删除，比栈多开了一个口，所以最早进入的元素也最早出去注意事项所有插入操作仅在队尾完成，所有删除、读取操作仅在队头完成。队列不允许在中间插入或删除，这正是它作为受限线性表的体现。InitQueue初始化队列，构造一个空队列DestroyQueue销毁队列，释放所占内存空间EnQueue入队，若队列未满，将新元素加入队尾DeQueue出队，若队列非空，删除队头元素并返回GetHead读队头元素，只读取而不删除栈与队列对比二者都是受限线性表，区别在于运算规则与操作端对比维度栈队列插入端栈顶队尾删除端栈顶队头运算原则后进先出先进先出操作受限仅一端操作两端分工逻辑结构一对一线性一对一线性从逻辑结构看，栈和队列与普通线性表完全相同，都是

一对一的线性关系；区别仅在于

运算规则不同——栈只在一端操作，队列在两端分工。因此教材常把它们统称为

操作受限的线性表。栈的存储实现数组与链表的抉择顺序栈与链栈，各擅胜场02栈的两种存储思路栈作为特殊线性表，同样有顺序与链式两种存储实现两种存储思路顺序栈连续存储单元｜链栈链表结点串接顺序栈顺序栈用一组地址连续的存储单元存放数据元素核心优势数组下标直接定位栈顶，入栈出栈极其方便链栈优先使用顺序栈链栈用链表结点通过指针串接起来性能短板入栈出栈需管理结点、指针与内存释放，代码更复杂顺序栈的结构与指针顺序栈用连续空间存放自栈底到栈顶的数据元素顺序栈以base、top、stacksize三个关键量维护自栈底到栈顶的连续存储空间关键指针设置base指示栈底元素位置，初始化后始终指向栈底不变top指示栈顶位置，随操作动态变化stacksize指示栈可使用的最大容量空栈约定若以

top等于0

表示空栈，配合C语言数组下标从0开始会带来不便另设base指针指示栈底，top与base相等时表示空栈为方便操作，通常规定top指向真正栈顶元素之上的下标地址顺序栈的入栈操作入栈即指针上移并写入新元素入栈操作的核心：指针上移，元素写入1判断栈是否已满已满则不能入栈→2将新元素写入top指针当前位置写入成功后指针不动→3top指针增1指向新的栈顶元素之上理解指针的移动方向，是掌握顺序栈一切操作的基础关键性质一每插入一个栈顶元素，top指针增1，复杂度

O(1)关键性质二栈非空时，top始终指向栈顶元素的上一位置，常数时间关键性质三入栈操作时间复杂度为

O(1)，常数操作顺序栈的出栈操作出栈即指针下移并取出元素对照记忆：入栈是先写入后加一，出栈是先减一再取出。指针的一增一减，正是栈顶动态变化的直观体现。1步骤01判断栈是否为空为空则不能出栈2步骤02top

指针先减1指向栈顶下移3步骤03取出元素并返回取出该位置元素，完成出栈关键性质3项top

指针减1每删除一个栈顶元素，top

指针随之递减栈空条件top

与

base

相等，二者都指向栈底O(1)复杂度出栈操作时间复杂度同样为

O(1)栈满判断与处理策略栈满需及时处理，否则产生上溢状态时间开销对比栈满处理策略4项栈满判定top−base=stacksize，即栈顶指针与栈底指针之差达到最大容量方案一·报错向操作系统返回溢出信息方案二·扩容分配更大空间作为新栈，将原栈内容整体移入新栈扩容代价需复制全部原有元素，时间复杂度为O(n)；预分配过大浪费内存、过小频繁扩容链栈：运算受限的单链表链栈是只在链表头部操作的运算受限单链表链栈以链式存储画出栈的单端操作，用指针串接换来了空间上的灵活。核心特征4项头指针即栈顶链表的头指针就是栈顶无需头结点不需要头结点基本不栈满基本不存在栈满情况，无需预分配空间空栈即头指针空空栈等价于头指针指向空基本操作2项入栈生成新结点p，写入数据，将其插入栈顶，修改栈顶指针指向p出栈取出栈顶结点数据，栈顶指针下移，释放原结点链式存储换空间灵活指针串接单端操作顺序栈与链栈对比时间与空间的权衡，决定栈实现方式的选择对比维度顺序栈链栈存储结构数组连续空间链表结点入栈出栈时间O(1)O(1)栈满情况可能上溢基本不会满扩容代价复制元素

O(n)修改指针

O(1)空间分配需预先分配无需预先分配存储开销仅数据空间需额外指针域选择建议：对

时间效率要求高、数据量大

宜用顺序栈；对

内存灵活、容量不确定

宜用链栈。二者入栈出栈均在栈顶进行，时间复杂度都可达

O(1)。共享栈：空间互补让两个栈共享一片数组空间，实现空间互补共享栈（双端栈）把两个栈底固定于数组两端，栈顶动态变化、向中间生长，内存空间得以互补利用。背景与原理问题由来多栈各自独立申请顺序栈，因难以估计空间而出现有的栈溢出、有的栈空闲。共享栈机制两个栈的栈底分别放在一维数组两端下标0和M减1处，两栈顶动态变化、向中间生长，形成空间互补。关键判定条件状态判定条件栈1空top1等于

负一栈2空top2等于

maxsize栈满top1加1等于top2，两个栈顶在中间相遇空间互补节省内存队列的存储实现环形空间的智慧判空判满，循环队列的核心03队列的存储结构概览队列同样有顺序存储与链式存储两种实现队列的两种物理结构，决定了它的存取方式与适用场景。—顺序存储与链式存储front

队头指针负责删除，rear

队尾指针负责插入。顺序队列隐藏关键缺陷，引出本章核心顺序队列用连续空间实现配合

front

与

rear

两个下标链队列用链表实现含有队头指针和队尾指针顺序队列与假上溢顺序队列的核心缺陷：假上溢普通顺序队列相当于一个一次性队列，空间浪费严重——循环复用需引入环形设计思路结论普通顺序队列相当于一个一次性队列，空间浪费严重。要让它循环复用，就须引入环形设计思路。顺序队列实现存储基于一个数组，配合

front（队头）与

rear（队尾）两个下标入队入队时

rear

增1出队出队时

front

增1致命问题：假上溢浪费每块空间仅使用一次，元素出队后空间不被复用阻塞指针单向移动，rear

超出边界时，即使数组前部还有大量空闲，也无法继续入队VS循环队列的环形思路用取余运算让指针回绕，实现空间循环复用将顺序队列的首尾相接，形成环状空间——循环队列核核心机制：取余运算入队rear更新为

rear加1之后对N取余出队front更新为

front加1之后对N取余效效果与复杂度回绕指针到达数组末端时，自动绕回到数组开头复用已出队释放的空间得以重复使用，彻底消除假上溢O(1)入队、出队时间复杂度均为

O(1)，避免移动元素的开销循环队列判空判满判空判满是循环队列的核心难点队空时

front与rear相等；队满时二者也可能相等，故不能只凭相等判断空满。难点所在队空时

front与rear相等队满时

front与rear也可能相等因此不能只凭二者相等来判断空满解决约定牺牲一个存储空间，使rear与front错开避免判空与判满的状态混淆队尾永远保留一个空单元，这是考研与面试的必考知识点循环队列操作与队列长度三大指针公式与队列长度计算队列指针操作入队rear出队front取余maxsize队列长度针指针更新公式入队rear

更新为

rear+1

后对

maxsize

取余出队front

更新为

front+1

后对

maxsize

取余长队列长度计算队列长度=(rear−front+maxsize)%maxsizefront指向

队头元素rear指向

队尾元素的下一位置掌握这三条公式，循环队列的所有基本操作都能顺利实现循环队列计算实例用具体下标演示指针移动设队列长度

maxsize等于10，初始

front与rear均为0操作过程入队3个rear依次变为

1、2、3rear出队1个front变为

1front队列长度(3−1+10)mod10=2=实际元素个数判满验证rear=9(9+1)mod10=0front=0即判定为

满rear循环回0核心结论整个过程中，入队出队全程无需移动任何元素这正是循环队列高效的关键链队列的实现用链表表示的队列，带头结点更便于操作用链表实现的队列，通过头结点与队尾指针管理进出队操作。“链队列无需预分配、无假上溢，严格遵循先进先出，适合队列长度变化较大的场景。”链队列定义一个链队列有一个队头指针和一个队尾指针为操作方便，通常给链队列添加一个头结点，并令头指针指向该头结点关键操作插入新队尾元素让队尾结点的指针指向新结点，再将队尾指针指向新结点删除队头元素取下头结点之后的第一个结点并返回其值典型应用与考点从理论到实战括号匹配与表达式求值04括号匹配：栈的经典首秀编译器如何检查括号是否缺失1遇到左括号入栈2遇到右括号与栈顶左括号匹配，成功则出栈最里层的左括号最先被匹配，最后出现的左括号最先被匹配——完全符合

后进先出，可用栈解决三种失败情形左右类型不匹配：用方括号去配圆括号右括号单身：栈已空却遇右括号，缺少左括号左括号单身：遍历结束栈非空，缺少右括号表达式求值：中缀转后缀用栈暂存运算符，按优先级调控输出表达式求值中缀转后缀·逆波兰表达式三类符号操作数参与运算的数值，直接承载结果运算符如

＋

－

×

÷，决定运算方式界限符（括号）界定优先级与结合范围中缀与后缀中缀运算符在两个操作数中间后缀运算符在两个操作数后面，又称逆波兰表达式中缀转后缀规则操作数：直接输出到后缀表达式左括号：直接入栈运算符：优先级大于栈顶则入栈，否则先弹出更高优先级运算符再入栈左优先原则保证运算顺序唯一，对应的后缀表达式也唯一；示例：中缀2加3乘4，转为后缀

234×

＋后缀表达式求值用操作数栈，遇运算符即弹栈计算关键注意：先弹出的是右操作数，后弹出的是左操作数，对减法和除法尤为关键，顺序颠倒会导致结果错误。中缀转后缀与后缀求值两阶段配合，即可完成任意中缀表达式的求值。1第一步遇到操作数进栈操作数直接压入栈顶暂存等待后续运算符2第二步遇到运算符弹栈计算再压回依次弹出两个操作数进行计算结果压回栈中3第三步遍历结束得出结果栈中留下的唯一元素即为结果依赖后进先出特性完成求值栈与递归、函数调用递归的本质依赖栈的后进先出特性栈帧压入与弹出，递归执行的每一步都在这条轨迹上展开函数调用栈机制3项保存现场信息保存

返回地址

与

局部变量压栈入栈帧每进入一层调用，压入一个栈帧弹栈返回返回时弹出栈帧，恢复上一层状态递归与栈的关系3项天然映射每层递归调用对应一个栈帧，是栈结构的天然体现典型实例典型例子：阶乘、斐波那契数列深度风险递归层次过深，栈帧持续累积，可能造成

栈溢出理解函数调用栈，是真正掌握递归执行过程的关键，也是领会栈这一结构核心价值的必经之路数制转换与撤销操作栈在最基础场景中的实际价值栈凭借后进先出特性，天然支持撤销与状态恢复，是回溯类问题的首选结构1第1步原理N整除d

再乘以d，加上

N对d取余数值整除与取余分解2第2步余数入栈将每次求得的余数依次入栈3第3步出栈输出转换完成依次弹出，恰好得到正确的高低位顺序1第1步原理软件中的撤销功能通常使用栈实现2第2步操作入栈每次操作记录入栈3第3步弹出撤销撤销时弹出最近一次操作，契合后进先出队列的典型应用凡需要先来先服务的场景都离不开队列队列是处理“顺序等待”类问题的首选结构，与栈的后进先出形成鲜明互补树的层次遍历按层访问从上到下、从左到右依次访问结点FIFO原则严格遵循先进先出（FIFO）原则公平有序先到达的结点先被处理，保证公平与有序图的广度优先遍历逐层扩展按距离由近及远逐层向外扩展FIFO原则严格遵循先进先出（FIFO）原则公平有序先到达的结点先被处理，保证公平与有序操作系统任务调度典型队列如打印队列、进程就绪队列FIFO原则严格遵循先进先出（FIFO）原则公平有序先到达的任务先被处理，保证公平与有序迷宫问题用栈实现深度优先搜索与路径回溯栈天然支持回溯与状态恢