数据结构 第3章 栈和队列

《数据结构 第3章 栈和队列》由会员分享，可在线阅读，更多相关《数据结构 第3章 栈和队列（35页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 栈和队列栈和队列栈和队列是两种特殊的线性表，是操作受限的 线性表，称为限定性数据结构。 3.1 栈（stack） 一、栈的定义和特点 v 定义：栈(Stack)是限制在表的一端进行插入和删除运算 的线性表，通常称插入、删除的这一端为栈顶(Top)，另一 端为栈底(Bottom)。当表中没有元素时称为空栈。 v 假设栈S=(a1，a2，a3，,an)，则a1称为栈底元素，an为 栈顶元素。栈中元素按 a1，a2，a3，an的次序进栈，退栈 的第一个元素应为栈顶元素。换句话说，栈的修改是按后进 先出的原则进行的。因此，栈称为后进先出表（LIFO）。 v 特点：先进后出（FILO）或后

2、进先出（LIFO）。第三章第三章 栈和队列栈和队列在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执 行，因此必须用栈来保存函数中中断的地址，以便调用返回时能从断点继续往 下执行。 例 设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c， 其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况。主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态， 进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数 a处于挂起状态，进入函数b中执行，函数b中调用函数c， 留下一个断点地址t 进栈， 然后函数b处于挂起状态，进入函数c中执行

3、，函数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)

4、删除栈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)toptoptoptoptop123450A

5、BCDEFtoptoptoptoptoptop栈空第三章第三章 栈和队列栈和队列顺序栈的存储结构描述#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表示堆栈，

6、入栈的元素值为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”);

7、return(0);stop-;return(1); 第三章第三章 栈和队列栈和队列2、链栈链栈的存储结构描述typedef struct nodeelementtype data;struct node *next;stacknode *linkstack; 第三章第三章 栈和队列栈和队列实现.topdatalink栈底.栈底toptopxptop.栈底 topp入栈过程：出栈过程：栈顶第三章第三章 栈和队列栈和队列1m栈1底栈1顶栈2底栈2顶3.在一个程序中同时使用两个栈（共享栈）有时，一个程序设计中，需要使用多个同一类型的栈,这时候 ，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空

8、间 过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存 储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一 个足够大的存储空间，让多个栈实现存储空间优势互补。常采用将两个栈底设在可用空间的两端。仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对 每个栈可用的最大空间就可能大于整个可用空间的一半m/2。第三章第三章 栈和队列栈和队列例：一个双向栈是将两个栈用一个数组构成，它们的栈底分 别设在数组的两端。当一个栈中元素的数目小于n/2时，另一 个栈相应的可以大于n/2。试分析以数组高端为底的栈的入栈 和出栈的情况。这个栈的栈顶指针top2是按相反的方向移动的，因此算法有所不同：

9、 入栈时为：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)允许插入的

10、一端 l队头(front)允许删除的一端a1 a2 a3.an 入队出队frontrear 队列Q=(a1,a2,an)第三章第三章 栈和队列栈和队列v特性：队列是一种运算受限制的线性表，元素的添加在表的一 端进行，而元素的删除在表的另一端进行。允许添加元素的一端称为队尾（Rear）；允许删除元素 的一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队 。 新入队的元素只能添加在队尾，出队的元素只能是删除 队头的元素，队列的特点是先进入队列的元素先出队，所 以队列也称作先进先出表或FIFO（First-In-First-Out） 表。 第三章第三章 栈和队列栈和队列二、

11、队列的基本运算队列可定义如下五种基本运算： 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队头队尾r

12、ear设队首、队尾指针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 基本操作实现：

13、出队算法 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(

14、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设两个指

15、针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