计算机软件技术基础教程课件-8第八章-栈和队列

第八章栈和队列8.1栈8.1.1栈的基本概念及其运算8.1栈8.1.1栈的基本概念及其运算(1)置空栈—SetNull(S)，完成对栈的初始化。(2)判断栈是否为空—Empty(S)，若栈S为空，则返回真；否则，返回假。(3)进栈—Push(S，e)，在栈S的栈顶插入数据元素e。(4)出栈—Pop(S)，删除栈S的栈顶数据元素，并把出栈数据元素返回。(5)取栈顶元素—GetTop(S)，取栈S的栈顶数据元素，并把数据元素返回。该操作完成后，栈的状态不变。8.1栈8.1.2栈的存储结构1.顺序存储结构2.链式存储结构8.1栈8.1.2栈的存储结构1.顺序存储结构--顺序栈structStack{ datatypeelements[maxsize]； intTop；}其中，maxsize是栈的容量，datatype是栈中数据元素的数据类型，Top指示当前栈顶位置，栈底位置为0。8.1栈8.1.2栈的存储结构1.顺序存储结构--顺序栈8.1栈8.1.2栈的存储结构(1)置空栈：将栈进行初始化，主要是将栈顶指针Top初始化为–1。voidSetNuLLS(structStack*S){ S－>Top=–1；} /

SetNuLLS

/(2)判断栈是否为空：在进行出栈操作时，首先必须判断栈不为空，否则会出错。intEmptyS(structStack*s){ if(S－>Top>=0)return(0)； elsereturn(1)；} /*EmptyS*/8.1栈8.1.2栈的存储结构(3)进栈：将数据元素E插入栈顶。

structStack*PushS(structStack*S,datatypeE){if(S－>Top>=maxsize-1){printf("StackOverflow")； /

上溢现象。

/return(NULL)；}else{S－>Top++； S－>elements[S－>Top]=E；

}return(s)；} /*PushS*/8.1栈8.1.2栈的存储结构(4)出栈：首先判断栈是否为空，若空则表示下溢，否则删除栈顶数据元素。datatypePOPS(structStack*S){datatype*temp; if(EmptyS(S)){printf("StackUnderflow")；return (NULL)；}else{S

Top--; temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top+1];return(temp);}}/*PopS*/8.1栈8.1.2栈的存储结构(5)取栈顶元素：只把栈顶元素的值取出，而不调整栈顶指针Top的值。datatype*GetTopS(structStack*S){datatype*temp;if(EmptyS(S)){printf("Stackisempty")；return (NULL)；}else{temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top];return (temp);}} /*GetTopS*/8.1栈8.1.2栈的存储结构2.链式存储结构—链栈8.1栈8.1.2栈的存储结构2.链式存储结构—链栈链栈定义如下：structNode{datatypeelement; structNode*next;};structNode*top;8.1栈8.1.2栈的存储结构voidPUSHL(structNode*S,datatypeE){structNode*p; /*进栈*/p=(structNode*)malloc(1,sizeof(structNode));p－>element=E;p－>next=S;S=p;}top链栈的进栈操作8.1栈8.1.2栈的存储结构top

datatypePOPL(structNode*S) /*出栈*/{datatype*X; if(S==NULL){printf("Stackisunderflow"); return(NULL);}else{ X=(datatype*)malloc(sizeof(datatype));* X=S－>element; S=S－>next; return(X); } } /*POPL*/链栈的出栈操作8.2栈的应用栈的应用非常广泛，只要问题满足LIFO原则，均可使用栈作为数据结构。栈的典型应用有：(1)“回溯”问题的求解；(2)过程递归调用和过程嵌套。8.2栈的应用8.2.1递归调用以计算Fibonacci序列为例来说明栈在递归调用中的作用。8.2栈的应用8.2.1递归调用intFib(intn){intfib；if(n==0)fib=0; else if(n==1)fib=1; elsefib=Fib(n-1)+Fib(n-2); return(fib);} /*Fib*/8.2栈的应用8.2.1递归调用当n=5时，递归执行过程如下图所示8.2栈的应用8.2.1递归调用栈在该递归调用的执行过程中用来存放每次调用中产生的中间结果。栈的变化过程如下图所示。8.2栈的应用8.2.1递归调用8.2栈的应用8.2.2地图染色问题8.2栈的应用8.2.2地图染色问题用一个关系矩阵R[n][n]来描述各行政区域间的相邻关系：1，行政区域i+1和j+1间是相邻的

R[i][j]=0，行政区域i+1和j+1间是不相邻的除R之外，还需设置一个栈S，用来记录行政区域所染颜色的序号：

