chapter03栈和队列.ppt

《chapter03栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章堆栈和队列StackandQueue一摞叠放好的盘子,上好子弹的弹匣排队等车的队列它们的状态是不断变化的（数据结构扩大或者缩减）添加和删除是它们共同的操作与其他数据结构最大的不同是：他们的添加和删除局限在特定的位置。堆栈和队列堆栈（Stack）队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式本章内容3.1堆栈一、堆栈的基本概念定义堆栈是限定只能在表的一端进行插入和删除的线性表。在表中允许插入和删除的一端叫做栈顶(top)；表的另一端则叫做栈底(base

2、)。出栈或退栈入栈或进栈a0a1…an-2an-1basetopLastInFirstOut一般线性表逻辑结构：一对一存储结构：顺序表、链表运算规则：随机存取堆栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出(LIFO)堆栈与一般线性表的比较例一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，1出即231；④1、2入，2、1出，3入3出，即213；⑤1、2

3、、3入，3、2、1出，即321；合计有5种可能性。*不可能产生的输出序列：3121、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空二、堆栈的操作三、栈的顺序表示和实现——顺序堆栈1.顺序栈的存储结构出栈或退栈入栈或进栈basetopa0a1a3a4a5maxsize-1543210顺序栈的定义typedefintdatatype;#definemaxsize100/*顺序堆栈数组最大存储单元个数*/typedefstruct/*顺序栈定义*/{datatypedata[maxsize];/*顺序堆栈存放数据元素的数组*/inttop

4、;/*顺序堆栈的当前栈顶位置*/}seqstack;/*结构类型名*/2.顺序堆栈的操作实现toptopa0a1a2toptopmaxsize个空栈a0进栈a1进栈a2进栈a2出栈top初始化参数：S是指向结构变量的指针；功能：建一个空栈S；voidinit(seqstack*s){seqstack*s=newseqstack;s->top=-1;returns;}判栈空操作参数：s是存放结构体变量的数组；功能：判断s是否为空，为空返回1，否则返回0；intempty(seqstacks){if(s.top==-1)return1;els

5、ereturn0;}入栈功能：将数据元素x压入顺序堆栈S，入栈成功返回1，否则返回0intpush(seqstack*s,datatypex){if(s->top==maxsize-1){printf(“Stackisfull”);return0;}s->top++;s->stack[s->top]=x;return1;}判栈满？栈顶下标加1入栈出栈功能：弹出顺序堆栈s的栈顶数据元素值到参数d，出栈成功返回1，否则返回0判栈空？元素出栈栈顶下标减1else{*d=s->stack[s->top];(s->top)--;return1;

6、}}intpop(seqstack*s,datatype*d){if(s->top==-1){printf("Stackisempty!");return0;}取栈顶元素功能：取顺序堆栈s的当前栈顶数据元素值到参数d，成功返回1，否则返回0intgettop(seqstacks,datatype*d){if(s.top==-1){printf(“Stackisempty!”);return0;}else{*d=s.stack[s.top];return1;}}两个堆栈共享空间目的：节省空间扩展知识——堆栈共用问题两个堆栈共享空间的

7、运算：初始化进栈出栈a0…aiaj…am0maxsize-1LeftTopRightTop…数据结构定义：typedefstruct{datatypestack[maxsize];intLeftTop;intRightTop;}dqstack;初始化算法voidInitiDqstack(dqstack*s);{s->LeftTop=-1;s->RightTop=maxsize;}intPushDqstack(dqstack*s,charWhichStack,DataTypex){if(s->LeftTop>=s->RightTop-1){

8、printf(“栈满”);return0;}if(WhichStack!=‘L’&&WhichStack!=‘R’){printf(“出错”);return0;}if(WhichStack==