计算机软件就是基础 软件基础之数据结构-栈、队.ppt

《计算机软件就是基础 软件基础之数据结构-栈、队.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业:P1022.162.172.21(1,2)2.222.231第二章常用数据结构及其运算----栈与队2主要内容栈队列这两种结构都是特殊的线性表3栈栈的定义栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。4根据栈的定义可知，最先放入栈中的元素在栈底，最后放入栈中的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。没有元素时称为空栈5讨论

2、输入序列为123的有关情况：反序：正序：其他:ana1退出栈底栈顶6栈的运算1、初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2、进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3、出栈：POP(&S)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4、取栈顶元素：GETTOP(S)取栈S中栈顶元素。5、判栈空：EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。7栈的抽象数据类型描述ADTStackisData：含有n个元素a1,a2,a3,…,an,按LIFO规则存放，每个元素的类型都为elemtype

3、。Operation：Voidinistack(&s)//将栈S置为一个空栈(不含任何元素)VoidPush(&s,x)//将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”VoidPop(&s)//删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”Elemtypegettop(s)//取栈S中栈顶元素Intempty(s)//判断栈S是否为空，若为空，返回值为1，否则返回值为0Endstack8顺序栈1、顺序栈顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所

4、以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的.9用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#defineStackSize100typedefcharelemtype;typedefstruct{elemtypeStack[StackSize];inttop;}seqstack;10设S是seqstack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top

5、加1，退栈时需将s–>top减1。因此，s–>top<0表示空栈，s–>top=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件.11栈的五种运算（1）初始化栈voidinistack(seqstack*s){S->top=-1;}12a3a2a1a4a3a2a1a2a1a5a4a3a2a1toptoptoptoptop进栈退栈栈空栈满13（２）进栈voidpus

6、h(seqstack&s,elemtypex){if(S->top==maxsize-1)return0”;else{s->stack[++(s->top]=x;return1;}}14（３）退栈elemtypepopQstack(qstack*s){if(s->top<0)returnNIL;elsereturns->Stack[(s->top)--];}15（４）取栈顶元素elemtypegettopQstack(qstack*s){if(s->top<0)returnNIL;elsereturns->Stack[s->top];}16（5）判栈空否intNotemptyQstack(qs

7、tack*s){if(s->Top<0)return0;return1;}17几点说明：1.对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：s->top=MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。183、栈的共享存储单元有时，一个程序设计中，需要