数据结构DS03-栈和队列.ppt

栈（栈（StackStack） 栈的应用栈的应用 队列（队列（QueueQueue） 队列的应用队列的应用 第三章 栈和队列 定 义 3.1 3.1 栈栈 与线性表相同，数据元素之间仍为一对一的关 系。 用顺序栈顺序栈或链栈链栈存储均可。 只能在栈顶栈顶运算，且访问结点时依照后进先出 后进先出 （LIFO）或先进后出先进后出（FILO）的原则。 关键是编写入栈入栈、出栈出栈等函数，具体实现按顺序 栈或链栈的存储结构的不同而不同。 存储结构 运算规则 实现方式 逻辑结构 限定只能在表的一端一端进行插入和删除运算的线 性表。 基本操作 建栈、判断栈满或栈空、入栈、出栈、读栈顶 元素值，等等。 栈栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 (top) ; 表头(即 a1 端)称为栈底(bottom)。 例如： 栈 S S= (a1 , a2 , a3 , .,an-1 , an ) 插入元素到栈顶的操作，称为入栈栈。 从栈顶删除元素的操作，称为出栈。 an称为栈顶元素a1称为栈底元素 强调：强调：插入和删除都只能在表 的一端（栈顶）进行！ 栈的基本操作 InitStack(S)： 构造一个空栈S ClearStack(S)： 清除栈S中的所有元素 StackEmpty(S)：判断栈S是否为空，若为空，则返回 true；否则返回false GetTop(S) ： 返回S的栈顶元素，但不移动栈顶指针 Push(S, x) ：插入元素x为新的栈顶元素（入栈操作) Pop(S) ： 删除S的栈顶元素并返回其值（出栈操作） 顺序栈的存储结构和操作的实现 顺序栈:是利用一组地址连续的存储单元依次存放从栈底到 栈顶的数据元素。 在在C C语言中，预设语言中，预设 一个数组的最大一个数组的最大 空间空间, ,栈底设置在栈底设置在 0 0下标端，栈顶随下标端，栈顶随 着插入和删除元着插入和删除元 素而变化，用一素而变化，用一 个整型变量个整型变量toptop来来 指示栈顶的位置指示栈顶的位置 。 a1 a2 an 顺序栈S ai 0 n 栈底 栈顶toptop 压入(PUSH)PUSH): : S+toptop=an+1 弹出( POP)POP) : : e e=S=Stop top - - - 顺序栈存储结构的描述： # #definedefine MaxsizeMaxsize 100 100 /*设顺序栈的最大长度为100，可依实现情 况而修改*/ typedef int datatypetypedef int datatype; ; typedef structtypedef struct datatype datatype stack stackMaxsizeMaxsize; ; int int top top； /*栈顶指针*/ SeqStackSeqStack； /*顺序栈类型定义*/ SeqStackSeqStack *s *s； /*s为顺序栈类型变量的指针*/ 顺序栈的几种状态以及在这些状态下栈顶指针top和栈 中结点的关系 栈为空的条件 ： top=-1; 栈满的条件 ： top=Maxsize-1 若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的堆栈: 入栈：栈指针top “先加后压” : S+top=an+1 出栈：栈指针top “先弹后减” : e=Stop- 顺序栈的基本操作 构造一个空顺序栈 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-stackS-top; 判别空栈 int StackEmpty(SeqStack *S) if(S-top= -1) return TRUE; else return FALSE; 顺序栈的入栈操作例如用堆栈存放（A，B，C，D） AA C B A B A top 核心语句：顺序栈入栈函数PUSH（） SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize-1) return NULL;/*栈满*/ else S-top+; S-stackS-top=x; return s; Push (B); Push (C); Push (D); top top top top 低地址L Push (A); 高地址M B C D 顺序栈出栈操作例如从栈中取出B B D C B A top top D C A B D C B A topD C B A top 低地址L 高地址M D 核心语句： Pop ( ); 顺序栈出栈函数POP() datatype Pop( SeqStack *S) if(S-top=-1) /*栈空*/ printf(“nThe sequence stack is empty!“); return FALSE; else S-top- -; return S-stackS-top+1; Pop ( ); Printf( Pop () ); 链 栈 链栈的构造方式用top指向栈顶，只能在栈顶插入或删除。 栈顶 栈底 栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈 。 toptop a1 a2 an-1 an nextdata 链栈中每个结点由两个域构成： data域和next域，其定义为： Typedef struct node datatype data; /*数据域*/ struct node *next; /*指针域*/ LinkStack; LinkStack *top; /* top为栈顶指针*/ 将x入栈，修改栈顶 指针:top=p an出栈，修改栈顶指 针:top=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转换为r进制数） 设计思路：用栈暂存余数（低位值） 2、括号匹配问题 设计思路：用栈暂存左括号 3、子程序的调用 设计思路：用栈暂存指令地址 4、逆置一个单链表 设计思路：用栈暂存每一结点的数据 3.2 3.2 栈的应用举例栈的应用举例 例3.2 将十进制整数转换成二至九之间的任一进 制数输出 将一个十进制数4327转换成八进制数(10347)8： 当N0，将N%r压 入栈s中； N/r N； 若N0，则重复 、两步；若N=0， 则将栈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 利用一个顺序栈将一个带头结点的单链表（ a1,a2,an）（其中n=0）逆置为（an,an-1,，a1） 。 1、建立一个带头结点的单链表 head； 2、输出该单链表； 3、建立一个空栈s（顺序栈） ； 4、依次将单链表的数据入栈； 5、依次将单链表的数据出栈， 并逐个将出栈的数据存入单链 表的数据域（自前向后）; 6、再输出单链表。 解题思路如下： linklist*backlinklist(linklist *head) linklist *p; p=head-next; initstack(); while(p) push( p=p-next ; p=head-next; while(!stackempty(s) p-data=pop( p=p-next; return (head); ； 3.3 3.3 队列队列 与线性表相同，仍为一对一关系 。 顺序存储方式：顺序队列(循环队列)和链式 存储方式：链队列。 只能在队尾入队、队头出队，并遵循先进先 出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现按存 储方式的不同(顺序队列或链队列)而不同。 存储结构存储结构 运算规则运算规则 实现方式实现方式 逻辑结构逻辑结构 只能在表的一端进行插入运算，在表的另一 端进行删除运算的线性表。 基本操作基本操作 入队、出队、建空队列、判队空或队满等。 尾部插 入 头部删 除 队列定义队列定义 队列 （Queue）是仅在表尾进行插入操作、在表头进行删除操 作的线性表。它是一种先进先出（）的线性表。 例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ) 在队尾插入元素称为入队入队；在队首删除元素称为出队出队。 队首队尾 队列的队列的实现方式实现方式是本节重点，是本节重点，关键是掌握入队和出队 等等操作。 具体实现按存储结构的不同（顺序队列或链队列）而 不同。 队列的基本操作队列的基本操作 （1）InitQueue(Q)： 构造一个空队列Q （2）QueueEmpty(Q)： 判断队列是否为空 （3）QueueLength(Q)：求队列的长度 （4）GetHead(Q)： 返回Q的队头元素，不改变队列状态 （5）EnQueue(Q,x)： 入队列：插入元素x为Q的新的队尾元素 （6）DeQueue(Q)： 出队列：删除Q的队头元素 （7）ClearQueue(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=rear 链队列会满吗 ？ 一般不会，因为删除时有free动作，除非内存不足！ 修改rear指针 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=front-next-next; 怎样实现链队列的入队操作和出队操作？ 假设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 struct datatype dataMAXSIZE； /* 存储队列的数据空间 */ 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=（rearfront +MAXSIZE）% MAXSIZE J2 J3 J1 J4 J5 front rear 解决办法：少用一个元素空间，约定以“队头指针在队尾指针的下 一位置(指环状的下一位置)”作为队列“满”的标志。也就是说，若 数组的大小是MAXSIZE，则该数组所表示的循环队列最多允许存储 MAXSIZE-1个结点。注意： rear所指的结点始终为空。 循环队列满的示意图 ： 经过约定后的循环队列操作示意图 （p.70，图3.13改 ） 循环队列的基本操作实现 以创建队列、入队和出队三种基本操作为例 1、构造（初始化）一个空队列 算法要求：生成一空队列 算法步骤： 为队列分配存储空间； 设置队列为空队列，其特征为： front=rear=0 构造一个空队列q SeqQueue *InitQueue() SeqQueue *q； q=(SeqQueue *)malloc(sizeof(SeqQueue)； /* 开辟一个足够大的存储队列空间 */ q-front = q-rear = 0； /* 将队列头尾指针置为零 */ return q； /* 返回队列的首地址 */ 算法说明：向循环队列的队尾插入一个元素。 分 析： (1)入队前应当先判断队列是否已满？ if(q-rear+1)% Maxsize)=q-front) return false; (2)入队动作如下: q-dataq-rear = x; q-rear=(q-rear+1)% Maxsize; 2、入队操作 int EnQueue(SeqQueue *q, datatype x) if(q-rear+1)MAXSIZE=q-front) printf(“n循环队列满!”); return FALSE; q-dataq-rear = x； q-rear = (q-rear+1)%MAXSIZE; return TRUE; 循环队列入队操作 3、出队操作 算法说明：删除循环队列的队头元素，返回其值 x。 分 析： （1）在出队前应当判断队列是否为空？ if (q-front=q-rear) return false; （2）出队动作如下: x= q-dataq-front; q-front=(q-front+1)% Maxsize; 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、打印杨辉三角形、打印杨辉三角形 2、迷宫问题：寻找一条从迷宫入口到出口 的最短路径 例3.7 打印杨辉三角形。 此问题是一个初等数学问题。系数表中的第i行有i+1个 数，除了第1个和最后一个数为1外，其余的数则为上一行中 位于其左、右的两数之和。 算法分析算法分析 如果要计算并输出二项式系数表（即杨辉三角形 ）的前n行的值，则所设循环队列的最大空间应为n+2 。假设队列中已存有第i行的值，为计算方便，在两行 之间均加一个“0”作为行间的分隔符，则在计算第 i+1行之前，头指针正指向第i行的“0”，而尾元素为 第i+1行的“0”。由此，从左至右输出第i行的值，并 将计算所得的第i+1行的值插入队列。 分析第 i 行元素与第 i+1行元素的关系如图所示 ： 假设n=4，i=3，则输出第3行元素并求解第4行 元素值的循环执行过程中队列的变化状态如图所示 ： 程序如下: (n7) #define MAXSIZE 10 /*定义队列的最大长度*/ #include #include typedef int datatype; typedef struct int dataMAXSIZE; int front; int rear; SeqQueue; SeqQueue *InitQueue() /*队列初始化*/ SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue); q-front = q-rear = 0; return q; void EnQueue(SeqQueue *q, datatype x) /*入队列*/ if(q-rear+1)%MAXSIZE=q-front) printf(“n顺序循环队列是满的!“); else q-dataq-rear = x; q-rear = (q-rear+1)%MAXSIZE; datatype DeQueue (SeqQueue *q) /*出队列*/ datatype x; if(q-front=q-rear) printf(“n顺序队列是空的！不能做删除操作！“); return 0; x = q-dataq-front; q-front = (q-front+1)%MAXSIZE; return x; int QueueEmpty(Se