第03章栈和队列.ppt

1,第3章 栈和队列,3.2 队列,3.1 栈,本章小结,2,3.1.1 栈的基本概念,3.1.2 栈的顺序存储结构,3.1.3 栈的链式存储结构,3.1 栈,3,栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。表中允许进行插入、删除操作的一端称为栈顶；另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,3.1.1 栈的基本概念,4,栈的特点是后进先出。举一个例子说明栈结构的特征，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为，按编号的顺序依次进入此胡同，如图3.1所示。此时若编号为的人要退出胡同，必须等退出后才可以。若要退出，则必须等到、依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。,5,栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除运算都在栈顶进行，相当于进出都经过胡同口。这表明栈修改的原则是先进后出（或后进先出）。因此栈又称为后进先出线性表。,6,栈顶,栈底,出栈,进栈,栈示意图,7,例1 设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,8,例2 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C,答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,9,例3 已知一个栈的进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=n,则pi的值。(A)i(B)n-i(C)n-i+1(D)不确定,答:当p1=n时,输出序列必是n,n-1,3,2,1,则有:p2=n-1,p3=n-2,pn=1推断出pi=n-i+1,所以本题答案为C。,10,例4 设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=3,则p2的值。(A)一定是2(B)一定是1(C)不可能是1(D)以上都不对,答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,n,但一定不能是1。所以本题答案为C。,11,栈的基本运算至少应包括以下5种:(1)初始化栈InitStack(st):构造一个空栈st。(2)进栈Push(st,x):将元素x插入到栈st中作为栈顶元素。(3)出栈Pop(st,x):其作用是当栈st不空时，将栈顶元素赋给x,并从栈中删除当前栈顶。(4)取栈顶元素GetTop(st,x):若st不空，由x返回当前的栈顶元素,当栈st为空时，结果为一特殊标志(。(5)判断栈是否为空StackEmpty(st):若栈st为空,则返回1；否则返回0。,12,例3.3 利用栈的基本运算，编写一个算法输入若干整数，以0标识输入结束。然后按与输入相反次序输出这些整数。,解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法如下：void Invert()int n;cout n;if(n=0)break;/输入值n为0时退出循环 Push(st,n);/n进栈 cout“输出序列：”；while(!StackEmpty(st)/栈不空时循环 Pop(st,n);/出栈n cout n“”;/输出n,13,3.1.2 栈的顺序存储结构 栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。假设用一维数组sq5表示一个栈，则需使用一个变量top记录当前栈顶下标值。图(a)表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶下标值top=-1。如果作出栈运算，则会“下溢”。,14,顺序栈进栈和出栈示意图,top,-1,top,top,top,15,顺序栈类型定义如下：顺序栈被定义为一个结构体类型，它有两个域：data和top。Data为一个一维数组，用于存储栈中元素，ElemType为栈元素的数据类型，可以根据需要而指定为某种具体的类型。top为int型，它的实际取值范围为0 StackSize-1。top=-1表示栈空；top=StackSize-1表示栈满。const int StackSize=100;/顺序栈的初始分配空间 typedef struct sqst ElemType dataStackSize；/保存栈中元素 int top；/栈指针 SqStack；,16,顺序栈的基本运算算法如下:(1)初始化栈运算算法 此算法主要用于创建一个空栈,并将栈顶下标top初始化为-1。void InitStack(SqStack,17,(2)进栈运算算法 其主要操作是：栈顶下标加1,将进栈元素放进栈顶下标所指的位置上。int Push(SqStack,18,(3)出栈运算算法 其主要操作是：先将栈顶元素取出，然后将栈顶下标减1。int Pop(SqStack,19,(4)取栈顶元素运算算法 其主要操作是：将栈中top处的元素取出赋给变量x。int GetTop(SqStack st,ElemType,20,(5)判断栈空运算算法 其主要操作是：若栈为空（top=-1）则返回值1，否则返回0。int StackEmpty(SqStack st)if(st.top=-1)return 1;else return 0;,21,例3.4 设计一个算法，判断一个表达式中符号“（”与“）”、“”与“”、“”与“”是否匹配。若匹配，则返回1；否则返回0。解:设置一个栈st,用i扫描表达式exps：遇到(、和时，将其进栈,遇到）、和时,判断栈顶是否是匹配的括号。若不是，则退出扫描过程，返回0；否则直到exps扫描完毕为止。若top=0，则返回1。对应算法如下：(以下为完整程序）#include const int Max=100;int match(char*exps)char stMax,top=-1,i=0;int nomatch=0;while(expsi!=0&nomatch=0),22,switch(expsi)case(:sttop=expsi;top+;break;case:sttop=expsi;top+;break;case:sttop=expsi;top+;break;case):if(sttop=()top-;else nomatch=1;break;case:if(sttop=)top-;else nomatch=1;break;case:if(sttop=)top-;else nomatch=1;break;,23,i+;if(nomatch=0),24,3.1.3 栈的链式存储结构 栈的链式存储结构是以某种形式的链表作为栈的存储结构，栈的链式存储结构简称为链栈，其组织形式与单链表类似。如图3.4所示。其中，单链表的第一个节点就是链栈栈顶结点，ls称为栈顶指针。,25,链栈示意图,栈由栈顶指针ls唯一确定。栈中的其他结点通过它们的next域链接起来。栈底结点的next域为NULL。因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况。,26,链栈的类型定义如下:typedef struct stnode ElemType data;/存储结点数据 struct stnode*next;/指针域 LinkStack;,27,在链栈中,栈的基本运算算法如下:(1)初始化栈运算算法 其主要操作是：创建一个头结点*ls,用ls=NULL标识栈为空栈。void InitStack(LinkStack*,28,(2)进栈运算算法 其主要操作是：先创建一个新节点，其data域值为x；然后将该结点插入到*ls结点之后作为栈顶结点。void Push(LinkStack*,29,(3)出栈运算算法 其主要操作是：将栈顶结点（即ls-next所指结点）的data域值赋给x，然后删除该栈顶结点。int Pop(LinkStack*,30,(4)取栈顶元素运算算法 其主要操作是：若栈为空（即ls-next所指结点）的data域值赋给x。int GetTop(LinkStack*ls,ElemType,31,(5)判断栈空运算算法 其主要操作是：若栈为空（ls-next=NULL）,则返回值1，否则返回0。int StackEmpty(LinkStack*ls)if(ls=NULL)return 1;else return 0;,32,例3.5 假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO 通过对的分析，写出一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）,33,解：A、D均合法，而B、C不合法。因为在B中，先进栈一次，立即出栈2次，这会造成栈下溢。在C中共进栈5次，出栈3次，栈的终态不为空。本例用一个链栈来判断操作序列是否合法，其中A为存放操作序列的字符数组，n为该数组的元素个数（这里的ElemType类型设定为char。）,34,int Judge(char A,int n)int i;ElemType x;LinkStack*ls;InitStack(ls);for(i=0;inext=NULL);/栈为空时返回1，否则返回0,35,3.2 队列,3.2.1 队列的基本概念,返回,3.2.2 队列的顺序存储结构,3.2.3 队列的链式存储结构,36,队列也是一种运算受限的线性表,在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。,3.2.1 队列的基本概念,37,队列与现实生活中人们为得到某种服务（如购物、购票等）而排队十分相似。排队的规则是不允许“插队”，新加入的成员只能排在队尾，而且队中全体成员只能按顺序向前移动，当到达队头（并得到服务）后离队。队列的特点是先进先出，因此，队列又称为先进先出线性表。,38,队列以线性表为逻辑结构，其基本运算如下：,初始化队列InitQueue(qu)入队列EnQueue(qu,x)出队DeQueue(qu,x)取队头元素GetHead(qu,x)判断队列空QueueEmptyq(qu),39,3.2.2 队列的顺序存储结构,队列的顺序存储结构简称为顺序队，它由一个一维数组（用于存储队列中元素）及两个分别指示队头和队尾的变量组成，这两个变量分别称为“队头指针”和“队尾指针”（注意它们并非指针变量，而是数组的下标）。队尾指针（real）指示队尾元素在一维数组中的当前位置，队头指针（front）指示队头元素在一维数组中的当前位置的前一个位置。,40,顺序队列的类型定义如下:const int QueueSize=20;/队列的容量 typedef struct sqqueue ElemType dataQueueSize；/保存队中元素 int front,rear；/队头和队尾指针 SqQueue 其中data为存储队列中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围是0QueueSize-1。,41,队列的入队和出队操作示意图,42,从前图中看到,图(a)为队列的初始状态,有front=rear成立,该条件可以作为队列空的条件。那么能不能用rear=QueueSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在data数组中存在可以存放元素的空位置,所以这是一种假溢出。为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为环形队列。,43,环形队列首尾相连,当队首front指针满足 front=QueueSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算(MOD)来实现:队头指针进1:front=(front+1)MOD QueueSize 队尾指针进1:rear=(rear+1)MOD QueueSize 环形队列的队头指针和队尾指针初始化时都置0:front=rear=0。在队尾插入新元素和删除队头元素时,指针都按逆时针方向进1。,44,为了区别于队列空条件，用(rear+1)MOD QueueSize=front来判断是否队已满，也就是说，让rear指到front的前一位置就认为队列已满。此时，因队头指针指示实际队头的前一个位置所以在队列满时实际空了一个元素位置。如果不留这个空位置，让队尾指针rear一直存到这个位置，必然有rear=front，则队列空条件和队列满条件就混淆了。,45,循环队的入队和出队操作示意图,46,环形队列qu的4要素：,队空条件：qu.front=qu.rear队满条件：(qu.rear+1)%QueueSize=qu.front进队操作：qu.rear循环进1；元素进队。出队操作：qu.front循环进1；元素出队。,47,在环形队列中,实现队列的基本运算算法如下:(1)初始化队列运算算法 其主要操作是：创建一个队列结点，用sq指向该队列结点，并指定sq-front=sq-rear=0 void InitQueue(SqQueue*/指针初始化,48,(2)入队运算算法 其主要操作是：先判断队列是否已满，若不满，将队尾指针增1,在该位置存放x。对应算法如下:int EnQueue(SqQueue*,49,(3)出队运算算法 其主要操作是：先判断队列是否已空,若不空，让队头指针增1,将该位置的元素值赋给x。int DeQueue(SqQueue*sq,ElemType,50,(4)取队头元素运算算法 其主要操作是：先判断队列是否已空,若不空，让队头指针上一个位置的元素值赋给x。int GetHead(SqQueue*sq,ElemType,51,(5)判断队列是否为空 若队列q满足q-front=q-rear条件,则返回1；否则返回0。对应算法如下:int QueueEmpty(SqQueue*q)return(q-front=q-rear);,52,例3.8 对于环形队列，写出求队列中元素个数的公式。解：根据环形队列的特点，有以下情况：0 队空，即front=rear元素个数=rear-front 若rearfront rear+QueueSize-front 若rearfront QueueSzie 若队列满即(rear+1)%QueueSize=front归纳起来，环形队列元素个数的计算公式如下：(rear+QueueSize-front)%QueueSize,53,例3.9 如果用一个环形数组quQueueSzie表示队列，该队列只有一个头指针front，不设队尾指针rear，而设置计数器count，用以记录队列中的元素个数。1、队列中最多能容纳多少个元素？2、设计实现队列基本运算算法。,解：1、队列中最多容纳QueueSize个元素，因为这里不需要空出一个位置以区分队列空和队列满的情况。2、队列为空的条件是：count=0；队列满的条件是：count=QueueSize；队尾元素的位置是(front+count)%QueueSize；队头元素的位置是(front+1)%QueueSize。在这种队列上实现队列的基本运算算法如下：,54,void InitQueue(SqQueue*,55,int DeQueue(SqQueue*sq,ElemType,56,int QueueEmpty(SqQueue*sq)/判断队空 if(sq-count=0)return 1;else return 0;,57,队列的链式存储结构简称为链队，它实际上是一个同时带有首指针和尾指针的单链表。首指针指向队头结点，尾指针指向队尾结点即单链表的最后一个结点。,3.2.3 队列的链式存储结构,58,链列的入队和出队操作示意图,59,链队的类型定义如下:typedef struct QNode ElemType data;struct QNode*next;QType;/链队中结点的类型 typedef struct qptr QType*front;*rear;LinkQueue;/链队类型 在这样的队列中，队空的条件是 lq-front=lq-rear=NULL。一般情况下，链队是不会出现队满的情况。,60,在链队上实现队列的基本运算算法如下:(1)初始化队列运算算法 其主要操作是：置结点lq*的rear和front均为NULL:void InitQueue(LinkQueue*/初始情况,61,(2)入队运算算法 其主要操作是：创建一个新结点，将其链接到链队的末尾，并由rear指向它。void EnQueue(LinkQueue*,62,(3)出队运算算法 int DeQueue(LinkQueue*,63,(4)取队头元素运算算法 其主要操作是：将*front结点的data域值赋给x。int GetHead(LinkQueue*,64,(5)判断队空运算算法 其主要操作是：若链队为空，则返回1；否则返回0。对应算法如下:int QueueEmpty(LinkQueue*lq)if(lq-front=NULL,65,例3.10 若使用循环链表来表示队列，p是链表中一个指针。试基于此结构给出队列的入队（EnQueue）和出队（DeQueue）算法，p为何值时队列空？解：这里使用的循环链表不带头结点，规定p始终指向队尾结点,p-next即为队头结点。当p=NULL时队列为空。队列的入队和出队算法如下：typedef struct node ElemType data;struct Qnode*next;Qnode;,66,void EnQueue(Qnode*,p-next,p-next=s,s-next=p-next,p,67,int DeQueue(Qnode*,68,s=pnext,pnext,free(s)释放空间,p,data,x=s-data,69,例3.11 设计一个程序，反映病人到医院看病、排队看医生的情况。解：病人排队看医生采用先到先看的方式，所以要用到一个队列，这里设计了一个带头结点的单链表作为队列。完整的程序如下：#include#include#includeTypedef struct QNode char data10;struct QNode*next;Qtype;Typedef struct qptr Qtype*front,*rear;LinkQueue;,70,void SeeDoctor()int sel,flag=1;LinkQueue*lq;Qtype*s;char name(10);lq=(LinkQueue*)malloc(sizeof(LinkQueue);lq-front=(Qtype*)malloc(sizeof(QType);lq-front-next=NULL;lq-rear=lq-front;while(flag=1)cout“1:排队 2:看医生 3:查看排队 0:下班 请选择:”;cin sel;,71,case 0:ifype(lq-front!=lq-rear)cout 请排队的患者明天就医”输入患者姓名:”;cin name;s=(QType*)malloc(sizeof(QType);strcpy(s-data,name);s-next=NULL;lq-rear-next=s;lq-rear=s;break;case2:if(lq-front=lq-rear)cout 没有排队的患者”endl;,72,else s=lq-front-next;if(lq-rear=s)lq-rear=lq-front;cout 患者”data front-next=s-next;free(s);break;case3:if(lq-front=lq-rear)cout 没有排队的患者”endl;,73,else s=lq-front-next;cout 排队患者:”;while(s!=NULL)cout data next;cout endl;break;,74,void main()SeeDoctor;本程序的一次执行结果：,75,本章小结本章基本学习要点如下:(1)理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意环形队列上队满和队空的条件。(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。,