S[i]=k表示行政区域i+1所染颜色的序号为k，k是1#、2#、3#、4#之一。8.2栈的应用voidmapcolor(intR[][],intn,intS[]){intcolor，area，k；S[0]=1; /*第(1)行政区域染1#号颜色*/area=1; /*从第(2)行政区域开始试探染色*/color=1; /*从第1#号颜色开始试探*/while(area<n){ while(color<=4){k=0; /*指示已染色区域*/while((k<area)&&(S[k]*R[area][k]!=color)){k++;/*判断当前area区域与k区域是否重色，并找k区域能染的颜色*/}if(k<area)color++; /*area区域与k区域重色*/else{ /*area区域与k区域不重色，再试探下一个行政区域*/S[area]=color;area++;color=1;}} /*while(color<=4)end*/if(color>4) /*area区域找不到合适的颜色*/{ area-=1; /*回溯并修改area-区域所用颜色*/color=s[area]+1;}}} /*mapcolor*/8.2栈的应用关系矩阵R运行过程中栈S的变化过程8.3队列8.3.1队列的基本概念合运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(Front)，允许插入的一端称为队尾(Rear)。队列同现实生活中排队相仿，新来的成员总是加入队尾(即不允许“加塞”)，每次离开的成员总是队列头上的(即不允许中途离队)，即当前“最老的”成员离队。换而言之，先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称为FIFO表。8.3队列8.3.1队列的基本概念合运算当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…,an之后，a1是队头元素，an是队尾元素。显然出队的次序也只能是a1,a2,…,an,也就是说队列的改变是依先进先出的原则进行的。8.3队列8.3.1队列的基本概念合运算队列的五种基本运算：

(1) SetNull(Q):置Q为一个空队列。(2) Empty(Q):判断队列Q是否为空队列。当Q是空队列时，返回“真”值，否则返回“假”值。(3) Front(Q):取队列Q的队头元素，队列中元素保持不变。(4) Enqueue(Q,x):将元素x插入队列Q的队尾,简称为入队(列)。(5) Dequeue(Q):删除队列Q的队头元素，简称为出队(列)。函数返回原队头元素。8.3队列8.3.2队列的存储结构1.顺序队列2.链队列8.3队列8.3.2队列的存储结构1.顺序队列顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而需要设置两个指针，分别指示当前队头元素和队尾元素在数组中的位置。对顺序队列的类型sequeue和一个实际的顺序队列指针sq的说明如下：structsequeue{datatypedata[maxsize];intfront，rear;}; /*顺序队列的类型*/sequeue

sq /*sq是顺序队列的指针*/8.3队列8.3.2队列的存储结构1.顺序队列为方便起见，我们规定头指针front总是指向当前队头元素的前一个位置，尾指针rear指向当前队尾元素的位置。一开始，队列的头、尾指针指向向量空间下界的前一个位置，在此设置为-1。若不考虑溢出，则入队运算可描述为

sq->rear++; //尾指针加1

sq->data[sq->rear]=x;//x入队

出队运算可描述为

sq->front++;//头指针加1

*temp=sq->data[sq->front];//读出队头元素8.3队列8.3.2队列的存储结构1.顺序队列顺序队列运算时的头、尾指针变化情况8.3队列8.3.2队列的存储结构1.顺序队列顺序队列运算时的头、尾指针变化情况显然，当前队列中的元素个数(即队列的长度)是(sq->rear)-(sq->front)。若sq->front=sq->rear，则队列长度为0，即当前队列是空队列，图3-12(a)和(c)均表示空队列。空队列时再做出队操作便会产生“下溢”。队满的条件是当前队列长度等于向量空间的大小，即

(sq->rear)-(sq->front)==MAXSIZE8.3队列8.3.2队列的存储结构1.顺序队列克服假上溢通常采用的方法是：设想向量sq->data

[MAXSIZE]是一个首尾相接的圆环，即sq->data[0]接在sq->data[MAXSIZE-1]之后，我们将这种意义下的队列称为循环队列。8.3队列8.3.2队列的存储结构1.顺序队列循环队列示意图8.3队列8.3.2队列的存储结构1.顺序队列若当前尾指针等于数组的上界，则再做入队操作时，令尾指针等于数组的下界，这样就能利用到已被删除的元素空间，克服了假上溢。因此入队操作时，在循环意义下的尾指针加1操作可描述为

 if(sq->rear+1>=MAXSIZE)sq->rear=0;

elsesq->rear++;

如果利用“模”运算，上述循环意义下的尾指针加1操作可以更简洁地描述为

sq->rear=(sq->rear+1)%MAXSIZE8.3队列8.3.2队列的存储结构1.顺序队列同样，出队操作时，在循环意义下的头指针加1操作，也可利用“模”运算来实现，即

sq->front=(sq->frout+1)%MAXSIZE

因为出队和入队分别要将头指针和尾指针在循环意义下加1，所以某个元素出队后，若头指针已从后面追上尾指针，即

sq->front==sq->rear8.3队列8.3.2队列的存储结构1.顺序队列则当前队列为空；若某个元素入队后，尾指针已从后面追上头指针，即

sq->rear==sq->front

则当前队列为满。因此，仅凭关系式sq->front==sq->rear是无法区别循环队列是空还是满的。对此，有两种解决的办法：一种是引入一个标志变量以区别是空队列还是满队；另一种更为简单的办法是入队前测试尾指针在循环意义下加1后是否等于头指针，若相等则认为是队满，即判别队满的条件是：

