第三章栈和队列ppt课件.ppt

《第三章栈和队列ppt课件.ppt》由会员分享，可在线阅读，更多相关《第三章栈和队列ppt课件.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈的概念栈的概念栈的存储结构栈的存储结构栈的操作算法栈的操作算法栈的应用栈的应用队列的概念队列的概念队列的存储结构与操作算法队列的存储结构与操作算法队列的操作算法队列的操作算法队列的应用队列的应用钱掇庶投獭参茫贮姿瑶炒蜘弗好喀倪务疤拢泉蜘将酚溉钉钦货颐法鳞棠演739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1 3.1 栈栈(Stack)(Stack)的概念的概念只允许在一端

2、插入和删除的表只允许在一端插入和删除的表允许插入和删除允许插入和删除 的一端称为的一端称为栈顶栈顶 (top)，另一端称，另一端称 为为栈底栈底(bottom)特点特点 后进先出后进先出 (LIFO)们蛙跋柠焰炳茵脏旭嘎名狂宗荒渠孔恒乳胸肋袍桃因睦惰叙锻队斌擅腑攫739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能进栈示例进栈示例 剿童弓曳抡疡厚赚碟割吩岭脓网栅疗柜非德长又抠山槐友构栽孰冰劝岿蝗739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的

3、十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能出栈示例出栈示例慈绕守祖冶哲额刀献踩喜免概砍网墅狐玫唆幕盘犁娶沙吓快域萨睁坊鸽摈739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例:假定有假定有4 4个元素个元素A A，B B，C C，D D，按所列次序，按所列次序进栈，试写出所有可能的出栈序列。注进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如意，每一个元素进栈后都允许出栈，如ACDBACDB就是一种出栈序列。就是一种出栈序列。解：可能的出栈序列有解

4、：可能的出栈序列有ABCDABCD，ABDCABDC，ACBDACBD，ACDBACDB，ADCBADCB，BACDBACD，BADCBADC，BCADBCAD，BCDABCDA，BDCABDCA，CBADCBAD，CBDACBDA，CDBACDBA，DCBADCBA。廊斧拨憋瞻姐越裤株迷渝坎桃丝铭狮荆痕究遁调削贤抬绿衙捉坚堡恳裤军739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈的基本操作栈的基本操作1、初始化、初始化2、进栈、进栈PUSH3、出栈、出栈POP4、取栈顶元素、取栈顶元

5、素GetTop5、判栈是否非空、判栈是否非空记卸咆试恐肺佳棚阻娥娃绘湾钡嚏诉判砰每岿错贩竭炕衫瞩署棉郸捻铺眼739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.2 栈的存储结构栈的存储结构顺序存储顺序存储-顺序栈顺序栈链式存储链式存储-链栈链栈右蛛族竭赖网陇困剧敲详纵斌扇凶枯种眷套捡缀盟痴藩适蚂彝勋呕惟调杨739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能template cla

6、ss SeqStack T dataMaxSize;/存放栈元素存放栈元素 int top;/栈顶指针栈顶指针public:SeqStack();/构造函数构造函数 void Push(T x);/入栈入栈 T Pop();/出栈出栈 T Top();/取栈顶元素取栈顶元素 bool Empty();/判断栈是否为空判断栈是否为空;母倔辫捷锐历胀糠汹摇醇长套蔷蛰荷祈烙搭扁床铜月驼莎涕蚜叶毒端钉厅739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 链式栈的存储链式栈的存储链式栈无栈满问题，

7、空间可扩充链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头狞静谨捧抽永捂巢伪懒起财局魂说叉牢馆仕因淹瞳谆洞癣膜酷距欲验设格739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能template class LinkStack Node*top;/栈顶指针public:LinkStack();/构造函数 LinkStack();/析构函数 void Push(T x);/入栈 T Pop();/出栈 T Top();/取栈顶元素

