《数据结构栈和队列ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构栈和队列ppt课件.ppt（45页珍藏版）》请在三一办公上搜索。
1、数据结构课程的内容,3.1 栈（Stack）,第三章 栈和队列,3.2 队列（Queue）,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,1.定义,3.1 栈,与同线性表相同，仍为一对一关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶(表尾)运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。,限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）,问：堆栈是什
2、么？它与一般线性表有什么不同？,3.1 栈,答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈逻辑结构：一对一 逻辑结构：一对一存储结构：顺序表、链表 存储结构：顺序栈、链栈运算规则：随机存取 运算规则：后进先出(LIFO),“进”压入=PUSH（x)“出”弹出=POP(y),栈 是仅在表尾进行插入、删除操作的线性表。表尾(即 an 端)称为栈顶 top;表头(即 a1 端)称为栈底base,例如：栈 s=(a1,a2,a3,.,an-1,an),a1 称为 栈底元素 an 称为 栈顶元素,插入元素到栈顶（即表尾
3、）的操作，称为入栈。从栈顶（即表尾）删除最后一个元素的操作，称为出栈。,教材P44对栈有更详细定义：,强调：插入和删除都只能在表的一端（栈顶）进行！,顺序栈示意图,表和栈的操作区别对线性表 s=(a1,a2,.,an-1,an),写入：vi=ai读出：x=vi,压入：PUSH(an+1)弹出：POP(x),前提：一定要预设栈顶指针top！,an+1,入栈操作例如用堆栈存放（A，B，C，D）（注意要遵循“后进先出”原则）,A,A,CBA,BA,核心语句：top=L;,顺序栈中的PUSH函数status Push(ElemType x)if(topM)上溢 else vtop+=x;,Push(B
4、);,Push(C);,Push(D);,低地址L,Push(A);,高地址M,B,C,D,出栈操作例如从栈中取出B（注意要遵循“后进先出”原则）,核心语句：Pop();Pop();Printf(Pop();,顺序栈中的POP函数status Pop()if(top=L)下溢 else y=v-top;return(y);,例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。,435612中到了12顺序不能实现；1354
5、26可以实现。,例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,答：,答：,例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入3、2出，即132；1、2入，2出，3入3出，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合计有5种可能性。,补充1：若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的栈入栈口诀
6、：堆栈指针top先压后加（vtop+=x）；出栈口诀：堆栈指针top先减后弹（y=v-top)。,3.1 栈,补充2：栈不存在的条件：base=NULL;栈为空 的条件：base=top;栈满的条件：top-base=stacksize;,补充3：链栈 链栈示意图,链栈的入栈函数、出栈函数（以头指针为栈顶，在头指针处插入或删除！）,公共说明部分：typedef struct snode SElemType data;struct snode*link;NODE;NODE*st,*p;int m=sizeof(NODE);,Push(SElemType x)p=(NODE*)malloc(m);
7、if(!p)上溢else p-data=x;p-link=st;st=p;,Status pop()if(st=NULL)下溢elsey=st-data;p=st;st=st-link;free(p);return(y);,链栈入栈函数,链栈出栈函数,插入表头,从表头删除,链栈不必设头结点，因为栈顶（表头）操作频繁；采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,说 明,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。,答：,数制转换（十转N）P4
8、8 设计思路：用栈暂存低位值例2：括号匹配的检验P49 设计思路：用栈暂存左括号例3：表达式求值 P52 设计思路：用栈暂存运算符例4：汉诺仪（Hanoi）塔P55 设计思路：用栈实现递归调用,例1：,例3 表达式求值(这是栈应用的典型例子)这里，表达式求值的算法是“算符优先法”。,例如：3*（7 2）（1）要正确求值，首先了解算术四则运算的规则：a.从左算到右 b.先乘除，后加减 c.先括号内，后括号外 由此，此表达式的计算顺序为：3*（7 2）=3*5=15,（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2，都要比较优先权关系。算符优先法所依据的算符间的优先关系见教
9、材P53表3.1（是提供给计算机用的表！）由表可看出，右括号)和井号#作为2时级别最低；由c 规则得出：*，/，+，-为1时的优先权低于（，高于）由a规则得出：（=）表明括号内运算，已算完。#=#表明表达式求值完毕。,栈的应用（表达式求值）,（3）算法思想：设定两栈：操作符栈 OPTR，操作数栈 OPND栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符#；依次读入字符：是操作数则入OPND栈，是操作符则要判断：if 栈顶元素 操作符，则退栈、计算，结果压入OPND栈；栈顶元素=操作符且不为#，脱括号（弹出左括号）；栈顶元素操作符，压入OPTR栈。,栈的应用（表
10、达式求值）,栈的应用（表达式求值）,Status EvaluateExpression(OperandType/EvaluateExpression,此函数在哪里？,定 义,3.2 队列,与同线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。基本操作有入队或出队，建空队列，判队空或队满等操作。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）,队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾即 an
11、端，称为 队尾；表头即 a1 端，称为队头。它是一种先进先出（）的线性表。,例如：队列 Q=(a1,a2,a3,.,an-1,an),插入元素称为入队；删除元素称为出队。,队头,队尾,教材P59对队列有更详细定义：,队列的抽象数据类型定义见教材5960队列的存储结构为链队或顺序队（常用循环顺序队）,链队列示意图,讨论：空队列的特征？,怎样实现入队和出队操作？入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：front-next=p-next;,完整动作设计参见教材P61-62,队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,构造一
12、个空队列Status InitQuene(LinkQuene,2)销毁队列Status DestroyQuene(LinkQuene,3)入队Status EnQuene(LinkQuene,4)出队Status DeQuene(LinkQuene,顺序队示意图,(队尾),(队首),队列会满吗？很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。,空队列的特征？约定：front=rear,队尾后地址,入队(尾部插入)：vrear=e;rear+;出队(头部删除)：x=vfront;front+;,讨论：,假溢出,有缺陷,怎样实现入队和出队操作？,3.2 队列,问：什么叫“假溢出”？如何
13、解决？,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,3.2 队列,解决假溢出的途径采用循环队列,循环队列（臆造）,顺序队列,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前 front=rear 使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，令队满特征为front=(rear+1)%N；,队空条件:front=rear(初始化时：front=rear)队满条件：front=(r
14、ear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,问3：在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,5,问2：左图中队列长度L=？,问1：左图中队列容量 maxsize N=？,6,注意：循环队列中的“长度”到底是指总长度还是数据元素个数？答：一般情况下的长度（L）是指元素个数（不含头结点或空闲单元），而maxsize N 才是指所有单元总 数，即“容量”。,例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可
15、知，队头和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，rear=4。,例2：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（）rf（）（nfr）%n（）nrf（）（nrf）%n,4种公式哪种合理？当 r f 时（A）合理；当 r f 时（C）合理；,分析：,综合2种情况，以（D）的表达最为合理,例3：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先，后。,移动队首指针,取出元素,问：为什么要设计
16、队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）；操作系统中多道作业的处理（一个CPU执行多个作业）；3.简化程序设计。,答：,循环队列的操作实现见教材P64,循环队列的操作实现,1）初始化一空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间 设置队列为空队列，即 front=rear=0（也可为任意单元，如 2，或 4）;,算法：,Status InitQueue(SqQueue,新开单元的地址为0则表示内存不足,算法说明：向循环队列的队尾插入一个元素分 析：(1)插入前应当先判断队列是否满 if(q.rear+1)%QUEUE_MAXSIZE)=q.front
17、)return ERROR;(2）插入动作 q.base q.rear=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;,2）入队操作,Status EnQueue(SqQueue,2）入队操作（完整函数）,3）出队操作,算法说明：删除队头元素，返回其值 e 分 析：（1）在删除前应当判断队列是否空；if(q.front=q.rear)return ERROR;（2）插入动作分析；因为队头指针front指向队头元素的位置，所以：e=q.base q.front;q.front=(q.front+1)%QUEUE_MAXSIZE;,Status DeQueue(SqQueue/DeQueue,算法：,讨论（代本章小结）,线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,