(sq->rear+1)%MAXSIZE==sq->front

从而保证了sq->rear==sq->front是队空的判别条件。8.3队列8.3.2队列的存储结构1.顺序队列在循环队列上实现的五种基本运算如下：

(1)置空队列。

(2)判队空。

(3)取队头元素。

(4)入队。

(5)出队。8.3队列8.3.2队列的存储结构2.链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型linkqueue定义为一个结构体类型，如下所示：

typedefstruct{

linklist*front,*rear;

}linkqueue;

linkqueue

q;8.3队列8.3.2队列的存储结构2.链队列8.3队列8.3.2队列的存储结构2.链队列在链队列上实现的五种基本运算如下：

(1)置空队。

(2)判队空。

(3)取队头结点数据。

(4)入队。

(5)出队。8.4队列应用举例8.4.1离散事件仿真1.具体问题假设服务系统有四个窗口对外接待客户，在营业时间内不断有客户进入并要求服务。由于每个窗口只能接待一个客户，因此进入该服务系统的客户须在某一个窗口前排队。如果窗口的服务员忙则进入的客户排队等待；闲则可立即服务。服务结束则从队列中撤离，并计算一天内进入服务系统的客户的平均逗留时间。8.4队列应用举例8.4.1离散事件仿真2.分析影响系统队列变化的原因有两种：

(1)新客户进入服务系统，该客户加入到队列最短的窗口队列中。

(2)四个队列中有客户服务完毕而撤离。8.4队列应用举例8.4.1离散事件仿真3.模拟程序应如何运行

假设事件表中最早发生的是新客户到达，则随之应得到两个时间：一是本客户处理业务所需时间；二是下一个客户到达服务系统的时间间隔。此时模拟程序应做的工作如下：

(1)比较四个队列中的客户数，将新到客户插入到最短队列中。若队列原来是空的，则插入的客户为队头元素，此时应设定一个新的事件——刚进入服务系统的客户办完业务离开服务系统的事件插入事件表。

(2)设定一个新的到达事件—下一个客户即将到达服务系统的事件插入事件表。8.4队列应用举例8.4.1离散事件仿真3.模拟程序应如何运行如果发生的事件是某队列中的客户服务结束离开服务系统，那么模拟程序应做以下两件工作：

(1)客户从队头删除，并计算该客户在服务系统中逗留时间。

(2)当队列非空(用户离开后)，应把新的队头客户设定为一个新的离开事件，计算该客户离开服务系统的时间，并插入事件表。当服务系统停止营业后，若事件表为空，则程序运行结束。8.4队列应用举例8.4.1离散事件仿真4.数据结构考虑在上述问题的仿真(模拟)程序中，应设置四个队列和一个有序事件表。

队列采用单链表来实现，其中单链表中的每个结点代表一个客户应有两个数据：客户到达时间和客户的服务时间。该链队列有一个队头结点，包括的数据是队列中的客户数。

事件表用单链表来实现，其中的每个结点代表一个事件，包括的数据项有：事件发生时间和事件类型。事件类型为0、1、2、3、4，其中，0表示客户到达事件；1、2、3和4分别表示四个窗口的客户离开事件。事件表中最多有五个事件，当事件表空时程序运行结束。8.4队列应用举例8.4.1离散事件仿真5.仿真程序的实现voidSimulation(){totaltime=0; /*客户逗留时间*/count=0; /*客户数*/generate(pe); /*产生一个事件结点*pe*/pe－>occurtime=0; /*初始化事件表*/pe－>eventtype=0; /*第一个事件客户到达事件*/pe－>next=NULL; /*到达时刻为0*/eventlst－>front=pe;eventlst－>rear=pe;eventlst－>eventnum=1;8.4队列应用举例8.4.1离散事件仿真5.仿真程序的实现for(i=0;i<4;i++) /*置空队列*/SetNullQL(queue[i]);while(!EmptyQL(eventlst)){delete_eventlist(eventlst,event); /*取发生事件并删除它*/if(event－>eventtype==0) /*客户到达事件发生*/{count++; /*统计客户数*/random(durtime,interaltime);/*产生该用户的服务时间和下一到达客户的到达时间间隔*/if((event－>occurtime+interaltime)<closetime){insert_eventlist(eventlst,(event－>occurtime+interaltime,0));/*插入到达事件*/}len=minlength();/*取最短队列号*/addqueue(queue[len],(event－>occurtime,durtime))/*把刚到达的新客户加入到minlen队列中*/8.4队列应用举例8.4.1离散事件仿真5.仿真程序的实现if(queue[len].queuenum==1)insert_eventlist(eventlst,(event－>occurtime+durtime,len));} /*if(...==0)*/else{i=event－>eventtype;deletequeue(q[i]，f); /*删除第i队列的头元素赋给f*/totaltime+=event－>occurtime－f.arrivetime;/*客户逗留时间统计*/if(queue[i]－>queuenum!=0)insert_eventlist(eventlst,(eve