资源预览内容
第1页 / 共35页
第2页 / 共35页
第3页 / 共35页
第4页 / 共35页
第5页 / 共35页
第6页 / 共35页
第7页 / 共35页
第8页 / 共35页
第9页 / 共35页
第10页 / 共35页
亲,该文档总共35页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三章第三章 栈和队列栈和队列栈和队列是两种特殊的线性表,是操作受限的 线性表,称为限定性数据结构。 3.1 栈(stack) 一、栈的定义和特点 v 定义:栈(Stack)是限制在表的一端进行插入和删除运算 的线性表,通常称插入、删除的这一端为栈顶(Top),另一 端为栈底(Bottom)。当表中没有元素时称为空栈。 v 假设栈S=(a1,a2,a3,,an),则a1称为栈底元素,an为 栈顶元素。栈中元素按 a1,a2,a3,an的次序进栈,退栈 的第一个元素应为栈顶元素。换句话说,栈的修改是按后进 先出的原则进行的。因此,栈称为后进先出表(LIFO)。 v 特点:先进后出(FILO)或后进先出(LIFO)。第三章第三章 栈和队列栈和队列在函数嵌套调用中,一个函数的执行没有结束,又开始另一个函数的执 行,因此必须用栈来保存函数中中断的地址,以便调用返回时能从断点继续往 下执行。 例 设有一个主程序,它调用函数a,函数a又调用函数b,函数b又调用函数c, 其中r,s,t分别表示中断地址,我们可以用一个栈来描述调用情况。主程序调用函数a,留下一个断点地址r进栈,然后主函数处于挂起状态, 进入函数a中执行,函数a中再调用函数b,留下一个断点地址s进栈,然后函数 a处于挂起状态,进入函数b中执行,函数b中调用函数c, 留下一个断点地址t 进栈, 然后函数b处于挂起状态,进入函数c中执行,函数c执行完后,要返回 断点处继续执行,但返回到那一个断点呢?根据栈顶元素来决定。返回时,执 行退栈操作,先退出t,故返回t断点继续执行, 接着退栈退出s,故返回s断点 继续执行,接着退栈退出r,返回r断点继续执行,最后栈为空,算法结束。第三章第三章 栈和队列栈和队列第三章第三章 栈和队列栈和队列ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈的示意图第三章第三章 栈和队列栈和队列二、栈的运算1.初始化栈:INISTACK(S)将栈S置为一个空栈(不含任何元素)。2.进栈:PUSH(S,X)将元素X插入到栈S中,也称为 “入栈”、 “插入”、 “压入”。3.出栈: POP(S) 删除栈S中的栈顶元素,也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素: GETTOP(S)取栈S中栈顶元素。5.判栈空: EMPTY(S)判断栈S是否为空,若为空,返回值为1,否则返回值为0。第三章第三章 栈和队列栈和队列三、栈的存储结构 1、顺序栈 实现:一维数组sMtop=-1123450 栈空栈顶指针top,指向实际栈顶 后的空位置,初值为-1top123450 进栈Atop出栈栈满BCDEF设数组维数为M top=-1,栈空,此时出栈,则下溢(underflow) top=Maxsize-1,栈满,此时入栈,则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空第三章第三章 栈和队列栈和队列顺序栈的存储结构描述#define Maxsizetypedef structelementtype skMaxsize;int top;seqstack *s;n Sski表示第i个进栈的元素n S skS top表示栈顶元素n 当S top =-1表示空栈n 当S top = Maxsize-1表示栈满第三章第三章 栈和队列栈和队列操作算法操作算法 入栈(入栈(pushpush)入栈的主要操作是先将栈顶指针加1;然后将入栈元素放到栈顶指针所指示下标值的位置上。设用下标从0到maxsize-1的数组Sk表示堆栈,入栈的元素值为x ,则可得到入栈函数如下: int push_stack(seqstack *s;elementtype x) if (stop= = sMaxsize-1)printf(“out of space!n”);return(0);stop+;sskstop=x;return(1); 第三章第三章 栈和队列栈和队列出栈(出栈(PopPop)出栈运算时,先将栈顶的元素值赋给某个变量,以备后面的运算 应用;然后栈顶指针减1,将栈顶位置下移。出栈的函数如下: int pop_stack(seqtstack *s) if (stop= =-1)printf(“no element!n”);return(0);stop-;return(1); 第三章第三章 栈和队列栈和队列2、链栈链栈的存储结构描述typedef struct nodeelementtype data;struct node *next;stacknode *linkstack; 第三章第三章 栈和队列栈和队列实现.topdatalink栈底.栈底toptopxptop.栈底 topp入栈过程:出栈过程:栈顶第三章第三章 栈和队列栈和队列1m栈1底栈1顶栈2底栈2顶3.在一个程序中同时使用两个栈(共享栈)有时,一个程序设计中,需要使用多个同一类型的栈,这时候 ,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间 过大,造成大量存储单元浪费的现象。 为了充分利用各个栈的存 储空间,这时可以采用多个栈共享存储单元,即给多个栈分配一 个足够大的存储空间,让多个栈实现存储空间优势互补。常采用将两个栈底设在可用空间的两端。仅当两个栈顶相遇时,才产生上溢,即所有可用空间已用完。对 每个栈可用的最大空间就可能大于整个可用空间的一半m/2。第三章第三章 栈和队列栈和队列例:一个双向栈是将两个栈用一个数组构成,它们的栈底分 别设在数组的两端。当一个栈中元素的数目小于n/2时,另一 个栈相应的可以大于n/2。试分析以数组高端为底的栈的入栈 和出栈的情况。这个栈的栈顶指针top2是按相反的方向移动的,因此算法有所不同: 入栈时为:top2=top2-1 出栈时为:top2=top2+1 两个栈在进栈过程中防止溢出的条件是:top2=top1+1 。 出栈过程中防止下溢出及判断空栈的条件分别为: top1=0,top2=(n+1)。第三章第三章 栈和队列栈和队列 3.2 栈的应用 表达式求值例 计算 2+4-3*6操作数运算符24 # 操作数运算符6# 操作数运算符6#36 -操作数运算符6#18操作数运算符-12+-*- #第三章第三章 栈和队列栈和队列 3.4 队列(Queue) 一、队列的定义及特点 v 定义:队列是限定只能在表的一端进行插入,在表的另一端 进行删除的线性表 l队尾(rear)允许插入的一端 l队头(front)允许删除的一端a1 a2 a3.an 入队出队frontrear 队列Q=(a1,a2,an)第三章第三章 栈和队列栈和队列v特性:队列是一种运算受限制的线性表,元素的添加在表的一 端进行,而元素的删除在表的另一端进行。允许添加元素的一端称为队尾(Rear);允许删除元素 的一端称为队头(Front)。向队列添加元素称为入队,从队列中删除元素称为出队 。 新入队的元素只能添加在队尾,出队的元素只能是删除 队头的元素,队列的特点是先进入队列的元素先出队,所 以队列也称作先进先出表或FIFO(First-In-First-Out) 表。 第三章第三章 栈和队列栈和队列二、队列的基本运算队列可定义如下五种基本运算: 1初始化队列 INIQUEUE(Q)将队列Q设置成一个空队列。 2入队列 ENQUEUE(Q,X) 将元素X插入到队尾中,也称“进队” ,“插入”。 3出队列 DLQUEUE(Q) 将队列Q的队头元素删除,也称“退队”、“删除”。 4取队头元素 GETHEAD(Q) 得到队列Q的队头元素之值。 5判队空 EMPTY(Q) 判断队列Q是否为空,若为空返回1,否则返回0。第三章第三章 栈和队列栈和队列 三、队列的存储结构 1、链队列链队列需要队头和队尾两个指针来确定;给链队列添加个头 结点,并令头指针指向头结点。 v 结点定义头结点.front队头队尾rear设队首、队尾指针front和rear, front指向头结点,rear指向队尾第三章第三章 栈和队列栈和队列v链队列描述: Typedef struct QsNodeelemtype data;struct QsNode *next; Qsnode *Qnodeptr; Typedef structQNodePtr front;QNodePtr rear; LinkQueue;第三章第三章 栈和队列栈和队列frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队第三章第三章 栈和队列栈和队列 v 基本操作实现: 出队算法 int DeQueue(LinkQueue *Q)Qsnode *p;if(Qfront= =Qrear) return 0;p=Qfrontnext;x=pdata;Qfrontnext=pnext;if(Qrear= =p) Qrear=Qfront;free(p);return 1; 删除时的三种情形: a.删除前已空; b.删除前只有一个结点,删除后为空队列; c.其他情形(删除前结点数1)第三章第三章 栈和队列栈和队列入队算法 Int InQueue(LinkQueue *Q,elemtype e) QNodePtr P;p=(QNodePtr)malloc(sizeof(Qsnode); if(p= =NULL) return 0;pdata=e;pnext=NULL;Qrearnext=p;Qrear=p;return 1; 第三章第三章 栈和队列栈和队列2、队列的顺序存储结构 v描述: #define Maxsize Typedef structelemtype elemmaxsize;int front;int rear;int S; SqQueue;第三章第三章 栈和队列栈和队列v实现:用一维数组实现front=0 rear=0123450 队空frontJ1,J1,J3入队J1J2J3rearrearJ4,J5,J6入队J4J5J6front设两个指针front,rear,约定: rear指示队尾元素下一个位置; front指示队头元素 初值front=rear=0rearrearfrontrearJ1,J2,J3出队J1J2J3frontfrontfront第三章第三章 栈和队列栈和队列v基本操作: 初始时:front=rear=0 空队列条件:front=rear 出队时:IF rear=front THEN ERROR(队空)ELSE Qfront= Qfront+1 入队时:IF rear=maxsize-1 THEN ERROR(队满)ELSE QelemQrear=x; Qrear= Qrear+1;第三章第三章 栈和队列栈和队列v存在问题 设数组维数为M,则: l当front=0,rear=Maxsize-1时,再有元素入队发生溢出真溢出 l当front0,rear=Maxsize-1时,再有元素入队发生溢出假溢出Maxsize-10QrearQfront此时,Qrear=maxsize-1 且队满 。真溢出Maxsize-10QrearQfront此时,尽管Qrear=maxsize-1,但 队列中实际元素并不足maxsize个, 仍有Qfront个空闲单元,称这种 情形为“假溢出”。第三章第三章 栈和队列栈和队列 v循环队列 v基本思想:把队列设想成环形,让sq
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号