数据结构 第3章 栈和队列ppt课件.ppt

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

1、第3章栈和队列9/15/20211主要内容栈队列这两种结构都是特殊的线性表9/15/202123.1栈3.1.1栈的定义栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。9/15/20213根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOu

2、t)的线性表，简称为LIFO表。没有元素时称为空栈9/15/20214ana1进入退出栈底栈顶详细的示意图见书P44的图3.1讨论输入序列为123的有关情况：反序：正序：其他9/15/20215课堂作业：1.把输入序列123经过栈的操作可能的所有结果进行讨论注意逻辑思维的规律思想方法9/15/202163.1.2　栈的运算1、初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2、进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3、出栈：POP(&S)删除栈

3、S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4、取栈顶元素：GETTOP(S)取栈S中栈顶元素。5、判栈空：EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。9/15/202173.1.3栈的抽象数据类型描述ADTStackisData：含有n个元素a1,a2,a3,…,an,按LIFO规则存放，每个元素的类型都为elemtype。Operation：Voidinistack(&s)//将栈S置为一个空栈(不含任何元素)VoidPush(&s,x)//将元素X插入到栈S中，也称为“入

4、栈”、“插入”、“压入”VoidPop(&s)//删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”Elemtypegettop(s)//取栈S中栈顶元素Intempty(s)//判断栈S是否为空，若为空，返回值为1，否则返回值为0Endstack9/15/202183.1.4顺序栈1、顺序栈的数据类型CONSTintmaxsize=maxlen;//定义栈的最大容量为maxlenStructseqstack{elemtypestack[maxsize];//将栈中元素定义为elemtype类型intto

5、p;//:指向栈顶位置的指针}9/15/202192、栈的五种运算（1）初始化栈voidinistack(seqstack&s){s.top=0;}9/15/202110（２）进栈voidpush(seqstack&s,elemtypex){if(s.top==maxsize-1}cout<<”overflow”;else{s.top++;s.stack[s.top]=x;}}9/15/202111（３）退栈voidpop(seqstack&s){if(s.top==0)cout<<”underflow”;el

6、ses.top--;}9/15/202112（４）取栈顶元素elemtypegettop(seqstacks){if(s.top==0){cout<<”underflow”;return0;}elsereturns.stack[s.top];}9/15/202113（5）判栈空否intempty(seqstacks){if(s.top==0)return1;elsereturn0;}9/15/2021143、栈的共享存储单元有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发

7、生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。9/15/202115两个栈共享存储单元可用如下C++语句描述：CONSTintmaxsize=maxlen;//maxlen为共享单元的最大长度Structduseqstack{elemtypestack[maxsize];inttop[2];//两个栈的栈顶指针………};9/15/202116（1）两个栈共享存储单元的进栈算法

8、voiddupush(duseqstack&s,elemtypex,intk)//将元素x进入到以S为栈空间的第k个栈中{if(s.top[0]+1==s.top[1])cout<<“overflow”elseif(k==0){s.top[0]++;s.stack[s.top[0]]=x;}else{s.top[1]--;s.stack[s.top[1]]=x;}}9/15/20211