中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第3章 栈和队列

数据结构 栈和队列 第三章 栈和队列 主讲：张昱 重点：栈和队列的基本特征，表示与 yuzhang@ustc.edu 实现 0551-3603804 难点：递归、循环队列 1/52 2/52 第三章 栈和队列 3.1栈 3.1找 。定义 特囊的线性表：操作变限 3.2栈的应用举例 是展宽仅在兼愿进杜墙入戴喷操作的腹性表 3.3栈与递归的实现 九许桶入求测除的一墙琳为楼顶(op),另一墙称为机毫(bottom) ■逻辑特征 出栈 一进栈 3.4队列 后进先出在.FO) 栈顶 3.5离散事件模拟 ■ADT Stack 南地化空栈、判前栈空、判前栈满 联顶vs.GetElem(L,l,&e) 入找vs.ListInsert&L,l,e) vs.ListDelete(&L,i,&e) a 3/50 4/50 ADT Stack 数据对象：D-f间EE目emSet,.1,2,“nn≥0 GetElem(L,i,&e) 数据关系：R-R1R1-长41>1aeD,23.…n GerTop(S.&e p 基本操作：。 初%条件：栈$己存在且非空 Initstack(&s】 蜂作结架：用：S中钱顶元 操作结果：构造一个空的栈S 初始条件：钱s已存在Listinsert(&L,ie Push(&s.e DestroyStack(&S) 初始条件：钱8已存在 操作结果：插入元素e为新的栈顶元素 操作结果：销吸钱S Pop(&S,&e ClearStack(&S) 初条件：钱s已存在且菲孕ListDelete(&L,i&e 初始条件：钱S已存在 操作结果：利除S的栈顶元素，并用e返回其值 操作结果：将栈S重置为空栈 Stack Traverse(S.visit()) StackEmpty(S 初始条件：栈S已存在且非空 初始条件，钱s已存在 操作结果：从钱底到钱顶依次对s的每个数据元素调用函数() 操作结果：若S为空找，则题回TRUE,否测返回FALSE 旦t()失数，则轻作失毁 StackLength(S) ADT Stack 初始条件：钱S已存在 操作结果：返国栈S中数据元素的个数 5/50 图 6/50 图 1

1 1/52 数据结构——栈和队列 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/52 重点：栈和队列的基本特征，表示与 实现 难点：递归、循环队列 第三章 栈和队列 3/50 第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.5 离散事件模拟 4/50 3.1 栈 „ 定义 特殊的线性表：操作受限 是限定仅在表尾进行插入或删除操作的线性表 允许插入或删除的一端称为栈顶(top),另一端称为栈底(bottom) „ 逻辑特征 后进先出(LIFO) „ ADT Stack 初始化空栈、判断栈空、判断栈满 取栈顶 vs. GetElem(L, i, &e) 入栈 vs. ListInsert(&L, i, e) 出栈 vs. ListDelete(&L, i, &e) 出栈 进栈 an . . . . a1 栈顶 栈底 5/50 6/50 GetElem(L, i, &e) ListInsert(&L, i, e) ListDelete(&L, i, &e)

3.1栈-顺序栈-类型定义 3.1栈-顺序栈-基本操作的实现 。题序想 ·顺序找 。基本操作的实现 。类型定义 注意t即的含义—的定 。战项的初始化：S.top=S.base #define STACK_INIT_SIzE1O0/∥存情空间的初地分配量 空，S.base==5.top ,找满：5.top-S.base>=S.stacksize #define STACKINCREMENT10/∥存情空间的分配增量 。入栈：S.top++=e,出找：e=*-S.top typedef struct( ElemType *base; 川提度指针 ElemType *top:∥线顶指针（拉亚元意的下一个位置） int stacksize; top- ∥当前分配的存伸容量 top >SqStack; base base- 空栈 a进栈 b进栈 7/50 回 钩定：op指向找顶元的下一个位 图 3.1栈-顺序栈-基本操作的实现 3.1栈赞钱的表示与实现 ,顺序栈 ■链栈 ·无栈满问题（除非分配不出内存），空间可扩充 top ,栈顶一链表的表头 。可以不必引入头结，点 hase has o柳一N一□一□一…一囚 e进栈 ∫进栈溢出 e出栈 约定：top指向栈顶元素所在的结点 约定：top指向找顶元素的下一个位量 9/50 图 10/50 图 3.2栈的应用举例 3.2栈的应用举例-数制转换 ,数制转换 ■数制转换：将十进制数N转换成其他d进制数 ■括号匹配的检验 ,算法思想：N=(N div d)Xd+N mod d ■行编辑程庄 1)保存余数N%d 2)N=N/d, ■迷宫求解 3)若N==0结束，否则继续1)。 ■表达式求值 保存的余数从先到后依次表示转换后的d进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表栈来保存：当全部的余 数求出后，通过逐个出栈输出d进制数。 11/50 图 12/50 图 2

2 7/50 3.1 栈–顺序栈-类型定义 „ 顺序栈 „ 类型定义 注意top的含义——约定 #define STACK_INIT_SIZE 100// 存储空间的初始分配量 #define STACKINCREMENT 10// 存储空间的分配增量 typedef struct{ ElemType *base; // 栈底指针 ElemType *top; // 栈顶指针(栈顶元素的下一个位置) int stacksize; // 当前分配的存储容量 }SqStack; 8/50 3.1 栈–顺序栈-基本操作的实现 „ 顺序栈 „ 基本操作的实现 „ 栈顶的初始化：S.top = S.base „ 栈空：S.base == S.top „ 栈满：S.top - S.base >= S.stacksize „ 入栈：*S.top ++ = e，出栈：e = *--S.top base 空栈 a 进栈 b 进栈 a top base top base top a b 约定：top指向栈顶元素的下一个位置 9/50 3.1 栈–顺序栈-基本操作的实现 base e 进栈 f 进栈溢出 e出栈 e d c b a top base top base top 约定：top指向栈顶元素的下一个位置 e d c b a „ 顺序栈 d c b a 10/50 3.1 栈–链栈的表示与实现 约定：top指向栈顶元素所在的结点 „ 链栈 „ 无栈满问题(除非分配不出内存), 空间可扩充 „ 栈顶----链表的表头 „ 可以不必引入头结点 top N ^ 11/50 3.2 栈的应用举例 „ 数制转换 „ 括号匹配的检验 „ 行编辑程序 „ 迷宫求解 „ 表达式求值 12/50 3.2 栈的应用举例-数制转换 „ 数制转换: 将十进制数N转换成其他d进制数 „ 算法思想：N = ( N div d )×d + N mod d 1) 保存余数N%d 2) N=N/d， 3) 若N==0结束，否则继续1)。 保存的余数从先到后依次表示转换后的d 进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表——栈来保存；当全部的余 数求出后，通过逐个出栈输出d进制数

3.2栈的应用举例-数制转换 3.2栈的应用举例-行编辑程序 行铺舞程序(P49) ■数制转换 。处理规则：造#通一格：漫@退一行 。算法（算法3.1P48) 算法题想：引入校，保存终增输入的一行字符（理行处理）： 出一次 void conversion(int N,int d) 透©逼一行清法 InitStack(S); while(N){Push(S,N%/od);N=N/d; 化5 while(!StackEmpty(S)){ 3)ch!=EOF Pop(S,e); 3.1)ch!=EOF &ch!='\n' 3.1.1)ch为#，Pop5,c.轴3.1.4) printf(e); 3.1.2)dh为@'， C1ear5ac(S,转3.1.4) 3.1.3)dh为其恤：Push(s,h),被3.1.4) 3.1.4)再读入享符h,雕读3.1) 3。实小，) 3.2)处理完 13/50 囵 14/50 回图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ,表达式求值(P52) ,问题描述 。表达式的表示 ·只包含+，*，/四个双目运算符，且算符本身 不具有二义性： ,中缀表达式(a+b)*c-d*(e-a) 。三个算术四则运算的规则 ,前级表达式*+abc*d-ea (波兰式) 先乘雕，后加减 ,后缀表达式ab士c*deae*。 (逆波兰式) ·从左算到右 。先括号内，后括号外 →算符间的优先关系（算符的优先级和结合性）（表3.1） 分支站点是算特 。#:表达式的开始符和结束符 ·只有(==)，'#==#， 叶子结点是操作数 ,假设输入的是一个合法的表达式。 15/50 回 16/50 图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ·算法思短 ·输入：前缀表达式串（被兰式） 输入：中氧表达式率 输出：表达式值 输出：表达式值 ,入OPTR和OPWD两个线 例：-*+abc*d-ea 钓始OPTR有一元膏”，OPND为空 ,通到算蒋时，由于远算对象还来读到，放前存 入一半将 um(GetTop(OPND)) 是算特，Push(OPND,C) 爱老整清音茶法入的竹逃系对 (OPTR),比款率c的优壳关事 管存的算将个最不国定，需要引入款播结构保存 ·针对上例：在进行算一个运算前，需智存， Pop(OPTR,x) ·敢据结构的操作塘点：后进先出→机 t>cr Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); 。管存的运算对象个数不国定，需要引入最端结构保存 x=Operate(a,theta,b); 。针对上例：在迹行第一个+运算前，馨智存a,b,c Push(OPND,x); 。敷霜辅构的操作将点：后进光出→投 。整能害入亭特处夏。 17/50 图 ·不衡共比模料特种儿点来蜡合出，只要幕林的选界对白 整齐全，即可计算！18/50

3 13/50 3.2 栈的应用举例-数制转换 „ 数制转换 „ 算法(算法3.1 P48) void conversion(int N, int d){ InitStack(S); while(N) { Push(S, N%d); N=N/d; } while(!StackEmpty(S)) { Pop(S, e); printf(e); } } 14/50 3.2 栈的应用举例-行编辑程序 „ 行编辑程序(P49) „ 处理规则：遇‘#’退一格；遇‘@’退一行 „ 算法思想：引入栈，保存终端输入的一行字符（逐行处理）； 遇‘#’退一格——出栈一次 遇‘@’退一行——清栈 „ 步骤： 1）初始化栈S 2）读入字符ch 3）ch!=EOF 3.1) ch!=EOF && ch!=’\n’ 3.1.1）ch为‘#’：Pop(S, c), 转3.1.4) 3.1.2）ch为‘@’： ClearStack (S) , 转3.1.4) 3.1.3）ch为其他： Push (S, ch) , 转3.1.4) 3.1.4）再读入字符ch，继续3.1) 3.2) 处理完一行，清空栈 3.3) 如ch!=EOF，读入字符ch，继续3) 15/50 3.2 栈的应用举例-表达式求值 „ 表达式求值(P52) „ 表达式的表示 „ 中缀表达式 (a+b)*c-d*(e-a) „ 前缀表达式 -*+abc*d-ea (波兰式) „ 后缀表达式 ab+c*dea-*- (逆波兰式) - * * + a b c d - e a 分支结点是算符 叶子结点是操作数 16/50 3.2 栈的应用举例-表达式求值 „ 问题描述 „ 只包含+, -, *, / 四个双目运算符，且算符本身 不具有二义性； „ 三个算术四则运算的规则 „ 先乘除,后加减 „ 从左算到右 „ 先括号内,后括号外 Î算符间的优先关系（算符的优先级和结合性）(表3.1) „ #: 表达式的开始符和结束符 „ 只有 '('==')'，'#'=='#'； „ 假设输入的是一个合法的表达式。 17/50 3.2 栈的应用举例-表达式求值 „ 算法思想 输入：中缀表达式串 输出：表达式值 „ 引入OPTR和OPND两个栈 „ 初始OPTR有一元素‘#’，OPND为空 „ 读入一字符c c==‘#’：return(GetTop(OPND)) c是非运算符：Push(OPND,c) c是运算符：t=GetTop(OPTR)，比较t和c的优先关系 t<c： Push(OPTR,c) t==c： Pop(OPTR, x) t>c： Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x); „ 继续读入字符处理。 18/50 3.2 栈的应用举例-表达式求值 „ 输入：前缀表达式串(波兰式) 输出：表达式值 例： -*+abc*d-ea „ 遇到算符时，由于运算对象还未读到，故暂存 „ 遇到运算对象时，需要判断当前最近读入的算符的运算对象 是否齐全，若齐全则计算否则暂存 „ 暂存的算符个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个运算前，需暂存-,* „ 数据结构的操作特点：后进先出-Æ栈 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个+运算前，需暂存a,b,c „ 数据结构的操作特点：后进先出-Æ栈 „ 不需要比较算符的优先级和结合性，只要算符的运算对象已 经齐全，即可计算！

3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 OpndType EvaluatePostExpr(OKII氧设表达文是合法的 ·输入：后领表达式申（逆波兰式） InitStack(OPND);c=getchar(); 输出：表达式值 while (cl#) if (!IsOP(c))Push(OPND,c); 。例：ab+c*dea-* else( 。退到进算时桌时，由于算将在后，故前存该进算对康 Pop(OPND,b);Pop(OPND,a); 逼到算符时，立即计算 Push(OPND,doop(a,c,b)); 。前存的运算时章个数不园定，营要引入款据站构保存 。上侧中：在进行第一个运算前，嚼督存和，b c=getchar(); 。数据结构的操作特点：后选先出~蝇作数技 。不需要比校算将的优先银塘合性 result GetTop(OPND);DestroyStack(OPND); 退到算符时，直接从操作数找中弹出所需的操作数进行计 return result; 算：计算后再将计算帅录入栽 19/50 回 2D/50 图 3.2栈的应用举例-表达式转换 栈的概念运用 。表达式的不同表示之间的相互转换 ■问题1：习题桌3.6P23 。逆波兰式)波兰式 。轴入序列：123…H ,如：ab+c*dea-*.-*+abc*d-ea ■轴出序列P1P2户3…P ·共同点 ,证明，不存在i<j<k使得P,<P<P 。运算对津的次序一票 ·证（反证法）：假设存在<<k,使，<P,< ,不需要指号区分优光最和纳合性 ?<k”n最先出找，P最后出找 ·某算符在所有算特中的女序决定丁它的计算欲序 由鞭设如即，是三个敢中最大的 ,转换的思想 :入提序列是按值道增的 a。黄材保线为病保年健 :若某个值大的先出找。花中还有比它小的值，这些值将按值道常 。逆波兰式)中鞭表达式 的次序依次输出 即即先出，P和部比，小，录后着出，P的值应该是最小的 ,如：ab+c*dea-*.→(a+b)*c-d*(e-a) 图 这与服设相矛看。 21/50 22/50 图 3.3栈与递归的实现 3.3栈与递归的实现 ,递归的定义 递归 递推 ·递归(recursion):直接或间接地调用自身， 。递归的规则 int fact1(int n) int fact2(int n) 开始 。递归终止条件 if(n<0)return-1; 如：nl=(n-11*n if(n<0)return-1; else if(n==0)return 1; fact=1;i=1; 01=1 return n*fact1(n-1); ile(i<=n) ·递推：从已知的初始条件出 r 发，恶次递推出最后要求的值，结 fact *=;++ 如：01=1,1=0I*1=1 2 2!=11*2=2 23/50 可图 24/50 图 4

4 19/50 3.2 栈的应用举例-表达式求值 OpndType EvaluatePostExpr(){ //假设表达式是合法的 InitStack(OPND); c=getchar(); while (c!=‘#’) { if ( !IsOP(c) ) Push(OPND, c) ; else{ Pop(OPND, b); Pop(OPND, a); Push(OPND, doOp(a,c,b)); } c=getchar(); } result = GetTop(OPND); DestroyStack(OPND); return result; } 20/50 3.2 栈的应用举例-表达式求值 „ 输入：后缀表达式串(逆波兰式) 输出：表达式值 „ 例： ab+c*dea-*- „ 遇到运算对象时，由于算符在后，故暂存该运算对象 „ 遇到算符时，立即计算 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 上例中：在进行第一个运算前，需暂存a,b „ 数据结构的操作特点：后进先出-Æ操作数栈 „ 不需要比较算符的优先级和结合性 „ 遇到算符时，直接从操作数栈中弹出所需的操作数进行计 算；计算后再将计算结果入栈 21/50 3.2 栈的应用举例-表达式转换 „ 表达式的不同表示之间的相互转换 „ 逆波兰式Æ波兰式 „ 如： ab+c*dea-*- Æ -*+abc*d-ea „ 共同点 „ 运算对象的次序一致 „ 不需要括号区分优先级和结合性 „ 某算符在所有算符中的次序决定了它的计算次序 „ 转换的思想 „ 参照逆波兰式的计算过程，将计算转换为待计算的算符和运 算对象的串的拼接 „ 逆波兰式Æ中缀表达式 „ 如： ab+c*dea-*- Æ (a+b)*c-d*(e-a) 22/50 栈的概念运用 „ 问题1：习题集3.6 P23 „ 输入序列：1 2 3 … n „ 输出序列：p1 p2 p3 … pn „ 证明：不存在i<j<k, 使得pj < pk < pi „ 证(反证法)：假设存在i<j<k, 使pj < pk < pi ∵ i<j<k ∴ pi 最先出栈，pk最后出栈 由假设知pi 是三个数中最大的 ∵入栈序列是按值递增的 ∴若某个值大的先出栈，栈中还有比它小的值，这些值将按值递减 的次序依次输出 即pi 先输出，pj 和pk都比pi 小，pk最后输出，pk的值应该是最小的 这与假设相矛盾。 23/50 3.3 栈与递归的实现 „ 递归的定义 „ 递归(recursion)：直接或间接地调用自身. „ 递归的规则 „ 递归终止条件 如: n! = (n-1)! *n 0! = 1 „ 递推：从已知的初始条件出 发，逐次递推出最后要求的值。 如：0!=1, 1!= 0!*1 = 1 2! = 1! *2 = 2 …… 24/50 3.3 栈与递归的实现 递归 int fact1(int n) { if (n<0) return -1; else if (n==0) return 1; return n*fact1(n-1); } 递推 int fact2(int n) { if (n<0) return -1; fact=1; i=1; while (i<=n) { fact *= i; i++; } }

3.3栈与递归的实现 3.3栈与递归的实现 ,递归与递推的关系 ,递归的对象：一个对象部分地包含它自己， 递归算法的执行过程分递推与回归两个阶段。 或用它自已给自己定义。如莱些数据结构的 定义 ,在递推阶段，把较复杂的问题（规模为）的求 战性表的另男一种定义（归纳定义）： 解推到比原问题简单一些的问题（规模小于） 。基本步：若元素个数为0，则称为空表 的求解。 ,归纳步：若元素个敢大于0，则有且仅有一个第一 ,在回归阶段，当获得最简单的情况后，逐级返 个无素（表头），剩余元素形成一个表〔表)· 回，依次获得稍复杂问愿的解。 ,递归的过程：一个过程直接或间接地调用自 遂推是递归的一个阶段，递归包含着递推。 己 如：0的阶乘是1，n(n>0)的阶乘等于n乘上(n-1) 的阶乘 25/50 回 26/50 图 3.3栈与递归的实现 3.3栈与递归的实现-阶桑函数 ■递归的应用 ■定义是递归的 ·递归定义：如阶来、Fibonacci数列等 1, 当n=0时 ,数据结构：如表、树、二叉树等 n!= ,问题求解：如Hanoi塔 n*(n-I)1, 当n≥1时 求解阶乘函数的递归算法 long fact long n) if(n==0)return 1; /递归结来条件 else return n fact (n-1); /递归的规则 27/50 圆 28/50 图 3.3栈与递归的实现阶乘函数 3.3栈与递归的实现数据结构 主程序main():fact(4) 。数据结构是递归的-一表 ·空表 fact(4):计算4*fact(3) ·非空表：（表头元素+除表头元素以外的剩余元素） 递参 6 。查找夜L中是否有元意值ε fact3):计算3*act2 结 LinkList search(LinkList L,ElemType e) 归调用 传 回归求位 //L为不带头结点的单陶非狮环链表 fact2:计算2*fact(1 返回 1 if (L==NULL)return NULL; fact:计算1*fact(0 else if L->data==e return L; else return search(L->next,e); fact0):直接定值为1 29/50 图 30/50 图

5 25/50 3.3 栈与递归的实现 „ 递归与递推的关系 递归算法的执行过程分递推与回归两个阶段。 „ 在递推阶段，把较复杂的问题（规模为n）的求 解推到比原问题简单一些的问题（规模小于n） 的求解。 „ 在回归阶段，当获得最简单的情况后，逐级返 回，依次获得稍复杂问题的解。 递推是递归的一个阶段，递归包含着递推。 26/50 3.3 栈与递归的实现 „ 递归的对象：一个对象部分地包含它自己， 或用它自己给自己定义。如某些数据结构的 定义 线性表的另一种定义(归纳定义): „ 基本步：若元素个数为0，则称为空表 „ 归纳步：若元素个数大于0，则有且仅有一个第一 个元素(表头)，剩余元素形成一个表(表尾) 。 „ 递归的过程：一个过程直接或间接地调用自 己 如：0的阶乘是1，n(n>0)的阶乘等于n乘上(n-1) 的阶乘 27/50 3.3 栈与递归的实现 „ 递归的应用 „ 递归定义：如阶乘、Fibonacci数列等 „ 数据结构：如表、树、二叉树等 „ 问题求解：如Hanoi塔 28/50 3.3 栈与递归的实现–阶乘函数 „ 定义是递归的 ⎩ ⎨ ⎧ ∗ − ≥ = = 当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n 求解阶乘函数的递归算法 long fact ( long n ) { if ( n == 0 ) return 1; //递归结束条件 else return n * fact (n-1); //递归的规则 } 29/50 3.3 栈与递归的实现–阶乘函数 主程序 main( ): fact(4) 参 数 传 递 递 归 调 用 结 果 返 回 回 归 求 值 fact(4): fact(3): fact(2): fact(1): fact(0): 1 直接定值为1 计算 4*fact(3) 计算 3*fact(2) 计算 2*fact(1) 计算 1*fact(0) 1 2 6 24 30/50 3.3 栈与递归的实现–数据结构 „ 数据结构是递归的--表 „ 空表 „ 非空表: (表头元素+除表头元素以外的剩余元素) „ 查找表L中是否有元素值e LinkList search(LinkList L, ElemType e) // L为不带头结点的单向非循环链表 { if ( L==NULL ) return NULL; else if ( L->data==e ) return L; else return search(L->next, e); }