《数据结构》栈与队列.ppt

第3章 栈与队列,3.1 栈与队列的应用背景 3.2 堆栈 3.3 队列 习题题,栈和队列是两种重要的线性结构。从数据结构的角度看，栈和队列也是线性表，其特殊性在于它们的运算要受到一定的限制，因此，可以称它们为运算受限线性表。它们在计算机领域中有广泛的应用。,3.1 栈与队列的应用背景,3.1 栈的应用背景 在实际应用中，许多问题的分解的步骤和求解的步骤次序恰好相反，这是栈具有广泛应用背景的客观基础。 在“进制数转换”问题中，当A进制数转换为B进制数时，首先得到的是B进制数的末位，以后才能逐步得到其余高位数字。 在“函数调用关系”问题中，我们会发现编程中的最基本现象，函数的调用关系中隐含了一个函数调用栈结构。譬如A函数调用B函数，B函数调用C函数，实际上调用次序是ABC，可完成次序是CBA。 类似问题还有：括号匹配问题、汉诺塔问题、迷宫问题、火车车厢重排问题等等。,3.2 队列的应用背景 现实世界中的排队问题无处不在，譬如人们去银行、电信营业厅、快餐厅、海关、医院、药房等服务行业办理业务都存在排队问题，甚至在生产管理中，也存在生产任务的排队计划、管理。队列结构的应用背景就来源于此。 本章所讨论的队列基本结构、算法，是在计算机领域中模拟排队问题的基础。对这些基本知识的掌握及灵活运用，是在编程领域中解决排队问题的管理、决策的必要条件。,3.2 堆栈,3.2.1 栈的定义和基本运算 定义：栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示： 进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。 若有一个栈为空，首先，按a1,a2,an次序顺序进栈，然后，连续执行出栈操作，则可得到出栈序列的顺序是an,an-1,a2,a1。 我们经常将栈用下图3-1的形式描述,以后只能在最上面的书上加把图3.1想像成一个只在顶上开口的长方形容器，容器的底面积大小只能摆放一本书，我们要向该容器中放入新书，若容器为空，可从上向下放入第一本，以后只能在最上面的书上加。,栈又称为先进后出线性表(Last In First Out),简称为LIFO表。把栈看成一个只在顶上开口的长方形容器，容器的底面积只能放一本书，要向该容器中放入新书，若容器为空，从上向下放入第一本，,栈的基本操作有： (1)初始化一个空栈(Stack_Init)。 (2)进栈(将一个结点进栈Stack_Push)。 (3)出栈(从栈顶取一个结点Stack_Pop)。 (4)取栈顶元素(Stack_GetTop)。 (5)判断栈是否为空(Stack_Empty)。 (6)判断栈是否为满(Stack_Full)。 出栈操作与取栈顶元素的区别是，后者只取出栈元素的值，而数据元素不出栈。,3.2.2 栈的表示和实现 栈和线性表一样，也有两种存储结构。即顺序存储结构和链式存储结构。 (1)顺序存储结构 (a)静态顺序栈结构。用C语言描述如下: #define MAX 100 typedef struct int stackMAX; int top; SStack;,说明： stack数组用于存放栈中元素，称为栈空间，MAX为栈的最大容量，top为栈顶指针。top的取值需要设定严格的规则，如top值为栈顶元素的下标，或下一个进栈元素的下标。本书采用的规则是top的取值是下一个进栈元素的下标。该规则也为大多数教材所采纳。在初始化空栈时，top=0，其意义是第一个进栈的数据元素存于stack0中。,(b)动态顺序栈结构。在静态顺序栈结构中，我们一定能感觉到栈最大容量MAX的局限性：在栈空间stack数组中必然存在空间浪费现象。克服这种缺点的一种途径是采用动态顺序栈结构。结构定义如下： typedef struct int *stack; int top; DStack;,由于在定义时，未开辟栈空间，因此在初始化空栈时，可以根据栈应用的实际情况，动态申请栈空间。这是该结构为何称为动态顺序栈结构的原因。申请n个int元素的栈空间的语句为： stack=(int )malloc(n*sizeof(int); 在栈应用中，发现栈空间不够，需要再增加delta个元素空间，实现语句为： stack=(int *)realloc(n+delta)*sizeof(int); 动态顺序栈结构操作也稍微麻烦了些。为便于重点掌握栈的基本操作，以下程序讨论主要在静态顺序栈结构上展开。,(c)静态栈的状态及变化。 设栈顶指针top的取值是下一个进栈元素的下标，则： 栈空的条件为：top=0; 栈满的条件为：top=MAX; 即下一个进栈元素的位置已超出了栈空间的地址范围。 数据元素e进栈：若栈满，则不能进栈；若栈不满，首先将e送到stacktop栈单元，然后top加1，即top指向存储下一次进栈的元素存储位。 数据元素出栈：若栈空，则不能出栈；若栈不空，首先top减1，然后取出原先的栈顶元素stacktop。 图3.2展示了静态顺序栈中数据元素和栈顶指针之间的对应关系。,(d)进栈/出栈算法。运算主要有进栈和出栈 算法3.1 静态顺序存储结构的进栈算法。 /* 将进栈元素e压入栈S中 */ int SStack_Push(SStack *S, int e) if(S-top=MAX) return(0); /* 超出了地址范围,失败 */ S-stackS-top=e; S-top+; return(1); /* 成功 */ 算法3.2 静态顺序存储结构的出栈算法。 /* 出栈元素的值存于*e之中 */ int SStack_Pop(SStack *S, int *e) if(S-top=0) return(0); /* 超出了地址范围,失败 */ S-top-; *e=S-stackS-top; return(1); /* 成功 */ 以上两个算法都可能调整栈S的内容，鉴于C语言参数传递的单向性，所以采用栈S的地址作为参数。,(2)共享空间的两个栈结构 定义： 栈的使用非常广泛，经常会在一个程序中需要同时使用多个栈。为了不因栈上溢而产生错误中断，必须给每一个栈预分一个较大的空间，但这并不容易做到，因为每个栈实际所使用的空间难以估计。而另一方面，栈的实际容量在使用期间是不断变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一些栈还是空栈。为此，采用多个栈共享同一空间，该空间可以用一个大数组表示。如图3.3所示。,数据存储结构：两个栈共享一个数组的定义如下： #define MAX 100 typedef struct int stackMAX; int top1,top2; SStack2; *stack数组是两个栈共同使用的空间 *top1为栈1的栈顶指针 *top2为栈2的栈顶指针 *初始：两个栈为空栈top1=0和top2=MAX-1。 *栈1进栈时，将要进栈的数据元素送到top1所指的数组单元，然后top1加1； *栈2进栈时，将要进栈的数据元素送到top2所指的数组单元，然后top2减1。,进栈和出栈算法如下： 共享进栈算法。 算法3.3 顺序存储结构下，共享进栈算法。 /* 栈1的进栈算法 */ int SStack2_Push1(SStack2 *S, int e) if(S-top1S-top2) return(0); /* 超出了地址范围,失败 */ S-stackS-top1=e; S-top1+; return(1); /* 成功 */ /* 栈2的进栈算法 */ int SStack2_Push2(SStack2 *S, int e) if(S-top1S-top2) return(0); /* 超出了地址范围,失败 */ S-stackS-top2=e; S-top2-; return(1); /* 成功 */ ,共享出栈算法 算法3.4 顺序存储结构下，共享出栈算法。 /* 栈1的出栈算法,出栈元素的值存于*e之中 */ int SStack2_Pop1(SStack2 *S, int *e) if(S-top1=0) return(0); /* 超出了地址范围,失败 */ S-top1-; *e=S-stackS-top1; return(1); /* 成功 */ /* 共享栈2的出栈算法,出栈元素的值存于*e之中 */ int SStack2_Pop2(SStack2 *S, int *e) if(S-top2=MAX-1) return(0);/*超出了地址范围,失败 */ S-top2+; *e=S-stackS-top2; return(1); /* 成功 */ ,3.链式存储结构 定义:当栈采用线性链表作为存储结构时，称为链栈。链栈的表示形式是链表的首指针，其进栈、出栈操作就是在表头增加、删除结点，由于进栈、出栈是最常用的操作，使得链栈的表示频繁变更，必然带来参数传递的负担，所以本书约定链栈具有特殊头结点。变化形式如图3.4所示。,数据结构 struct linkstack int data; /* 为简化代码，设栈中数据元素为整数 */ struct linkstack *next; ; typedef struct linkstack LinkStack;,(a)链栈 (b)进栈 (c)出栈 图3.4 链栈及插入和删除操作,进栈/出栈算法 算法3.5 进栈算法。将数据元素e压入链栈S中。对于链栈而言，只有在系统资源耗尽时，才可能出现申请空间失败的情形。 int LinkStack_Push(LinkStack *S, int e) LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack); if(p=NULL) return(0); /* 系统资源耗尽，失败 */ p-data=e; p-next=S-next; S-next=p; return(1); /* 成功 */ ,算法3.6 出栈算法。 int LinkStack_Pop(LinkStack *S, int *e) LinkStack *p; if(S-next=NULL) return(0); /* 空栈,失败 */ *e=S-next-data; p=S-next; S-next=p-next; free(p); return(1); /* 成功 */ ,3.2.3 栈的应用 (1)进制数的转换 例3.1十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。在此采用栈依次存放所求的余数，然后从栈中依次取出，即得到转换后的十进制数。 算法3.7 十进制数转换算法。 void conversion(int dec,int oct) Stack_Init(S); /* 初始化一个栈 */ for(; dec!=0; dec=dec/8) Stack_Push(S, dec%8); /* 进栈次序是个位、十位. */ for(i=0; !Stack_Empty(S); i+) octi=Stack_Pop(S); /* 先出栈者是高位，最后是个位 */ ,(2)表达式求值的算法 在表达式中存在多个算符优先级和括号优先级，所以，在运算中要解决优先级后才能进行运算。优先级的顺序是： (1)括号的优先级最高，对括号内的各种运算符有：先乘除，再加减，同级运算从左至右。 (2)先括号内，后括号外，多层括号，由内向外。 在每一个运算步，相邻的算符c1和c2之间的关系是下面三种情况之一(c1出现在c2之前)。 c1c2 c1的优先级大于c2 运算符有算术运算符、左右括号、算式结束符。表3.1定义了算符之间的优先关系。,注意：“#”为优先级最低的算符，是表达式结束符，为算法简洁，在表达式最左边也虚设一个“#”构成整个表达式的一对括号，当“#”=“#”表示整个表达式求值完毕。,算法的基本思想是： (a)定义一个存放算符栈OPTR和存放数据栈OPND。 (b) 首先置数据栈为空栈，表达式起始符“#”为算符栈的栈底元素。 (c) 自左向右扫描表达式，读到操作数进OPND栈，读到运算符，则和OPTR栈顶元素比较(栈顶元素为c1，读到的算符为c2)；若c1c2，则将c1 出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND。重复直到表达式求值完毕(OPTR栈为空栈)。,按上面的说明，可将队列中插入元素的操作描述为： if (q-rear = MAXSIZE - 1) printf(queue full); else q-rear +; q-dataq-rear = x ; 队列中删除元素的操作描述为： if (q-front = q- rear) printf (queue empty); else q-front+; 上面的顺序队列在操作中存在着如下问题：例如当q-front = q-rear = 4时，队列为空，但插入新元素只能从当前rear指针指向的位置开始插入，前面,的单元无法利用。更有甚者，当q-rear = MAXSIZE - 1时，队满条件出现，不能再插入新元素，但当前队列可能并不满，而是假满现象。又如当q-front = q-rear = MAXSIZE - 1 时，虽为队空，但不能再插入新元素，要做一次队列置空操作后才能工作。产生这些现象的原因是被删除元素的空间在该元素删除以后就永远使用不到了。解决这一问题的常用方法是：将向量q-data从逻辑上构筑成一个头尾相接的圆环，即q-data0接在q-dataMAXSIZE - 1之后，并将这种逻辑含义下的向量称为循环向量，此队列称为循环队列，如图4.6所示。循环队列仍然是顺序队列结构，只是逻辑上和前面的顺序队列有所不同。,为使两个算符比较方便，给算符设置优先级如表3.2所示。其中c1 为栈内元素，c2为栈外元素。算符比较算法如下：,表3.2 算符优先级设置,算法3.8 算符比较算法。 char Precede(char c1,char c2) char c_temp1, c_temp2; switch (c1) case * : case / :c_temp1=4; break; case + : case - :c_temp1=2; break; case ( :c_temp1=0; break; case ) :c_temp1=5; break; case # :c_temp1=-1; switch (c2) case * :,case / :c_temp2=3; break; case + : case - :c_temp2=1; break; case ( :c_temp2=5; break; case ) :c_temp2=0; break; case # :c_temp2=-1; if (c_temp1c_temp2) return(); ,算法3.9 表达式求值算法。 int express( ) Stack_Init(OPTR)；Stack_Push(OPTR, #); /* 运算符栈 */ Stack_Init(OPND)； /* 运算数栈 */ w=getchar(); while(w!= #| Stack_GetTop(OPTR)!= #) /* #是表达式结束的标记，也是运算符栈为空的标记 */ if(!In(w,OP) Stack_Push(OPND,w);w=getchar(); /* 不是运算符的情况 else /* 判断运算符栈顶元素和新输入运算符的优先权 */ switch(Precede(Stack_GetTop(OPTR),w) case : /* 栈顶元素优先权高 */ op=Stack_Pop(OPTR); b=Stack_Pop (OPND); a= Stack_Pop(OPND); /* a是第一运算数，b是第二运算数 */ Stack_Push(OPND,Operate(a,op,b); break; return(Stack_GetTop(OPND); ,3.3 队列,3.3.1 队列的定义和运算 与栈一样，队列也是线性表的重要的特例，也是运算受限线性表，若限制对表的插入只能在一端进行，而删除在另一端进行，就称此线性表为“队列”。队列的插入在线性表的表尾进行，称表尾端为“队尾”，而删除在线性表的表头进行，称表头端为“队头”。若线性表为空表称为空队列。向队列里增加一个结点称为“结点入列”，从队列中删除一个结点称为“结点出列”。队列中结点出列的顺序和入列的顺序完全相同，所以，队列又称为“先进先出的线性表FIFO”，如图3.7所示。,队列的基本运算有以下几种： (1)初始化一个空队列。队头指针等于队尾指针的队列 (Squeue_Init)。 (2)入列操作。在队列中增加一个结点(Squeue_Enter)。 (3)出列操作。从队列中删除一个结点(Squeue_Leave)。 (4)取队列首结点。取队头结点的值(Squeue_GetTop)。,3.3.2 队列的存储结构 队列是线性表的一种特例，所以，队列的存储结构和线性表相同，也有顺序存储结构和链式存储结构两种方式。从便于编程调试的角度出发，我们设队列中的数据元素类型为int型。 (1)顺序存储结构. (a)队列的顺序存储结构定义如下： #define MAX 100 typedef struct int queueMAX; int front,rear; SQueue;,说明： a. queueMAX用于顺序依次存储队列中的元素. b. MAX表示队列允许的最大容量. c. front表示队头元素的位置，称为队头指针。指向队头元素的前一个位置. d. rear表示队尾元素的位置，称为队尾指针。指向队尾元素的位置。,g. 出列运算是：front+； 队列空的条件：front=rear,e. 队列为空的是front=rear，初始空队列front=rear=-1,f. 入列运算是：rear+；queuerear=e； 队列满(上溢)的条件：rear=MAX-1；,(b)顺序存储结构队列的运算 算法3.11 出队列运算 int Squeue_Enter(SQueue *Q, int e) if(Q-rear=MAX-1) return(0); /* 超出了地址范围,失败 */ Q-rear+; Q-queueQ-rear=e; return(1); /* 成功 */ 算法3.12 出队列运算 int Squeue_Leave(SQueue *Q, int *e) /* 空队列,失败 */ if(Q-rear=Q-front) return(0); Q-front+; *e=Q-queueQ-front; return(1); /* 成功 */ ,(c)“假溢出”现象 现象：按上述算法，分析下图的情形，此时： rear = MAX-1 显然不能进行入列操作。但队列中实际容量并非最大，这种现象称为“假溢出”。,解决方法：假溢出的对策是将数组设想为循环数组，即queue MAX-1的后续为queue0，这样，队列变成循环队列。,图3.9 循环队列示意图,在图3.9的循环队列中。 初始时，队列空的标志为： front=rear=0 入列运算是：rear=(rear+1)%MAX 出列运算是：front=(front+1)%MAX 队列为空：front=rear 队列为满为：(rear+1)%MAX=front(数组中还有一个剩余空间时，队列为满),(a)满队列 (b)空队列,算法实现： 算法3.13 初始化算法。 void Squeue_Init(SQueue *Q) Q-rear=Q-front=0; 算法3.14 循环队列的入列算法。 int Squeue_Enter(SQueue *Q, int e) if(Q-rear+1)%MAX=Q-front) return(0); /*队列满*/ Q-rear=(rear+1)%MAX; Q-queueQ-rear=e; return(1); /* 成功 */ 算法3.15 循环队列的出列算法。 int Squeue_Leave(SQueue *Q, int *e) if(Q-rear=Q-front) return(0); /* 空队列,失败 */ Q-front=(Q-front+1)%MAX; *e=Q-queueQ-front; return(1); /* 成功 */ ,(2)链式存储结构 在对线性表的讨论中可知，对于应用中数据元素变动较大的数据结构，采用链式存储结构更有利。 (a)链式结构定义 struct LQueueNode int data; struct LQueueNode *next; ; 将链队列的头、尾指针封装为以下的链队列结构： typedef struct struct LQueueNode *front; struct LQueueNode *rear; LinkQueue;,图3.10为链队列。头指针front指向队头和尾指针rear指向队尾。为了操作方便起见，也给链队列增加一个头结点，并令头指针front指向头结点。由此，空的链队列的判决条件为头指针front和尾指针rear均指向头结点。在对带有头结点的链队列操作时，建立一个空队列是需初始化，即置front=rear且等于头结点的地址；在正常出列操作时，尾指针不变；但当出列操作后，队列为空时，要修改队尾指针，使rear = front。入列操作是申请一个结点，数据域赋x，指针域赋NULL，再将该结点链结到队尾，同时，使队尾指针指向该结点。,(a)链队列 (b)空队列,图3.10 带头结点的链队列,(b)链队列的算法 算法3.16 初始化算法。 说明：在对带有头结点的链队列操作前，首先需要初始化。即申请头结点，并置front、rear共同指向头结点。 int LinkQueue_Init(LinkQueue *Q) Q-front=(struct LQueueNode *)malloc(sizeof(struct LQueueNode); if(Q-front=NULL) return(0); /* 申请空间失败 */ Q-rear=Q-front; Q-fornt-next=NULL; return(1); /* 成功 */ ,算法3.17 链式队列的入列算法。 说明：入列操作需要申请一个新结点；然后赋值；再将该新结点链接 到队尾；最后调整队尾指针指向该结点。 int LinkQueue_Enter(Link