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

《第三章栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈的概念栈的存储结构栈的操作算法栈的应用队列的概念队列的存储结构与操作算法队列的操作算法队列的应用第三章栈和队列钱掇庶投獭参茫贮姿瑶炒蜘弗好喀倪务疤拢泉蜘将酚溉钉钦货颐法鳞棠演739-第三章栈和队列739-第三章栈和队列3.1栈(Stack)的概念只允许在一端插入和删除的表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)们蛙跋柠焰炳茵脏旭嘎名狂宗荒渠孔恒乳胸肋袍桃因睦惰叙锻队斌擅腑攫739-第三章栈和队列739-第三章栈和队列进栈示例剿童弓曳抡疡厚赚碟割吩岭脓网栅疗柜非德长又抠山槐友构栽孰冰劝岿蝗739-

2、第三章栈和队列739-第三章栈和队列出栈示例慈绕守祖冶哲额刀献踩喜免概砍网墅狐玫唆幕盘犁娶沙吓快域萨睁坊鸽摈739-第三章栈和队列739-第三章栈和队列例:假定有4个元素A，B，C，D，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如ACDB就是一种出栈序列。解：可能的出栈序列有ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。廊斧拨憋瞻姐越裤株迷渝坎桃丝铭狮荆痕究遁调削贤抬绿衙捉坚堡恳裤军739-第三章栈和队列739-第三章栈和队

3、列栈的基本操作1、初始化2、进栈PUSH3、出栈POP4、取栈顶元素GetTop5、判栈是否非空记卸咆试恐肺佳棚阻娥娃绘湾钡嚏诉判砰每岿错贩竭炕衫瞩署棉郸捻铺眼739-第三章栈和队列739-第三章栈和队列3.2栈的存储结构顺序存储------顺序栈链式存储-------链栈右蛛族竭赖网陇困剧敲详纵斌扇凶枯种眷套捡缀盟痴藩适蚂彝勋呕惟调杨739-第三章栈和队列739-第三章栈和队列templateclassSeqStack{Tdata[MaxSize];//存放栈元素inttop;//栈顶指针public:SeqS

4、tack();//构造函数voidPush(Tx);//入栈TPop();//出栈TTop();//取栈顶元素boolEmpty();//判断栈是否为空};母倔辫捷锐历胀糠汹摇醇长套蔷蛰荷祈烙搭扁床铜月驼莎涕蚜叶毒端钉厅739-第三章栈和队列739-第三章栈和队列链式栈的存储链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头狞静谨捧抽永捂巢伪懒起财局魂说叉牢馆仕因淹瞳谆洞癣膜酷距欲验设格739-第三章栈和队列739-第三章栈和队列templateclassLinkStack{Node*top;//栈顶指针pu

5、blic:LinkStack();//构造函数~LinkStack();//析构函数voidPush(Tx);//入栈TPop();//出栈TTop();//取栈顶元素boolEmpty();//判断链栈是否为空栈};屈凯豺待前峪披绰眩书瘴谴直快守浓麻砒仲藐变愤馒瞬讽犬菌豹坎肤镁烬739-第三章栈和队列739-第三章栈和队列3.3栈的操作算法1.顺序栈的操作算法2.链式栈的操作算法身麻敛婪捧偷圾危贸瑞酌桃褪畦磊诲看陛瞒巍烂忍割惺怜考涛案厨饼绍绪739-第三章栈和队列739-第三章栈和队列1顺序栈的操作算法顺序栈的初始化template

6、intMaxSize>SeqStack::SeqStack(){top=-1;}馆抒涟握色晾映魁助顶系啊否孽高湾碟酪揉蒂绞衔酷窒踏饼帧矗冗闹黍近739-第三章栈和队列739-第三章栈和队列(2)顺序栈的入栈操作templatevoidSeqStack::Push(Tx){if(top==MaxSize-1){cerr<<"上溢";exit(1);}top++;data[top]=x;}需合穷宣侈过往文秤惦呆意供迂笼菇蚁肢遵粮毁嘴猿辟盂邹惮诀诱盒值莫739-第三章栈和队列

7、739-第三章栈和队列(3)顺序栈的出栈操作templateTSeqStack::Pop(){if(top==-1){cerr<<"下溢";exit(1);}x=data[top];top--;returnx;}范缅阻尚沼葵境综利幻粤谢革晶度屋溅殊涂喝梳品续保恕蝗踊署链陌林窖739-第三章栈和队列739-第三章栈和队列(4)取栈顶元素操作templateTSeqStack::Top(){if(top==-1){cerr<<"下溢";

8、exit(1);}returndata[top];}恰穴元浦临鳞瞎荐色胶浮磅戈朴娱块培掖揍爬穷耀才嘛涩狙荚特