第 3 章 栈和队列1

2020 4 15 1 开始学习本章前要掌握 从数据结构角度看 栈和队列仍属于线性结构 具有线性结构的共同特征 学习本章时 要注意到栈和队列所具有的线性结构的共性 更要掌握其个性 栈和队列是操作受限的线性结构 本章具体内容见本章目录 第三章栈和队列 2020 4 15 2 栈 Statck 的定义 栈是操作受限制的线性表定义 仅在表尾进行插入或删除操作的线性表 概念 栈顶 在栈顶操作 是表尾 通常用top表示 栈底 bottom 是表头 空栈 空表 通常栈底固定 栈顶移动 2020 4 15 3 栈的表示和实现 顺序存储结构 顺序栈 链式存储结构 链栈 2020 4 15 4 顺序栈 利用一组地址连续的存储单元依次自栈底到栈顶存放栈的数据元素 在数组上实现时 栈底位置可以设置在数组的任一个端点 而栈顶是随着插入和删除而变化的 可以用一个整形变量top存放栈顶的指针 数据入栈或出栈时使整形变量top分别加1或减1 2020 4 15 5 顺序栈的类型定义 defineMAXSIZE1024typedefstruct ElemTypedata MAXSIZE inttop SeqStack 2020 4 15 6 用顺序栈实现栈的运算 1 SeqStackSeqStackInit 构造一个空栈SSeqStackS S top 1 returnS 初始化 2020 4 15 7 用顺序栈实现栈的运算 2 intSeqStackEmpty SeqStackS 判断栈S是否为空if S top 1 returnTRUE elsereturnFALSE 判栈空 2020 4 15 8 用顺序栈实现栈的运算 3 voidSeqStackPush SeqStackS ElemTypex 插入元素x为新的栈顶元素if S top MAXSIZE 1 printf Overflow exit 0 栈满 退出运行S top S data S top x 入栈 2020 4 15 9 用顺序栈实现栈的运算 4 ElemTypeSeqStackPop SeqStackS 若栈S不空 删除S的栈顶元素 并返回其值if S top 1 栈已空 退出运行 printf Empty n exit 0 x S data S top S top returnx 出栈 2020 4 15 10 用顺序栈实现栈的运算 5 ElemTypeSeqStackGetTop SeqStackS if S top 1 printf 栈空 n exit 0 elsereturn S data S top 取栈顶元素 2020 4 15 11 双向栈 栈1底 栈2底 栈1 栈2 两个栈共享一个向量空间 栈底分别设在两端 写出进栈和退栈操作 2020 4 15 12 双向栈的类型定义 definem64typedefstruct ElemTypedata m inttop 2 top 0 top 1 分别是两个栈的栈顶指针 TStack 初始化时 top 0 1和top 1 m表示栈空 栈顶相遇时表示栈满 入栈时栈顶指针相向移动 2020 4 15 13 链栈 用链式存储结构实现的栈称为链栈 通常链栈可用单链表表示 因此其结点结构与单链表的结构相同 链栈结点的类型描述 typedefstructStackNode ElemTypedata structStackNode next StackNode LinkedStack 由于栈只在栈顶操作 因此 通常不设头结点 2020 4 15 14 链栈图示 top 2020 4 15 15 用链栈实现栈的运算 1 LinkedStackLinkedStackInit 构造一个空栈 栈顶指针为topLinkedStacktop top NULL returntop 链栈的初始化 2020 4 15 16 用链栈实现栈的运算 2 intLinkedStackEmpty LinkedStacktop 判定栈S是否是空栈if top NULL returnTRUE elsereturnFALSE 判栈空 2020 4 15 17 用链栈实现栈的运算 3 LinkedStackPush LinkedStacktop ElemTypex 插入元素x为新的栈顶元素 链栈用栈顶指针top表示 s LinkedStack malloc sizeof StackNode 创建一个新结点s data x 设置新结点的数据域s next top 设置新结点的指针域top s 设置新栈顶指针returntop 入栈 2020 4 15 18 用链栈实现栈的运算 4 ElemTypePop LinkedStacktop 若栈S不空 则删除S的栈顶元素 并返回其值if top NULL x top data p top top top next free p returnx else printf 栈空 n exit 0 退栈 2020 4 15 19 利用栈消除任何递归 1 利用栈可以将任何递归函数转换成非递归的形式 其步骤大致如下 入栈处理设一个工作栈代替递归函数中的栈 栈中每个记录包括函数的所有参数 函数名 局部变量和返回地址 所有递归调用语句处 改写成把形参 局部变量和返回地址入栈的语句 修改确定本次递归调用时的实在参数之新值 转到函数的第一个语句 转下页 2020 4 15 20 利用栈消除任何递归 2 接上页 退栈处理若栈空 算法结束 执行正常返回 若栈不空 从栈中退出参变量赋给原来入栈时相对应的参变量 并退出返回地址 转到执行返回地址处的语句 继续执行 2020 4 15 21 队列 Queue 定义和概念 队列 队列是一种只允许在表的一端插入 在另一端删除的存取受限的线性表 概念 队尾rear 插入端 线性表的表尾 队头front 删除端 线性表的表头 2020 4 15 22 队列 Queue 图示 FIFO FirstInFirstOut 先进先出表 a1 a2 a3 an 1 2020 4 15 23 队列的表示和实现 顺序存储结构 循环队列 链式存储结构 链队列 2020 4 15 24 队列的顺序表示和实现 问题 如何解决 假上溢 现象 约定队头指针指向队头元素的前一个位置 队尾指针指向队尾元素 2020 4 15 25 队列的顺序表示和实现 循环队列 2020 4 15 26 循环队列操作示意图 2020 4 15 27 循环队列 空队列条件 Q rear Q front 满队列条件 Q rear Q front 问题 如何区别队空和队满 1 牺牲一个存储空间 2 引入一个标志变量区别空和不空 3 使用计数器 2020 4 15 28 循环队列类型定义 defineMAXSIZE256typedefstruct ElemTypedata MAXSIZE 数据的存储区intfront rear 队头队尾指针 SeQueue 循环队 2020 4 15 29 循环队列的初始化 SeQueueSeQueueInit SeQueueQ Q front Q rear 0 returnQ 2020 4 15 30 循环队列的入队 voidSeQueueIn SeQueueQ ElemTypex if Q rear 1 MAXSIZE Q front printf Full n exit 0 队列满 退出运行 Q rear Q rear 1 MAXSIZE Q data Q rear x 2020 4 15 31 循环队列的出队 ElemTypeSeQueueOut SeQueueQ if Q front Q rear printf Empty n exit 0 队已空 退出运行 Q front Q front 1 MAXSIZE x Q data Q front 读出队头元素returnx 出队完成 2020 4 15 32 循环队列的判空 intSeQueueEmpty SeQueueQ if Q front Q rear returntrue elsereturnfalse 2020 4 15 33 求队中元素个数 intSeQueueLength SeQueueQ 返回队列Q的元素个数return Q rear Q front MAXSIZE MAXSIZE 2020 4 15 34 链队列 用链表表示的队列简称为链队列 为便于操作 一个链队列需要分别指示队头和队尾的两个指针 2020 4 15 35 链队示意图 a 非空队 b 空队 c 链队中只有一个元素结点 2020 4 15 36 链队列的类型描述 typedefstructLQNode ElemTypedata structLQNode next LQNode LinkedQNode 链队结点的类型及指针typedefstruct StructLQNode front rear LQueue LinkedQueue 将头尾指针封装在一起的链队 2020 4 15 37 链队列的初始化 创建一个带头结点的空队 LinkedQueueLinkedQueueInit Q LinkedQueue malloc sizeof LQueue 申请头尾指针结点p LinkedQNode malloc sizeof LQNode 申请链队头结点p next NULL Q front Q rear p returnQ 2020 4 15 38 链队列的入队 voidLinkedQueueIn LinkedQueueQ ElemTypex p LinkedQNode malloc sizeof LQNode p data x p next Q rear next 或p next NULL Q rear next p Q rear p 2020 4 15 39 链队列的判空 intLinkedQueueEmpty LinkedQueueQ if Q front Q rear returntrue elsereturnfalse 2020 4 15 40 链队列的出队 出队 LinkedQueueOut LinkedQueueQ if LinkedQueueEmpty Q p Q front next 队列带头结点Q front next p next x p data 队头元素放x中if p Q rear Q rear Q front 只有一个元素时 出队后队空 此时还要修改队尾指针free p returnx 2020 4 15 41 4 设栈的输入序列为1 2 3 n 输出序列为p1 p2 pn 若p1 n则当n i 1时 pi为 若存在k 1使pk n 则当i k时 pi为 A pi n i 1B pi不确定C pi n i k 中国科学技术大学1992八 8 1分 2020 4 15 42 5 某表达式的前缀形式为 ABCD E F GH它的中缀形式为 A AB C D E F G HB AB C D HC AB C D E F G H D AB C D E F G H 中国科学技术大学1992八 7 1分 2020 4 15 43 6 有六个元素6 5 4 3 2 1的顺序进栈 问下列哪一个不是合法的出栈序列 A 543612B 453126C 346521D 234156 北方交通大学2001一 3 2分 2020 4 15 44 9 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时 应执行 A h next s B s next h C s next h h next s D s next h next h next s 北京理工大学2005十一 6 1分 2020 4 15 45 13 若一个栈以向量V 1 n 存储 初始栈顶指针top为n 1 则下面x进栈的正确操作是 A top top 1 V top x B V top x top top 1 C top top 1 V top x D V top x top top 1 南京理工大学1998一 13 2分 2020 4 15 46 14 若栈采用顺序存储方式存储 现两栈共享空间V 1 m top i 代表第i个栈 i 1 2 栈顶 栈1的底在v 1 栈2的底在V m 则栈满的条件是 A top 2 top 1 0B top 1 1 top 2 C top 1 top 2 mD top 1 top 2 南京理工大学1999一 14 1分 2020 4 15 47 16 一个递归算法必须包括 武汉大学2000二 2 A 递归部分B 终止条件和递归部分C 迭代部分D 终止条件和迭代部分 2020 4 15 48 17 intcalc intx inty if y 1 returnx elsereturn calc x y 1 x a b均为正整数 则calc a b A a b 1 B a bC a bD a a 中国科学技术大学1995十四 14 6分 2020 4 15 49 19 表达式a b c d的后缀表达式是 南京理工大学2001一 2 1 5分 A abcd B abc d C abc d D abcd 2020 4 15 50 20 表达式3 2 4 2 2 6 3 5求值过程中当扫描到6时 对象栈和算符栈为 其中 为乘幂 青岛大学2000五 5 2分 A 3 2 4 1 1 B 3 2 8 C 3 2 4 2 2 D 3 2 8 2020 4 15 51 21 设计一个判别表达式中左 右括号是否配对出现的算法 采用 数据结构最佳 A 线性表的顺序存储结构B 队列C 线性表的链式存储结构D 栈 西安电子科技大学1996一 6 2分 2020 4 15 52 23 用不带头结点的单链表存储队列 其队头指针指向队头结点 队尾指针指向队尾结点 则在进行出队操作时 江苏大学2004一 4 2分 A 仅修改队头指针B 仅修改队尾指针C 队头 队尾指针都可能要修改D 队头 队尾指针都要修改 2020 4 15 53 24 递归过程或函数调用时 处理参数及返回地址 要用一种称为 的数据结构 A 队列B 多维数组C 栈D 线性表 福州大学1998一 1 2分 2020 4 15 54 26 循环队列A 0 m 1 存放其元素值 用front和rear分别表示队头和队尾 则当前队列中的元素数是 南京理工大学2001一 5 1 5分 A rear front m mB rear front 1C rear front 1D rear front 2020 4 15 55 27 循环队列存储在数组A 0 m 中 则入队时的操作为 中山大学1999一 6 1分 A rear rear 1B rear rear 1 mod m 1 C rear rear 1 modmD rear rear 1 mod m 1 2020 4 15 56 输出受限的双端队列 即删除限制在一端进行 而插入仍允许在两端进行 输入受限的双端队列 即插入限制在一端进行 而删除仍允许在两端进行 29 已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有 A dacbB cadbC dbcaD bdac 2020 4 15 57 30 若以1234作为双端队列的输入序列 则既不能由输入受限的双端队列得到 也不能由输出受限的双端队列得到的输出序列是 西安电子科技大学1996一 5 2分 A 1234B 4132C 4231D 4213 2020 4 15 58 31 最大容量为n的循环队列 队尾指针是rear 队头是front 则队空的条件是 A rear 1 MODn frontB rear frontC rear 1 frontD rear l MODn front 南京理工大学1999一 16 2分 2020 4 15 59 35 设栈S和队列Q的初始状态为空 元素e1 e2 e3 e4 e5和e6依次通过栈S 一个元素出栈后即进队列Q 若6个元素出队的序列是e2 e4 e3 e6 e5 e1则栈S的容量至少应该是 南京理工大学2000一 6 1 5分 哈尔滨工业大学2004二 3 1分 A 6B 4C 3D 2 2020 4 15 60 36 用单链表表示的链式队列的队头在链表的 位置 清华大学1998一 1 2分 A 链头B 链尾C 链中 2020 4 15 61 41 执行 操作时 需要使用队列作辅助存储空间 华中科技大学2006一 1 2分 A 查找哈希 Hash 表B 广度优先搜索网C 先序 根 遍历二叉树D 深度优先搜索网 2020 4 15 62 38 4个园盘的Hahoi塔 总的移动次数为 北京邮电大学2005 A 7B 8C 15D 16 解答 C 2020 4 15 63 自测题14 用一个大小为1000的数组来实现循环队列 当前rear和front的值分别为0和994 若要达到队满的条件 还需要继续入队的元素个数是 北京工业大学2005二 3 3分 2020 4 15 64 3 9写出下列中缀表达式的后缀表达式 1 A B C 2 A B C D 3 A B C D E 4 A B D E F A D C 解答 1 ABC 2 AB C D 3 AB CDE 4 AB D EFAD C 2020 4 15 65 3 6设长度为n的链队列用单循环链表表示 若只设头指针 则入队和出队的时间如何 若只设尾指针呢 解答 若只设头指针 则入队的时间为O n 出队的时间为O 1 若只设尾指针 则入队和出队的时间均为O 1 2020 4 15 66 循环链队 只有尾指针 11 在一个循环链队中只有尾指针 记为rear 结点结构为数据域data 指针域next 请给出这种队列的入队和出队操作的实现过程 山东科技大学2002一 2 6分 2020 4 15 67 1 只有尾指针的循环链队的入队voidEnQueue LinkedListrear ElemTypex s LinkedList malloc sizeof Lnode s data x s next rear next 将s结点链入队尾rear next s rear s rear指向新队尾 2020 4 15 68 2 只有尾指针的循环链队的出队voidDeQueue LinkedListrear rear是带头结点的循环链队列的尾指针 if rear next rear printf 队空 n exit 0 s rear next next s指向队头元素rear next next s next 队头元素出队printf 出队元素是 s data if s rear rear rear next 删除后变成空队列 需要修改尾指针free s 2020 4 15 69 3 15设以数组Q m 存放循环队列中的元素 同时设置一个标志tag 以tag 0和tag 1来区别在队头指针 front 和队尾指针 rear 相等时 队列状态为 空 还是 不空 试编写相应的入队 QueueIn 和出队 QueueOut 算法 循环队列 tag区分是否为空 2020 4 15 70 1 初始化SeQueueQueueInit SeQueueQ 初始化队列Q front Q rear 0 Q tag 0 returnQ 2020 4 15 71 2 入队SeQueueQueueIn SeQueueQ inte 入队列if Q tag 1 2020 4 15 72 3 出队ElemTypeQueueOut SeQueueQ 出队列if Q tag 0 printf 队列为空 n exit 0 else Q front Q front 1 m e Q data Q front if Q front Q rear Q tag 0 空队列 return e 2020 4 15 73 3 16假设用变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数 试给出此循环队列的定义 并写出相应的入队 QueueIn 和出队 QueueOut 算法 循环队列 rear length 2020 4 15 74 1 循环队列的定义typedefstruct ElemTypeQ m 循环队列占m个存储单元intrear length rear指向队尾元素 length为元素个数 SeQueue 2020 4 15 75 2 初始化SeQueueQueueInit SeQueuecq cq为循环队列 本算法进行队列初始化 cq rear 0 cq length 0 returncq 2020 4 15 76 3 入队SeQueueQueueIn SeQueuecq ElemTypex cq是以如上定义的循环队列 本算法将元素x入队 if cq length m return 0 队满else cq rear cq rear 1 m 计算插入元素位置cq Q cq rear x 将元素x入队列cq length 修改队列长度 return cq 2020 4 15 77 4 出队ElemTypeQueueOut SeQueuecq cq是以如上定义的循环队列 本算法是出队算法 且返回出队元素 if cq length 0 return 0 队空else intfront cq rear cq length 1 m m 出队元素位置cq length 修改队列长度return cq Q front 返回对头元素 2020 4 15 78 循环队列 front count 32 如果用一个循环数组q 0 m 1 表示队列时 该队列只有一个队列头指针front 不设队列尾指针rear 而改置计数器count用以记录队列中结点的个数 1 编写实现队列的三个基本运算 判空 入队 出队 3分 2 队列中能容纳元素的最多个数是多少 1分 东北大学2002一 1 2020 4 15 79 typedefstruct ElemTypeq m intfront count front队首 count元素个数 cqnode 2020 4 15 80 1 判空 intEmpty cqnodecq if cq count 0 return 1 elsereturn 0 2020 4 15 81 2 入队 intEnQueue cqnodecq ElemTypex if count m printf 队满 n exit 0 cq q cq front count m x x入队count return 1 入队成功 2020 4 15 82 3 出队 intDelQueue cqnodecq if count 0 printf 队空 n return 0 printf 出队元素 cq q cq front x cq q cq front cq front cq front 1 m 计算新的队头指针return x 2020 4 15 83 双向栈 1 设有两个栈S1 S2都采用顺序栈方式 并且共享一个存储区 O maxsize 1 为了尽量利用空间 减少溢出的可能 可采用栈顶相向 迎面增长的存储方式 试设计S1 S2有关入栈和出栈的操作算法 哈尔滨工业大学2001七 12分 题目分析 两栈共享向量空间 将两栈栈底设在向量两端 初始时 s1栈顶指针为 1 s2栈顶为maxsize 两栈顶指针相邻时为栈满 两栈顶相向 迎面增长 栈顶指针指向栈顶元素 2020 4 15 84 definemaxsize100 两栈共享顺序存储空间所能达到的最多元素数 defineElemTypeint 假设元素类型为整型typedefstruct ElemTypestack maxsize 栈空间inttop 2 top为两个栈顶指针 stk stks s是如上定义的结构类型变量 为全局变量 2020 4 15 85 入栈操作 intpush inti intx 入栈 i 0表示左栈s1 i 1表示右栈s2 x是入栈元素 入栈成功返回1 否则返回0 if i1 printf 栈号输入不对 n exit 0 if s top 1 s top 0 1 printf 栈已满 n return 0 switch i case0 s stack s top 0 x return 1 break case1 s stack s top 1 x return 1 push 2020 4 15 86 退栈操作 ElemTypepop inti 退栈算法 i 0时为s1栈 i 1时为s2栈 退栈成功返回退栈元素 否则返回 1 if i1 printf 栈号输入错误 n exit 0 switch i case0 if s top 0 1 printf 栈空 n return 1 elsereturn s stack s top 0 case1 if s top 1 maxsize printf 栈空 n return 1 elsereturn s stack s top 1 switch 算法结束 2020 4 15 87 判断栈空intEmpty return S top 0 1 2020 4 15 88 栈的应用 逆波兰表达式 4 从键盘上输入一个逆波兰表达式 用伪码写出其求值程序 规定 逆波兰表达式的长度不超过一行 以 符作为输入结束 操作数之间用空格分隔 操作符只可能有 四种运算 例如 23434 2 山东师范大学1999七 10分 题目分析 逆波兰表达式 即后缀表达式 求值规则如下 设立运算数栈OPND 对表达式从左到右扫描 读入 当表达式中扫描到数时 压入OPND栈 当扫描到运算符时 从OPND退出两个数 进行相应运算 结果再压入OPND栈 这个过程一直进行到读出表达式结束符 这时OPND栈中只有一个数 就是结果 2020 4 15 89 Floatexpr 从键盘输入逆波兰表达式 以 表示输入结束 floatOPND 30 OPND是操作数栈init OPND 两栈初始化 Floatnum 0 0 结果变量初始化scanf c x是字符型变量 2020 4 15 90 while x switch case 0 0 2020 4 15 91 casex break 遇空格 继续读下一个字符 casex push OPND pop OPND pop OPND break casex x1 pop OPND x2 pop OPND push OPND x2 x1 break casex push OPND pop OPND pop OPND break casex x1 pop OPND x2 pop OPND push OPND x2 x1 break default 其它符号不作处理 结束switchscanf c 算法结束 2020 4 15 92 21 已知Ackermann函数定义如下 akm m n n 1ifm 0akm m n ack m 1 1 ifm0n 0akm m n akm m 1 akm m n 1 ifm0n0 1 写出Ack 2 1 的计算过程 2 写出计算Ack m n 的递归和非递归算法 北京师范大学2005六 2 15分 递归 2020 4 15 93 1 Ack 2 1 的计算过程Ack 2 1 Ack 1 Ack 2 0 因m0 n0而得 Ack 1 Ack 1 1 因m0 n 0而得 Ack 1 Ack 0 Ack 1 0 因m0 n0而得 Ack 1 Ack 0 Ack 0 1 因m0 n 0而得 Ack 1 Ack 0 2 因m 0而得 Ack 1 3 因m 0而得 Ack 0 Ack 1 2 因m0 n0而得 Ack 0 Ack 0 Ack 1 1 因m0 n0而得 Ack 0 Ack 0 Ack 0 Ack 1 0 因m0 n0而得 Ack 0 Ack 0 Ack 0 Ack 0 1 因m0 n 0而得 Ack 0 Ack 0 Ack 0 2 因m 0而得 Ack 0 Ack 0 3 因m 0而得 Ack 0 4 因n 0而得 5 因n 0而得 2020 4 15 94 2a 递归算法intAck intm n if m 0 return n 1 elseif m 0 2020 4 15 95 2b 非递归算法intAckerman intm intn intakm m n inti j for j 0 j n j akm 0 j j 1 第一行for i 1 i m i 2 m行 akm i 0 akm i 1 1 第一列for j 1 j n j 2 n列akm i j akm i 1 akm i j 1 return akm m n 2020 4 15 96 递归 组合 22 设计算法以求解从集合 1 n 中选取k k n 个元素的所有组合 例如 从集合 1 4 中选取2个元素的所有组合的输出结果为 12 13 14 23 24 34 合肥工业大学2000五 5 8分 2020 4 15 97 从集合 1 n 中选出k 本题中k 2 个元素 为了避免重复和漏选 可分别求出包括1和不包括1的所有组合 即包括1时 求出集合 2 n 中取出k 1个元素的所有组合 不包括1时 求出集合 2 n 中取出k个元素的所有组合 将这两种情况合到一起 就是题目的解 2020 4 15 98 intA n 设集合已存于数组A中 voidcomb intP inti intk if k 0 printf P elseif k n P i A i comb P i 1 k 1 包含i 从i 1位置开始取k 1个comb P i 1 k 不包含i 从i 1位置开始取k个 算法结束说明 i从0开始 表示当前的起始下标k表示取k个元素 2020 4 15 99 递归 全排列 25 已知有n个元素存放在向量S 1 n 中 其值各不相同 请写一递归算法 生成并输出n个元素的全排列 中国科学技术大学1992十三 20分 苏州大学2005五 15分 2