数据结构DS03栈和队列.ppt
52页
§栈（栈（Stack）） §栈的应用栈的应用§队列（队列（Queue））§队列的应用队列的应用 第三章第三章 栈和队列栈和队列 定定 义义3.1 栈栈与线性表相同，数据元素之间仍为一对一的关与线性表相同，数据元素之间仍为一对一的关系用用顺序栈顺序栈顺序栈顺序栈或或链栈链栈链栈链栈存储均可存储均可只能在只能在栈顶栈顶栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进先出后进先出后进先出后进先出（（LIFOLIFO））或或先进后出先进后出先进后出先进后出（（FILOFILO））的原则关键是编写关键是编写入栈入栈入栈入栈、、出栈出栈出栈出栈等函数，具体实现按顺序等函数，具体实现按顺序栈或链栈的存储结构的不同而不同栈或链栈的存储结构的不同而不同存储结构存储结构运算规则运算规则实现方式实现方式 逻辑结构逻辑结构限定只能在表的限定只能在表的一端一端一端一端进行插入和删除运算的线进行插入和删除运算的线性表基本操作基本操作 建栈、判断栈满或栈空、入栈、出栈、读栈顶建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等元素值，等等 栈栈栈栈 是仅在是仅在表尾表尾进行插入、删除操作的线性表。
进行插入、删除操作的线性表表尾表尾( (即即 a an n 端端) )称为称为栈顶栈顶 ( (top) ; top) ; 表头表头( (即即 a a1 1 端端) )称为称为栈底栈底( (bottom)bottom)例如：例如： 栈栈 S S= (a1 , a2 , a3 , ……….,an-1 , an )插入元素到栈顶的操作，称为插入元素到栈顶的操作，称为入入栈栈栈栈从栈顶删除元素的操作，称为从栈顶删除元素的操作，称为出栈出栈a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素强调：强调：强调：强调：插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！ 栈的栈的基本操作基本操作•InitStackInitStack(S)(S)：： 构造一个空栈构造一个空栈S S•ClearStackClearStack(S)(S)：： 清除栈清除栈S S中的所有元素中的所有元素•StackEmptyStackEmpty(S)(S)：：判判断断栈栈S S是是否否为为空空，，若若为为空空，，则则返返回回 truetrue；；否则返回否则返回falsefalse•GetTopGetTop(S) (S) ：： 返回返回S S的栈顶元素，但不移动栈顶指针的栈顶元素，但不移动栈顶指针•Push(S, x) Push(S, x) ：：插入元素插入元素x x为新的栈顶元素（入栈操作为新的栈顶元素（入栈操作) )•Pop(S) Pop(S) ：： 删除删除S S的栈顶元素并返回其值（出栈操作）的栈顶元素并返回其值（出栈操作） 顺序栈的存储结构和操作的实现顺序栈的存储结构和操作的实现 顺序栈顺序栈: :是利用一组地址连续的存储单元依次存放从栈底到是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。
栈顶的数据元素在在在在C C C C语言中，预设语言中，预设语言中，预设语言中，预设一个数组的最大一个数组的最大一个数组的最大一个数组的最大空间空间空间空间, , , ,栈底设置在栈底设置在栈底设置在栈底设置在0 0 0 0下标端，栈顶随下标端，栈顶随下标端，栈顶随下标端，栈顶随着插入和删除元着插入和删除元着插入和删除元着插入和删除元素而变化，用一素而变化，用一素而变化，用一素而变化，用一个整型变量个整型变量个整型变量个整型变量toptoptoptop来来来来指示栈顶的位置指示栈顶的位置指示栈顶的位置指示栈顶的位置 a1 a2…… an顺序栈顺序栈S ai……0n栈底栈底栈顶栈顶toptop压入压入( (PUSH)PUSH)PUSH)PUSH): : : : S[S[++toptop]=]=a an+1n+1弹出弹出( ( POP)POP)POP)POP) : : : : e e e e=S=S=S=S[ [top top - -- -- -- -] ] 顺序栈存储结构的描述：顺序栈存储结构的描述：# #definedefine MaxsizeMaxsize 100 100 /*设顺序栈的最大长度为100，可依实现情况而修改*/typedef int datatypetypedef int datatype; ;typedef structtypedef struct{ { datatype datatype stack[ stack[MaxsizeMaxsize]; ]; int int top top；；；； /*栈顶指针*/} }SeqStackSeqStack；；；； /*顺序栈类型定义*/SeqStackSeqStack *s *s；；；； /*s为顺序栈类型变量的指针*/ 顺序栈的几种状态以及在这些状态下栈顶指针顺序栈的几种状态以及在这些状态下栈顶指针toptop和栈和栈中结点的关系中结点的关系 栈为空的条件栈为空的条件 ：： top==-1;top==-1;栈满的条件栈满的条件 ：： top==top==MaxsizeMaxsize-1-1 若入栈动作使地址向高端增长，称为若入栈动作使地址向高端增长，称为““向上生成向上生成””的栈；的栈；若入栈动作使地址向低端增长，称为若入栈动作使地址向低端增长，称为““向下生成向下生成””的栈；的栈； 对于向上生成的堆栈对于向上生成的堆栈: :入栈入栈：栈指针：栈指针top “top “先加后压先加后压” : ” : S[S[++top++top]=a]=an+1n+1出栈出栈：栈指针：栈指针top “top “先弹后减先弹后减”” : : e=S[e=S[top--top--] ]顺序栈的基本操作顺序栈的基本操作 构造一个空顺序栈构造一个空顺序栈 SeqStack *InitStack() { SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack));if(!S) {printf(“空间不足空间不足”)；； return NULL;}else {S->top=- -1; return S;}} 取顺序栈栈顶元素取顺序栈栈顶元素 datatype GetTop(SeqStack *S) {if (S->top== - -1) { printf("\n栈是空的栈是空的!"); return FALSE;} else return S->stack[S->top]; } 判别空栈判别空栈int StackEmpty(SeqStack *S) {if(S->top== - -1) return TRUE; else return FALSE; } 顺序栈的入栈操作顺序栈的入栈操作————例如用堆栈存放（例如用堆栈存放（A A，，B B，，C C，，D D））AACBABAtop核心语句：核心语句：顺序栈入栈函数顺序栈入栈函数PUSHPUSH（）（）SeqStack*Push(SeqStack*S，，datatype x) {if(S->top==Maxsize-1) return NULL;/*栈栈满满*/ else {S->top++; S->stack[S->top]=x; return s;} } Push (B);Push (C);Push (D);toptoptoptop低低地址地址LPush (A);高地址高地址MBCD 顺序栈出栈操作顺序栈出栈操作————例如从栈中取出例如从栈中取出‘‘B B B B’’DCBAtoptopDCABDCBAtopDCBAtop低低地址地址L高地址高地址MD核心语句：核心语句：Pop ( );顺序栈出栈函数顺序栈出栈函数POP()POP()datatype Pop( SeqStack *S) {if(S->top==- -1) /*栈空栈空*/ {printf("\nThe sequence stack is empty!"); return FALSE;} else {S->top- -; return S->stack[S->top+1];} } Pop ( );Printf( Pop () ); 链链 栈栈链栈的构造方式链栈的构造方式——用用top指向栈顶，只能在栈顶插入或删除。
指向栈顶，只能在栈顶插入或删除栈顶栈顶栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈toptop a1 a2an-1 annextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：Typedef struct node {datatype data; /*数据域数据域*/ struct node *next; /*指针域指针域*/ }LinkStack; LinkStack *top; /* top为为栈栈顶顶指指针针*/ 将将x x入栈，修改栈顶入栈，修改栈顶指针指针: :top=ptop=pa an n出栈，修改栈顶指出栈，修改栈顶指针针: :top=top->nexttop=top->next链栈的入栈操作和出栈操作链栈的入栈操作和出栈操作 LinkStack *Push((LinkStack *top，，datatype x) { LinkStack *p; p=( Linkstack *)malloc(sizeof(LinkStack)); p->data=x; p->next=top; top=p; return top;}链栈入栈操作链栈入栈操作 LinkStack *Pop( LinkStack *top) { LinkStack *q; if(!top) {printf("\n链栈是空的链栈是空的!");return NULL;} else {q=top; /*q指向要删除的栈顶结点*/ top=top->next; /*栈顶指针下移*/ free(q); /*释放q指向结点空间*/ return top; } }链栈出栈操作链栈出栈操作 1、、数制转换（十进制数数制转换（十进制数N N转换为转换为r r进制数进制数）） 设计思路：用栈暂存余数（低位值）设计思路：用栈暂存余数（低位值）2、、括号匹配问题括号匹配问题 设计思路：用栈暂存左括号设计思路：用栈暂存左括号3、、子程序的调用子程序的调用 设计思路：用栈暂存指令地址设计思路：用栈暂存指令地址4、、逆置一个单链表逆置一个单链表 设计思路：用栈暂存每一结点的数据设计思路：用栈暂存每一结点的数据3.2 栈的应用举例栈的应用举例 例例3.2 将十进制整数转换成二至九之间的任一进将十进制整数转换成二至九之间的任一进制数输出制数输出 将一个十进制数将一个十进制数43274327转换成八进制数转换成八进制数(10347)(10347)8 8：： ⑴⑴ 当当N≠0N≠0，，将将N%rN%r压压入栈入栈s s中；中；⑵⑵ N/r N/r ⇒⇒ N N；；⑶⑶ 若若N N＞＞0 0，，则则重重复复⑴⑴、、⑵⑵两两步步；；若若N=0N=0，，则则将将栈栈s s的内容依次出栈。
的内容依次出栈解题解题思路如下：思路如下：void conversion(int N, int r){ int x=N,y=r;SeqStack *s; s=InitStack(); while(N!=0) { Push(s, N %r ); N=N/r ; }printf(“\n十十进进制制数数%d所所对对应应的的%d进进制制数数是是:”，，x,y);while(!StackEmpty(s)) printf(“%d”,Pop(s));printf(“\n”);} 例例3.5 3.5 利用一个顺序栈将一个带头结点的单链表利用一个顺序栈将一个带头结点的单链表（（a1, ,a2, ,…, ,an）（）（其中其中n>=0n>=0））逆置为（逆置为（an, ,an-1, ,……，，a1） 1 1、、建建立立一一个个带带头头结结点点的的单单链链表表headhead；；2 2、、输出该单链表；输出该单链表；3 3、建立一个空栈、建立一个空栈s s（（顺序栈）顺序栈）；；4 4、依次将单链表的数据入栈；、依次将单链表的数据入栈；5 5、、依依次次将将单单链链表表的的数数据据出出栈栈，，并并逐逐个个将将出出栈栈的的数数据据存存入入单单链链表的数据域（自前向后）表的数据域（自前向后）; ;6 6、再输出单链表。
再输出单链表 解题解题思路如下：思路如下：linklist*backlinklist(linklist *head) {linklist *p; p=head->next; initstack(); while(p) {push(&s, p->data); p=p->next ; } p=head->next; while(!stackempty(s)) {p->data=pop(&s); p=p->next; } return (head);}； 3.3 队列队列 与线性表相同，仍为一对一关系与线性表相同，仍为一对一关系顺序存储方式：顺序队列顺序存储方式：顺序队列( (循环队列循环队列) )和链式和链式存储方式：存储方式：链队列链队列只能在队尾入队、队头出队，并遵循只能在队尾入队、队头出队，并遵循先进先先进先出出（（FIFOFIFO））的原则关键是掌握关键是掌握入队入队和和出队出队操作，具体实现按存操作，具体实现按存储方式的不同储方式的不同( (顺序队列或链队列顺序队列或链队列) )而不同存储结构存储结构存储结构存储结构运算规则运算规则运算规则运算规则实现方式实现方式实现方式实现方式 逻辑结构逻辑结构逻辑结构逻辑结构只能在表的一端进行插入运算，在表的另一只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
端进行删除运算的线性表基本操作基本操作基本操作基本操作 入队、出队、建空队列、判队空或队满等入队、出队、建空队列、判队空或队满等尾部插入尾部插入头部删除头部删除队列定义队列定义队列定义队列定义 队列队列 （（QueueQueue））是仅在是仅在表尾表尾进行插入操作、在进行插入操作、在表头表头进行删除操进行删除操作的线性表它是一种先进先出作的线性表它是一种先进先出（ＦＩＦＯ）（ＦＩＦＯ）的线性表的线性表例如：队列例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an )在队尾插入元素称为在队尾插入元素称为入队入队入队入队；在队首删除元素称为；在队首删除元素称为出队出队出队出队队首队首队尾队尾 队列的队列的队列的队列的实现方式实现方式实现方式实现方式是本节重点，是本节重点，是本节重点，是本节重点，关键是掌握关键是掌握入队入队和和出队出队等等等等操作 具体实现按具体实现按存储结构存储结构的不同（的不同（顺序队列顺序队列或或链队列链队列）而）而不同 队列的基本操作队列的基本操作（（1 1））InitQueueInitQueue(Q)(Q)：： 构造一个空队列构造一个空队列Q Q（（2 2））QueueEmptyQueueEmpty(Q)(Q)：： 判断队列是否为空判断队列是否为空 （（3 3））QueueLengthQueueLength(Q)(Q)：：求队列的长度求队列的长度 （（4 4））GetHeadGetHead(Q)(Q)：： 返回返回Q Q的队头元素，不改变队列状态的队头元素，不改变队列状态 （（5 5））EnQueueEnQueue(Q,x)(Q,x)：： 入队列：插入元素入队列：插入元素x x为为Q Q的新的队尾元素的新的队尾元素 （（6 6））DeQueueDeQueue(Q)(Q)：： 出队列：删除出队列：删除Q Q的队头元素的队头元素（（7 7））ClearQueueClearQueue(Q)(Q)：： 清除队列清除队列Q Q中的所有元素中的所有元素 链队列类型定义：链队列类型定义： typedef struct { Qnode *front ; /*队头指针*/ Qnode *rear ; /*队尾指针*/ }LinkQueue; LinkQueue *q; /*q是链队列指针,其中封装了队头指针和队尾指针*/链队列链队列链队列链队列结点类型定义：结点类型定义： typedef Struct Qnode { datatype data; /*数据域*/ Struct Qnode *next; /*指针域*/ }Qnode; 链队列的几种状态示意图：链队列的几种状态示意图：此时，front==rear修改rear指针修改头结点的指针域①①链队列为空的特征：链队列为空的特征：front==rearfront==rear②② 链队列会满吗链队列会满吗？？一般不会，因为删除时有一般不会，因为删除时有freefree动作，除非内存不足！动作，除非内存不足！修改rear指针 入队（尾部插入）：入队（尾部插入）：rear->next=S; rear->next=S; rear=S; rear=S;出队（头部删除）：出队（头部删除）：front->next=front->next->next;front->next=front->next->next;③③ 怎样实现链队列的怎样实现链队列的入队入队操作操作和出队和出队操作？操作？ 假设假设S S所指所指结点为入队结点，则有结点为入队结点，则有 LinkQueue *InitQueue() {LinkQueue *q; /*q为链队列指针,q中封装了队头指针和队尾指针*/ Qnode *p; /*p为指向链队列结点的指针*/ Q=(LinkQueue*)malloc(sizeof(LinkQueue)); p=(Qnode*)malloc(sizeof(Qnode)); p->next=NULL; q->front =q->rear=p; return q; }构造一个空链队列构造一个空链队列构造一个空链队列构造一个空链队列 datatype GetHead(LinkQueue *Q) {if(Q->front==Q->rear) {printf(“\n链队列为空!”); return FALSE;} else return Q->front->next->data； /*返回队头元素的值*/ }取链队列的队头元素取链队列的队头元素取链队列的队头元素取链队列的队头元素 void EnQueue(LinkQueue *Q，，datatype x) { Qnode *p; /*p为指向链队列结点的指针*/ p = (Qnode *)malloc(sizeof(Qnode))；； p->data = x；； p->next = NULL；； Q->rear->next = p；； Q->rear=p；； } 链队列的入队操作链队列的入队操作链队列的入队操作链队列的入队操作 datatype DeQueue(LinkQueue *Q) { Qnode *p; /*p为指向链队列结点的指针*/ datatype x; if (Q->front ==== Q->rear) {printf("队列为空，无法删除！队列为空，无法删除！"); return FALSE;} else {p = Q->front->next；； /*p指向链队列的队头结点*/ x = p->data；； /*将队头元素的值赋给变量x*/ Q->front->next = p->next；； /*出队列，修改队头指针*/ if(Q->rear == p) Q->rear=Q->front；； /*若出队列后队列为空， 则还应当修改队尾指针，使队尾指针指向头结点*/ free(p)；； /*释放空间*/ return x; /*返回已出队元素（即原队头元素）的值*/ } }链队列的出队操作链队列的出队操作链队列的出队操作链队列的出队操作 循环（顺序）队列的类型定义：循环（顺序）队列的类型定义：#define MAXSIZE 100 /* 最大队列长度 */typedef structtypedef struct{ datatype data[MAXSIZE]；； /* 存储队列的数据空间 */ int front；； /* 队头指针，若队列不空，则指向队头元素 */ int rear；； /* 队尾指针，若队列不空，则指向队尾元素的下一个位置 */}SeqQueue; 头、尾指针与队列中元素之间的关系示意图：头、尾指针与队列中元素之间的关系示意图： 入队操作时的尾指针运算入队操作时的尾指针运算: rear=(rear+1)%Maxsize出队操作时的头指针运算出队操作时的头指针运算: front=(front+1)%Maxaize问题：问题：在循环队列中，由于队空时有在循环队列中，由于队空时有front==rear；；队满时也有队满时也有front==rear；；因因此我们无法通过此我们无法通过front==rear来来判断队列是判断队列是““空空””还是还是““满满””。
循环队列示意图循环队列示意图循环队列的几种状态循环队列的几种状态 循环队列空的条件循环队列空的条件 : : front = =rear循环队列满的条件循环队列满的条件：： front == (rear+1) % MAXSIZE循环循环队列长度为队列长度为：：L=（（rear－－front +MAXSIZE））% MAXSIZE J2 J3J1 J4 J5frontrear解解决决办办法法：：少少用用一一个个元元素素空空间间，，约约定定以以““队队头头指指针针在在队队尾尾指指针针的的下下一一位位置置(指指环环状状的的下下一一位位置置)””作作为为队队列列““满满””的的标标志志也也就就是是说说，，若若数数组组的的大大小小是是MAXSIZE，，则则该该数数组组所所表表示示的的循循环环队队列列最最多多允允许许存存储储MAXSIZE-1个个结点注意：结点注意： rear所指的结点始终为空所指的结点始终为空循环队列满的示意图：循环队列满的示意图： 经过约定后的循环队列操作示意图 （p.70，图3.13改） 循环队列的基本操作实现循环队列的基本操作实现以创建队列、入队和出队三种基本操作为例以创建队列、入队和出队三种基本操作为例1 1、构造（初始化）一个空队列、构造（初始化）一个空队列算法要求：生成一空队列算法要求：生成一空队列算法步骤：算法步骤： ① ①为队列分配存储空间；为队列分配存储空间； ② ②设置队列为设置队列为空队列空队列，其特征为：，其特征为： front=rear=0front=rear=0 构造一个空队列构造一个空队列qSeqQueue *InitQueue(){ SeqQueue *q；； q=(SeqQueue *)malloc(sizeof(SeqQueue))；； /* 开辟一个足够大的存储队列空间 */ q->front = q->rear = 0；； /* 将队列头尾指针置为零 */ return q；； /* 返回队列的首地址 */} 算法说明：向循环队列的队尾插入一个元素。
算法说明：向循环队列的队尾插入一个元素分分 析析：：(1)(1)入队入队前应当先判断队列是否已满？前应当先判断队列是否已满？ if((q->rear+1)% if((q->rear+1)% MaxsizeMaxsize) )====q->front)q->front) return false; return false;(2)(2)入队入队动作如下动作如下: : q->data[q->rear] = x; q->data[q->rear] = x; q->rear=(q->rear+1)% q->rear=(q->rear+1)% MaxsizeMaxsize; ;2 2、入队操作、入队操作 int EnQueue(SeqQueue *q, datatype x){ if((q->rear+1)％％MAXSIZE==q->front) {printf(“\n循环队列满循环队列满!”); return FALSE;} q->data[q->rear] = x；； q->rear = (q->rear+1)%MAXSIZE; return TRUE;}循环队列入队操作循环队列入队操作 3 3、、出队操作出队操作算法说明：删除循环队列的队头元素，返回其值算法说明：删除循环队列的队头元素，返回其值 x x。
分分 析：析： （（1 1））在在出队出队前应当判断队列是否为空？前应当判断队列是否为空？ if (q->frontif (q->front====q->rear) return false;q->rear) return false; （（2 2））出队出队动作动作如下如下: : x= q->data[q->front]; x= q->data[q->front]; q->front=(q->front+1)% q->front=(q->front+1)% MaxsizeMaxsize; ; datatype DeQueue(SeqQueue *q){ datatype x; if (q->front = = q->rear) {printf(“\n循环队列空！不能做删除操作！循环队列空！不能做删除操作！”); return FALSE;} x = q->data[ q->front ]；； q->front = (q->front+1)％％MAXSIZE；； return x；；}循环队列出队操作循环队列出队操作 3.4 队列的应用队列的应用1 1 1 1、打印杨辉三角形、打印杨辉三角形、打印杨辉三角形、打印杨辉三角形2 2、迷宫问题：寻找一条从迷宫入口到出口、迷宫问题：寻找一条从迷宫入口到出口的最短路径的最短路径 例例3.7 打印杨辉三角形。
打印杨辉三角形 此问题是一个初等数学问题系数表中的第此问题是一个初等数学问题系数表中的第i i行有行有i+1i+1个个数，除了第数，除了第1 1个和最后一个数为个和最后一个数为1 1外，其余的数则为上一行中外，其余的数则为上一行中位于其左、右的两数之和位于其左、右的两数之和 算法分析算法分析算法分析算法分析 如如果果要要计计算算并并输输出出二二项项式式系系数数表表（（即即杨杨辉辉三三角角形形））的的前前n n行行的的值值，，则则所所设设循循环环队队列列的的最最大大空空间间应应为为n+2n+2假假设设队队列列中中已已存存有有第第i i行行的的值值，，为为计计算算方方便便，，在在两两行行之之间间均均加加一一个个“0”“0”作作为为行行间间的的分分隔隔符符，，则则在在计计算算第第i+1i+1行行之之前前，，头头指指针针正正指指向向第第i i行行的的“0”“0”，，而而尾尾元元素素为为第第i+1i+1行行的的“0”“0”由由此此，，从从左左至至右右输输出出第第i i行行的的值值，，并并将将计算所得的第计算所得的第i+1i+1行的值插入队列行的值插入队列 分析第分析第 i i 行元素与第行元素与第 i+1i+1行元素的关系如图所示行元素的关系如图所示 ： 假设假设n=4n=4，，i=3i=3，，则输出第则输出第3 3行元素并求解第行元素并求解第4 4行行元素值的循环执行过程中队列的变化状态如图所示元素值的循环执行过程中队列的变化状态如图所示 ： 程序如下: (n≤7)#define MAXSIZE 10 /*定义队列的最大长度*/#include
