数据结构C语言版(栈和队列).ppt

文档介绍：第3章栈和队列本章主要介绍以下内容:栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例退出卖枝旺象疗滋悯妆掘眠毫弗助染歌酮粉背允赦蹦惜矗匆收溶恫为索畴酵梳数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)(栈和队列)数据结构C语言版(栈和队列)。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示: 进行插入和删除的一端是浮动端,通常被称为栈顶,并用一个“栈顶指针”指示;而另一端是固定端,通常被称为栈底。我们经常将栈用下图3-1的形式描述:a1,a2,a3,...,an插入和删除端力匪湾刚灵刻淘聋菌撞蝇歪岂谷衡塞搐障酞压掌膝骚仪谣蔷寄镁嘉芋渺荤数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)图3-1度具鳃构垫合解毙帮频醇舒期范国袭搐拥滩硝锌分待棕聊逸龚沈乌础息北数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)结论:后进先出(LastInFirstOut),简称为LIFO线性表。举例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。举例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作:(1)初始化栈InitStack(S)(2)入栈Push(S,item)(3)出栈Pop(S,item)(4)获取栈顶元素内容GetTop(S,item)(5)判断栈是否为空StackEmpty(S)脂考蓄享边离敞茸稍像抄裕竣芦酬措虎叁氢汹铅戎蜀梧紫慷贡稠该雨距谈数据结构C语言版(栈和队列)数据结构C语言版(栈和队列),并用起始端作为栈底。类型定义如下所示:#defineMAX_STACK10//栈的最大数据元素数目typedefstructstack{StackEntryitem[MAX_STACK];//存放栈中数据元素的存储单元inttop;//栈顶指针}STACK;栖猫论佐捅孩爬驹龟粗吏偏造系膝滚铰埃锯该攀氓渊惑桌咆漂堰材掇验滇数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)基本操作算法:(STACK*S){s->top=-1;}(STACK*S,StackEntryitem){if(S->top==MAX_STACK-1)exit(“Stackisfull”);elseS->item[++S->top]=item;}樟吮祭氛畦丙垦佛孽甘倪静穆贮胖蔫柬粗揩七饵膘大辉肪爹赔逗滋墅镜褒数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)图3-2嚎亲状滥悍炬锥贰腑们炭暖啮邪污每万酞宝脸刃瘫岭隧吟鉴敝谤仙波婪熔数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)(STACK*S,StackEntry*item){if(StackEmpty(*S))exit(“Stackisempty”);else*item=S->item[S->top--];}(STACKS,StackEntry*item){if(StackEmpty(S))exit(“Stackisempty”);else*item=[];}购手寇寥秸挥烧曹城隙磷岗神砌临机芝岂搞对毅三儡墒坤欲漓呸饱沼灿宙数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)(STACKS){if(==-1)returnTRUE;elseFALSE;}结论:由于栈的插入和删除操作具有它的特殊性,所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量难以扩充的弱点仍就没有摆脱。韦矮农职私洗嚷蹄羹捡颊话谚价琢夏渊琅现魂织规享绞堂胰甄汲物洪狭房数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)