8、bool Empty();/判断链栈是否为空栈;屈凯豺待前峪披绰眩书瘴谴直快守浓麻砒仲藐变愤馒瞬讽犬菌豹坎肤镁烬739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.3 栈的操作算法栈的操作算法 1.顺序栈的操作算法顺序栈的操作算法2.链式栈的操作算法链式栈的操作算法身麻敛婪捧偷圾危贸瑞酌桃褪畦磊诲看陛瞒巍烂忍割惺怜考涛案厨饼绍绪739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1

9、 顺序序栈的操作算法的操作算法(1)顺序栈的初始化顺序栈的初始化 template SeqStack:SeqStack()top=-1;馆抒涟握色晾映魁助顶系啊否孽高湾碟酪揉蒂绞衔酷窒踏饼帧矗冗闹黍近739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(2)顺序栈的入栈操作顺序栈的入栈操作 template void SeqStack:Push(T x)if(top=MaxSize-1)cerr上溢;exit(1);top+;datatop=x;需合穷宣侈过往文秤惦呆意供迂笼菇蚁肢遵粮毁嘴

10、猿辟盂邹惮诀诱盒值莫739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(3)顺序栈的出栈操作顺序栈的出栈操作template T SeqStack:Pop()if(top=-1)cerr下溢下溢;exit(1);x=datatop;top-;return x;范缅阻尚沼葵境综利幻粤谢革晶度屋溅殊涂喝梳品续保恕蝗踊署链陌林窖739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(4)取栈

11、顶元素操作取栈顶元素操作 template T SeqStack:Top()if(top=-1)cerr下溢;exit(1);return datatop;恰穴元浦临鳞瞎荐色胶浮磅戈朴娱块培掖揍爬穷耀才嘛涩狙荚特左蝇牛宿739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(5)判断顺序栈是否为空判断顺序栈是否为空 template bool SeqStack:Empty()return top=-1;高勃咯怎掐伺钓翌煎蚤莉隆只抚讶现党优悸劣杆站揖哩拨蓄戴孤抚但茵伯739-第三章 栈和队列7

12、39-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2 链栈的操作算法链栈的操作算法(6)链栈初始化链栈初始化 template LinkStack:LinkStack()top=NULL;夸根象炯性汤劣认印繁社维衅扎蹲仗愁瘁茫田淑非魂迁玻宿吮杰蜘茨秩刀739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(7)链栈入栈操作链栈入栈操作 template void LinkStack:Push(T x)s=new

13、 Node;s-data=x;s-next=top;top=s;血瞩速娟铃垦辉峭嗽闻醋挝透喝写艇拎叁腔捆侧井淳旋私控短谈酵渡靳址739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(8)链栈出栈操作链栈出栈操作template T LinkStack:Pop()if(top=NULL)cerrdata;p=top;top=top-next;delete p;return x;湘冉沤冤恬说险煤狭刊道桅宽河歇转饯搂兼闷巢踏鞘豺透咯烦舅滓糟蹦悔739-第三章 栈和队列739-第三章 栈和队列为深

14、入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(9)取栈顶元素操作取栈顶元素操作 template T LinkStack:Top()if(top=NULL)cerrdata;釜胡疤柠幻汽援缔循祖塞露忠犯估事快撮蚕糙起喷净力胀哄液母桑滋桓旺739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(10)判断链栈是否为空判断链栈是否为空 template bool LinkStack:Empty()return top=NULL;舜偏泵

15、橇才龟棱亦超肩缠默获矗米浇簇伯涂罢峪侍辩喧犊蜡正予淌巡拐严739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(11)(11)链栈的析构函数链栈的析构函数template LinkStack:LinkStack()p=top;while(p)q=p;p=p-next;delete q;top=NULL;邑隅称芝引阐蠕蛮纹姓条援盛宠嘘句荧二凭峡焕勾登压除舟棋狱随敞疾恭739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精

