升本第3章栈和队列

《升本第3章栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学习要求：掌握栈和队列的特点理解顺序栈的实现、满空条件、两栈共享掌握循环队列、链队列的算法，满空条件会利用栈和队列的思想解决实际问题。第三章栈和队列3.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。（举例，电

2、梯，公车）3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize

3、];inttop;}seqstack;考点：栈顶1、(20041分)栈顶的位置是随着____________操作而变化.top6543210-1例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P44anan-1a2a1……栈顶栈底1、置空栈voidinitstack(seqstack*s){s–>top=-1;}2、判断栈空intstackempty(seqstack*s){return(s–>top==-1);}3、判断栈满intstackfull(seqstack*s){return(s–>top==stacksize-1);}4、进栈voidpush(seqstack*s，da

4、tatypex){if(stackfull(s))error(“stackoverflow”);s–>data[++s–>top]=x;}5、退栈datatypepop(seqstack*s){if(stackempty(s))error(“stackunderflow”);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}例：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B

5、出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB考点：出栈次序1、若进栈序列为3，5，7，9不可能的出栈次序为_______。（20061分,2007）A7539B9753C7593D95732、进栈序列为1、2、3、4、5、…..n，出栈次序为P0、P1、…Pi…、Pn-1,已知P0=n,则Pi=_______。（2007）两个栈共享空间0maxsize-1lefttoprighttop考点：两栈共享1、为了增加内存的利用率，可以让两个顺序栈共享一块连续的内存空间，应将两个栈的______分别设置在这片空间的两端。当______时候才会出现栈满。3.2栈的应

6、用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。栈的应用举例-----数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：nndiv8nmod8134816841682102125202voidconversion(){initstack(s);scanf(“%”,n);while(n){push(s,n%8);n=n/8;}while(!Stacke

7、mpty(s)){pop(s,e);printf(“%d”,e);}}栈的应用举例－－表达式计算中缀表达式：A+(B–C/D)×E后缀表达式：ABCD/－E×+后缀表达式特点1、与相应的中缀表达式中的操作数次序相同2、没有括号3.4队列3.4.1抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物