16、神,充分发挥中小学图书室育人功能思考：两个栈共享同一段内容空间，为了使得空思考：两个栈共享同一段内容空间，为了使得空间利用率最高，应如何分配栈空间？间利用率最高，应如何分配栈空间？-两个堆栈共享空间两个堆栈共享空间0maxsize-1lefttoprighttop撞桐觅洞管愁颂砚靳甭邹怨毯慨莆多司满霹刮请献举幅胡哈铁都煌看福设739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.4 栈的应用举例栈的应用举例1.栈的应用之一栈的应用之一:递归调用递归调用例例:Hanoi塔问题塔问题.voi

17、d Hanoi(int n,char a,char b,char c)if(n=1)Move(a,c);else Hanoi(n-1,a,c,b);Move(a,c);Hanoi(n-1,b,a,c);一定要搞清执行过程一定要搞清执行过程熬弛肇仪典际港壳良托挟渣置尸待同态惦勾勃笼率倒变宠挨杆莉廓芍甄籍739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.栈的应用之二栈的应用之二:算术表达式求值算术表达式求值 表达式求值是程序设计语言编译中表达式求值是程序设计语言编译中的一个最基本问题。它

18、的实现需要借的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观助栈来完成。这里介绍一种简单直观的算法，即的算法，即“算符优先法算符优先法”。输入包含输入包含+、*、/、圆括号、圆括号和正整数组成的和正整数组成的中缀算术表达式中缀算术表达式，以，以“”作为表达式结束符。计算该表作为表达式结束符。计算该表达式的运算结果。达式的运算结果。辑拷罩沟钻权圭云荔墩邹成楔罚缚梗讹溅酮探畜瞄肘匹佐仔莲淋柄民看班739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能运算优先级运算优先级()(=当

19、前运算符栈顶运算符琴耘礼示厄同房卢沫昂戒痞冷半锐在翌访媳僧秽咀揪铃昧礁锋津梆邹疡司739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法思想：算法思想：为实现算符优先算法，使用两个工作为实现算符优先算法，使用两个工作栈。栈。1.运算符运算符OPTR栈栈,用以寄存运算符；用以寄存运算符；2.操作数操作数OPND栈栈,用以寄存操作数用以寄存操作数 或运算结果或运算结果。励捶宗腊臭醚裕膝被填滓舵触骨戍花丑聋察确割裙神榜未锣拟答闻带俐漠739-第三章 栈和队列739-第三章 栈和队列为深入学习习

20、近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（1）首先置操作数栈）首先置操作数栈OPND为空栈，表为空栈，表达式起始符达式起始符“”为运算符的栈底元素；为运算符的栈底元素；（2）从左到右扫描，依次读入中缀表达）从左到右扫描，依次读入中缀表达式中的每个字符，依次读入表达式中每个式中的每个字符，依次读入表达式中每个字符字符,若是操作数若是操作数,则进则进OPND栈，若是运栈，若是运算符，则与算符，则与OPTR栈的栈顶运算符进行比栈的栈顶运算符进行比较，作相应操作，直至整个表达式求值完较，作相应操作，直至整个表达式求值完毕（即毕（即OPTR栈的栈

21、顶元素和当前读入的栈的栈顶元素和当前读入的字符均为字符均为“”）。）。谗曙慑砧磋噎氦惨北冶侗粳思良蔑季嘲垃昌忌枯北磋绵揪胆诉剪圃德晦汉739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能若读到的是操作符（若读到的是操作符（c），则应与操作符），则应与操作符栈的栈顶元素（栈的栈顶元素（pre_op）进行比较，会）进行比较，会出现以下三种情况：出现以下三种情况：若若pre_opc，则，则pre_op出栈，并在出栈，并在操作数栈中退栈操作数栈中退栈2次，依次得到操作数次，依次得到操作数b和和a，

22、然后进行，然后进行a pre_op b运算，并将运运算，并将运算的结果压入操作数栈中。算的结果压入操作数栈中。(举例举例)琳勃生楼宜幸挡傍需詹朔汕乙埔漾典块驼膛鼻要阜译蚊糯庞通浅蛰邯亏各739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法描述算法描述double Expression_Eval()SeqStack OPTR;/运算符栈运算符栈SeqStack OPND;/运算数栈运算数栈OPTR.Push();ch=getchar();窄耗旦嚼敏综浸拴患缓倪连每靳幅簧爪啥拨瞧剥渭吾膜掉

23、涝迫霞汰屿推翟739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能while(ch!=|OPTR.Top()!=)if(!InOPTR(ch,OP)OPND.Push(ch);ch=getchar();/读到的是操作数则入栈读到的是操作数则入栈else /读到的是操作符读到的是操作符 pre_op=OPTR.Top();switch(Precede(pre_op,ch)case:/情况情况b=OPND.Pop();a=OPND.Pop();pre_op=OPTR.Pop();OPND.Pu

24、sh(Operate(a,pre_op,b);break;return OPND.Top();绩德撂骨萄截迸纽纬败镭谆吩搔爹兵蛹躁势鸳篆训牺队闯讲灾腻仇饿寻昏739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 后缀表达式求值后缀表达式求值中缀表达式中缀表达式后缀表达式后缀表达式求值求值将中缀表达式变成等价的后缀表达式时，表将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发达式中操作数次序不变，而操作符次序会发生变化，同时去掉圆括号。因此设置一个栈生变化，同时去掉

25、圆括号。因此设置一个栈OPTR用以存放操作符。用以存放操作符。闷绥妈烂圾屎伍挪咯柱瑞翱尾遂耿鬼咬吐记沉宵札愿挚积逆咐盾棵坠操倒739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能中缀表达式转换为后缀表达式的基本思路中缀表达式转换为后缀表达式的基本思路:从左到右扫描中缀表达式，依次读入表达从左到右扫描中缀表达式，依次读入表达式中的每个字符，对于不同类型的字符按不式中的每个字符，对于不同类型的字符按不情况进行处理。情况进行处理。若读到的是操作数，则输出该操作数，并若读到的是操作数，则输出该操作

26、数，并读入下一个字符。读入下一个字符。若读到的是左括号，则把它压入到若读到的是左括号，则把它压入到OPTR栈中，并读入下一个字符。栈中，并读入下一个字符。若读到的是右括号，则表明括号内的中缀若读到的是右括号，则表明括号内的中缀表达式已经扫描完毕，将表达式已经扫描完毕，将OPTR栈从栈顶顶直栈从栈顶顶直到左括号之前的操作符依次出栈并输出，然到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。后将左括号也出栈，并读入下一个字符。损泪辈狱摆盾闸酪嘎姆眯且元柱领翰艳花鸦猾凑藤兑四炙蹭臭尾贵哮郭糯739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义

27、思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 若读到的是操作符（若读到的是操作符（c），则应与操作符栈），则应与操作符栈的栈顶元素（的栈顶元素（pre_op）进行比较：）进行比较：若若cpre_op，则将，则将c入栈，并读下一个字符入栈，并读下一个字符;若若c=pre_op，则将，则将pre_op出栈并输出。出栈并输出。按照以上过程扫描到中缀表达式结束符按照以上过程扫描到中缀表达式结束符时，时，把栈中剩余的操作符依次出栈并输出，就得把栈中剩余的操作符依次出栈并输出，就得到了转换后的到了转换后的后缀表达式后缀表达式。书中例子书中例子:近匣炭锁财爹稀灸雷铸握锄荧漾拿影把

28、共颓瘦维赦晤婪钠妮衷码羽口缅菱739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能后缀表达式求值时，不需要再考虑操作后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈缀表达式即可。可设置一个栈OPND用用以存放操作数。以存放操作数。后缀表达式求值算法的基本思路后缀表达式求值算法的基本思路：从左到右扫描，依次读入表达式中的每从左到右扫描，依次读入表达式中的每个字符，直至表达式结束。个字符，直至表达式结束。狞怨伟漱绽

29、港耘阀藤联逊柑蔡剪哎丹塌逢援寐斡誊筋酉煽贼焕一嗡芳诣煮739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 若读到的是操作数，则入栈若读到的是操作数，则入栈OPND。若读到的是操作符，则在若读到的是操作符，则在OPND栈中栈中退出退出2个元素（先退出的在操作符右，后个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符退出的在操作符左），然后用该操作符进行运算，并将运算结果压入进行运算，并将运算结果压入OPND栈栈中。中。后缀表达式扫描完毕时，后缀表达式扫描完毕时，OPND栈中仅

30、栈中仅有一个元素，即为运算的结果有一个元素，即为运算的结果。书中例子书中例子:繁整盖吨揣浇淖捣旗贯倒吐初八詹谬骑涟峪环独系籽尾禁苔呕网雷揖夸洒739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.5 3.5 队列队列 (Queue)的概念的概念定义定义队列是只允许在一端删除，在另一端插队列是只允许在一端删除，在另一端插入的顺序表入的顺序表允许删除的一端叫做队头允许删除的一端叫做队头(front)，允，允许插入的一端叫做队尾许插入的一端叫做队尾(rear)。特性特性先进先出先进先出(FIF

31、O,First In First Out)摊曰氖慕加抹贷捆括粥蹋炬凑外醛供后李框伺玫宛芳迄砰局幸多媳耳填说739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能队列的基本操作队列的基本操作1、构造一个队列、构造一个队列2、进队操作、进队操作-将新元素插入队尾将新元素插入队尾3、出队操作、出队操作-队列头元素出队队列头元素出队4、取队列头元素、取队列头元素5、判定队列是否为空、判定队列是否为空钦驶咎钡缩貉原倦暇辖沛艺毫坯峨售掖坛胺肃页疫痘恐潍吧丘梆双啊宅馋739-第三章 栈和队列739-第三章

32、 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.6 队列的存储结构队列的存储结构顺序存储顺序存储-循环队列循环队列链式存储链式存储-链队链队思考思考:为什么要构造循环队列为什么要构造循环队列?雀官流膀涣捏坡绚享迎约削猛团粤腋鳃肖毗森办纠侍操酣钳毗娇驴贷奋柱739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能template class SeqQueue T data MaxSize;/存放队列元素存放队列元素 in

33、t front,rear;/队头和队尾指针队头和队尾指针public:SeqQueue();/构造函数，置空队构造函数，置空队 void EnQueue(T x);/将元素将元素x入队入队 T DeQueue();/将队头元素出队将队头元素出队 T GetQueue();/取队头元素取队头元素 bool Empty();/判断队列是否为空判断队列是否为空;1队列的顺序存储结构队列的顺序存储结构敲袜碟捷宁捻靡吭碉待律禄囱途颤宜恬邵些裁权乓西迈缚氛擒庐蕴欺袱怯739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中

34、小学图书室育人功能n 进队时队尾指针进队时队尾指针 rear=rear+1，将新元素按，将新元素按 rear 指示位置加入。指示位置加入。n n 出队时队头指针出队时队头指针 front=front+1，再将下标为，再将下标为 front 的元素取出。的元素取出。n 思考：上图中，元素再进队，将如何？思考：上图中，元素再进队，将如何？虑得绑杜陶尾永营呈盂贡皱栋失牛赫丹贷马张像化俘历羌撮担募寥葛俯厌739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能出现出现“假上溢假上溢”现象现象 解决办法

35、解决办法:将存储数据元素的一维数组看成是头尾将存储数据元素的一维数组看成是头尾相接的循环结构相接的循环结构即即循环队列循环队列 胆驰隅庭乡九峪挪拆存霞舀肯汤纳蹲谩苦杨八黔勿骇狐张泼择宛耿鼓逼牧739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能循环队列的进队和出队队头指针队头指针:front=(front+1)%maxSize;队尾指针队尾指针:rear=(rear+1)%maxSize;队列初始化：队列初始化：front=rear=0;淮瘪各屎南雅屿疟武霉韵垃捻膜权封柏尹赵娃娠恨番垒谣澄

36、茸坞削角磊噬739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能循环队列的队空队满问题循环队列的队空队满问题为了方便起见，约定：为了方便起见，约定：初始化建空队时，令初始化建空队时，令front=rear=0,当队空时：当队空时：front=rear 当队满时：当队满时：front=rear 亦成立亦成立 因此，只凭等式因此，只凭等式front=rear 无法判断队空还是队满。无法判断队空还是队满。誓研辊薛淬负窃茧丝李祥臃镶九斯践师俱茨赡帮蛰遗窘拖季渝肤泌桃攀筐739-第三章 栈和队列73

37、9-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能有三种方法处理上述问题：有三种方法处理上述问题：浪费一个单元。当使用浪费一个单元。当使用MaxSize-1个单元个单元时即认为是队满时即认为是队满,此时此时 (rear+1)%MaxSize=front 设置一个布尔变量设置一个布尔变量flag。当。当flag=flase时时为空，当为空，当flag=true时为满。时为满。使用一个计数器记录队列中元素的个数。使用一个计数器记录队列中元素的个数。如如num，当，当num=0时队空，时队空，当当num=MaxSize时

38、队满。时队满。亢仍焚司耍喧逊壳溅食筑谗游感诗炎陋棺晤喘玄神斩哺附废喜忧糕殊勘勺739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2队列的链式存储结构队列的链式存储结构攘惭莆克晌号抒案奉孙宴栋赋碱光蔼幢请骄藤刃专孪键惋酉呐跪孵宦墩给739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能template class LinkQueueprivate:Node*front,*rear;pub

39、lic:LinkQueue();/构造函数构造函数 LinkQueue();/析构函数析构函数 void EnQueue(T x);/将元素将元素x入队入队 T DeQueue();/将队头元素出队将队头元素出队 T GetQueue();/取链队列的队头元素取链队列的队头元素 bool Empty();/判断链队列是否为空判断链队列是否为空;冒晃创则川咕围体伊撑醒卿斟人甭隶户冉葛乙眨可而船氛妙嘛代浦颇人谚739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.7 队列的操作算法队列的操作

40、算法 1循环队列的操作循环队列的操作 2链队列的操作链队列的操作霉痕烹渺剁氮允耿拉殿毋疼韧频余彰讶胰甘蓖顷祖曳溃畅痞漠烽跑哀富韵739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1循环队列的操作循环队列的操作（1）循环队列的初始化）循环队列的初始化template SeqQueue:SeqQueue()front=rear=0;刹贬缕模弥玛弹啤任禾亿撬辙洼煌酝粉消由孰碧锦玖星霸潍改婴亲晚鼠汀739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十

41、九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）循环队列的入队操作）循环队列的入队操作template void SeqQueue:EnQueue(T x)if(rear+1)%MaxSize=front)cerr上溢上溢;exit(1);rear=(rear+1)%MaxSize;datarear=x;队尾处插入元素队尾处插入元素升且举床阉榔横迟丫涉天喉嚏揪孙窗汤号图逼林荤窒析卯桌哈火剃馅闺宁739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（3）循环队列的出队操作）

42、循环队列的出队操作template T SeqQueue:DeQueue()if(rear=front)cerr下溢下溢;exit(1);front=(front+1)%MaxSize;return datafront;礁锁菱言环籍囊叶咨延议斟鼻墅萌遁布棱酗秒簧楚睡疾罩砷蛀嫡贱樱濒柴739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（4）判断循环队列是否为空）判断循环队列是否为空template bool SeqQueue:Empty()return rear=front;尺捕疮蜡驻股所

43、濒诚摈吓双恶狂账吻径裕畅抽短削蹄遗浴沼噎册作掣险敢739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2链队列的操作链队列的操作(1)链队列的初始化链队列的初始化 template LinkQueue:LinkQueue()s=new Node;s-next=NULL;front=rear=s;伙餐阿玄拦慰晴克座狰牡品抖鲍邦渍购婶善决幅簇惧扯芹宏燃唉喉茧帚渍739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分

44、发挥中小学图书室育人功能（2）链队列入队操作）链队列入队操作template void LinkQueue:EnQueue(T x)s=new Node;s-data=x;s-next=NULL;rear-next=s;/将结点将结点s插入到队尾插入到队尾rear=s;/将队尾指针指向结点将队尾指针指向结点s 罕晨葱胸桑妥雏沂淀排频助贺蕊匙瘴钟匠砷揣朽地派纸镇莎敦堡脯惭狱忙739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(3)链队列的出队操作链队列的出队操作 template T Li

45、nkQueue:DeQueue()if(rear=front)cerrnext;x=p-data;front-next=p-next;if(p-next=NULL)rear=front;delete p;return x;彻日舌厦颂启材里山佣贞寄募紫藤佛珐幕衅驶不裸爱诸潭迂彻到辗擦屎施739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.8 队列的应用示例队列的应用示例（1）问题描述）问题描述设有设有n个人排成一列，从前往后个人排成一列，从前往后“0，1”连续报连续报数。凡是报到数。凡是

46、报到“0”的人出列，凡是报到的人出列，凡是报到“1”的人立即站到队伍的最后。反复进行报数，直的人立即站到队伍的最后。反复进行报数，直到所有人均出列为止。要求给出这到所有人均出列为止。要求给出这n个人的出个人的出列顺序。列顺序。例如，例如，n=5时，初始序列为时，初始序列为1、2、3、4、5，出队序列为出队序列为1、3、5、4、2。讳听噎胺哨遁假久急形特西殖阶娇入赡澜窿重皋治澄卓逾毙掳库株斑仙泳739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）数据结构的设计）数据结构的设计 将将n个

47、人排成的队伍用队列模拟。个人排成的队伍用队列模拟。采用链队列存储结构。采用链队列存储结构。（3）算法的设计）算法的设计 实质上是一个反复出队和入队的问题，实质上是一个反复出队和入队的问题，即凡是报到即凡是报到“0”的人出列，凡是报到的人出列，凡是报到“1”的人入队，直至队列为空。的人入队，直至队列为空。懊傍伐钥傅害苫淹庚溯华纪板竭旨想屋缅忙讹镶还泳侧钟蚂凸磅庇账谈诀739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法的基本思想是：算法的基本思想是：反复执行以下步骤，直至队列为空。反复执

48、行以下步骤，直至队列为空。将队头元素出队，并输出其编号。将队头元素出队，并输出其编号。若队列不空，则再出队一个元素，若队列不空，则再出队一个元素，并将该元素再次入队。并将该元素再次入队。劳件歇爱旭邑笑轻枢躺妖蚕戎所典笛矫讶皑荫啪最咳除址希砒成理痉捆蔼739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能void Number()LinkQueue linkq;for(i=1;i=n;i+)linkq.EnQueue(i);while(!linkq.Empty()x=linkq.DeQueue

49、();coutx;/报到报到0的人出列的人出列if(!linkq.Empty()/报到报到“1”的人到队伍的最后的人到队伍的最后y=linkq.DeQueue();linkq.EnQueue(y);土菏腐俗旭友撞闯免尊垣着磺俺誊镣霍单遁戊频羔敝恋贪武超汾撅俄锻也739-第三章 栈和队列739-第三章 栈和队列为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能本本 章章 小小 结结（1）理解栈和队列的特点及它们的差异。）理解栈和队列的特点及它们的差异。（2）掌握顺序栈和链栈的定义及操作。）掌握顺序栈和链栈的定义及操作。（3）掌握循环队列和链队列的定义及操作。）掌握循环队列和链队列的定义及操作。（4）掌握栈和队列的应用。）掌握栈和队列的应用。请贼硼径堰哆拧锌圭拉与受河马溶啦热和睹扩笨殴抬嫉孵祷酌码倒娶坑刹739-第三章 栈和队列739-第三章 栈和队列