数据结构及应用算法教程--栈和队列优秀PPT.ppt

数据结构,第四章 栈和队列,韶关学院,栈 和 队 列,4.1,栈,（,Stack,）,4.3,队列,（,Queue,）,1.,定义,2.,逻辑结构,3.,存储结构,4.,运算规则,5.,实现方式,1.,定义,2.,逻辑结构,3.,存储结构,4.,运算规则,5.,实现方式,栈和队列,是两种特殊的,线性表,，是,操作受限,的线性表，称,限定性数据结构,。,4.1,栈,栈,是什么？,栈有什么,特点,？,栈的,模型,栈如何在计算机中,实现,？,栈的,顺序,存储结构？,栈的,链式,存储结构？,?,!,【,教学内容,】,栈、存储结构、基本操作实现算法以及栈的应用。,【,教学要求,】,掌握栈逻辑结构的特点。,掌握栈的不同存储方式的基本操作实现方法。,掌握栈的在实际问题应用。,【,重点与难点,】,顺序栈和链栈两种存储基本操作实现算法,栈的在实际问题中应用,限定仅在表尾进行插入或删除操作,。,4.1,栈 （,一头串珠子或垒菜碟,）,4.1.1,栈的结构特点和操作,栈的定义,a,1,a,2,a,n,-1,a,n,栈顶,(top),栈底,(base),出栈,进栈,栈底元素,栈顶元素,栈：,线性表,特点：,后进先出,(LIFO,表,),。,表尾称为栈顶,(top),表头称为栈底,(base),插入元素称为入栈,(push),删除元素称为出栈,(pop,),栈的抽象数据类型的定义,ADT Stack,数据对象：,D,a,i,|,a,i,ElemSet,i,=1,2,.,n,n,0,数据关系：,R1,|,a,i,-1,a,i,D,i,=2,.,n,约定,a,n,端为栈顶，,a,1,端为栈底。,基本操作：,InitStack(&S),操作结果：,构造一个空栈,S,。,DestroyStack(&S),初始条件：,栈,S,已存在。,操作结果：,栈,S,被销毁。,GetTop(S,&,e,),初始条件：,栈,S,已存在且非空。,操作结果：,用,e,返回,S,的栈顶元素。,StackEmpty(S),初始条件：,栈,S,已存在。,操作结果,：,若栈,S,为空栈，则返回,TRUE,，否则,FALSE,。,StackLength(S),初始条件,：,栈,S,已存在。,操作结果：,返回,S,的元素个数，即栈的长度。,ClearStack(&S),初始条件：,栈,S,已存在。,操作结果：,将,S,清为空栈。,Push(&S,e,),初始条件：,栈,S,已存在。,操作结果：,插入元素,e,为新的栈顶元素。,Pop(&S,&,e,),初始条件：,栈,S,已存在且非空。,操作结果：,删除,S,的栈顶元素，并用,e,返回其值。,ADT Stack,4.1.2,栈的表示和操作实现,1.,顺序栈,顺序栈定义及结构定义,顺序栈：,利用一组地址连续的存储单元依次存放自,栈底到栈顶的数据元素，同时附设指针,top,指示栈顶元,素在顺序栈中的位置。,top,A,top,B,top,C,top,D,top,E,top,空栈,若再进行元,素“出栈”操,作，将产生,“,下溢,”。,top,栈满,若再进行元,素“入栈”操,作，将产生,“,上溢,”。,栈,是操作受限制的,线性表,顺序栈是栈的顺序存储,就对应于线性表的顺序存储,即顺序表,故,顺序栈与顺序表存储表示一致,.,#const LIST_INIT_SIZE 100,/,线性表存储空间的初始分配量,#const LISTINCREMENT 10,/,线性表存储空间的分配增量,typedef struct ElemType *elem;,/,数组指针，指示线性表的基地址,int length;,/,当前长度,int listsize;,/,当前分配的存储容量,(,以,sizeof(ElemType),为单位,),int increment;/,约定的增补空间量,SqList;,SelemType*elem;,/,存储数据元素的数组,int top;/,栈顶指针。,int stacksize;/,当前分配的栈可使用的最大存储容量。,SqStack;,注：,top,的值为,=-1,，表明顺序栈为空栈。,#const STACK_INIT_SIZE 100,/,栈存储空间的初始分配量,#const STACKINCREMENT 10,/,栈存储空间的分配增量,int increment;/,约定的增补空间量,讨论：,栈是什么？它与一般线性表有什么不同？,答：,栈是一种特殊的线性表，它只能在,表的一端（即栈顶）,进行插入和删除运算。,与一般线性表的,区别,：仅在于运算规则不同。,线性表,堆栈,逻辑结构：一对一,逻辑结构：一对一,存储结构：顺序表、链表,存储结构：顺序栈、链栈,运算规则：随机存取,运算规则：后进先出,(LIFO),先进后出,(FILO),a,1,a,2,a,n,顺序栈,S,a,i,表和栈的操作区别,对线性表,s=(a,1,a,2 ,.,a,n-1,a,n,),表头,表尾,栈底,栈顶,top,低地址,高地址,写入：,vi=,a,i,读出：,x=vi,压入：,PUSH(a,n+1,),弹出：,POP (x,),前提：,一定要,预设,栈顶指针,top,！,低地址,高地址,vi,a,1,a,2,a,i,a,n,顺序表,Vn,a,n+1,栈的基本操作在顺序栈中的实现,#const maxsize 9;,main(),int stackmaxsize;,int top=-1;,while(top0),e=stacktop-1;,top-=1;,InitStack,Push,Pop,top,1,2,top,top,top,2,top,GetTop,2,1,Status InitStack(SqStack&S,int maxsize=STACK_INIT_SIZE,int incresize=STACKINCREMENT),/,构造一个空栈,S,，初始分配的最大空间为,maxsize,，扩容增量为,increment,S.elem=new SElemTypemaxsize;/,为顺序栈分配容量为,maxsize,的数组空间,S.top=-1;/,顺序栈中当前所含的元素的个数为零,S.stacksize=maxsize;/,该顺序栈可以容纳,maxsize,个数据元素,S.incrementsize=incresize;/,分配增补空间,/InitStack_Sq,bool Push(SqStack&S,SElemType e),/,插入元素,e,为新的栈顶元素,if(S.top=S.stacksize-1),incrementStacksize(S);,S.elem+S.top=e;,/Push_Sq,bool GetTop_Sq(SqStack S,SElemType&e),/,若栈不空，则用,e,返回,S,的栈顶元素，并返回,TRUE,；否则返回,Flase,if(S.top=-1)return FLASE;,e=S.elemS.top;,return TRUE;,/GetTop _Sq,bool Pop_Sq(SqStack&S,SElemType&e),/,若栈不空，删除,S,的栈顶元素,用,e,返回其值，并返回,TRUE,否则返回,FLASE,if(S.top=-1)return FLASE;,e=S.elemS.top-;,return TURE;,/Pop _Sq,顺序栈入栈操作,Push,函数,例如用栈存放（,A,，,B,，,C,，,D,）,（注意要遵循,“,后进先出,”,原则）,A,A,C,B,A,B,A,top,核心语句：,top,=L;,bool Push_Sq(SqStack&S,SElemType e),/,插入元素,e,为新的栈顶元素,if(S.top=S.stacksize-1),incrementStacksize(S);,S.elem+S.top=e;,/Push_Sq,Push(L,B);,Push(L,C);,Push(L,D);,top,top,top,top,低地址,L,Push(L,A);,高地址,M,B,C,D,顺序栈出栈操作,POP,函数,例如从栈中取出,B,（注意要遵循,“,后进先出,”,原则）,D,C,B,A,top,top,D,C,A,B,D,C,B,A,top,D,C,B,A,top,低地址,L,高地址,M,D,核心语句：,Pop(L,e);,Pop(L,e);,Printf(,Pop(L,e),);,bool Pop_Sq(SqStack&S,SElemType&e),/,若栈不空，删除,S,的栈顶元素,用,e,返回其,/,值，并返回,TRUE,否则返回,FLASE,if(S.top=-1)return FLASE;,e=S.elemS.top-;,return TURE;,/Pop _Sq,例,1,：,一个栈的输入序列是,12345,，若在入栈的过程中允许出栈,，,则栈的输出序列,43512,可能实现吗？,12345,的输出呢？,43512,不可能实现，主要是其中的,12,顺序不,能实现；,12345,的输出可以实现，只需压入一个立即,弹出一个即可。,435612,中到了,12,顺序不能实现；,135426,可以实现。,例,2,：,如果一个栈的输入序列为,123456,，能否得到,435612,和,135426,的出栈序列？,答：,答：,例,3,一个栈的输入序列为,123,，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解,：,1,入,1,出，,2,入,2,出，,3,入,3,出，即,123,；,1,入,1,出，,2,、,3,入,3,、,2,出，即,132,；,1,、,2,入，,2,出，,3,入,3,出，即,231,；,1,、,2,入，,2,、,1,出，,3,入,3,出，即,213,；,1,、,2,、,3,入，,3,、,2,、,1,出，即,321,；,合计有,5,种可能性。,栈顶指针,2.,链栈,a,n,注意,:,链栈中指针的方向,a,n,-1,a,1,链栈的入栈函数、出栈函数,（以头指针为栈顶，在头指针处插入或删除！）,链栈的结点定义：,typedef struct Lnode,SElemType data;,struct Lnode*link;,Lnode;*LinkList,typedef LinkList LinkStack;,Void Push_L(LinkStack&S,SElemType e),/,在链栈的栈顶插入新的栈顶元素,e,p=new LNode;,/,为新的栈顶元素分配结点,p-data=e;,p-next=S;/,插入新的栈顶元素,S=p;/,修改栈顶指针,链栈,入栈函数,插入到表头,链栈的入栈算法,.,栈底,top,S=top,e,p,bool Pop_L(LinkStack&S,ElemType&e),/,若栈不空，删除栈顶元素,用,e,返回值,并返回,TRUE;/,否则返回,FLASE,if(S),p=S;S=S-next;/,修改栈顶指针,e=p-data;/,返回栈顶元素,delete p;/,释放结点空间,return TRUE;,else return FLASE;,链栈,出栈函数,从表头删除,链栈出栈操作算法,S=top,.,栈底,top,p,链 栈 说,明,链栈不必设头结点，因为栈顶（表头）操作频繁；,采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,讨论：,为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属；,递归运算的有力工具；,用于保护现场和恢复现场；,简化了程序设计的问题。,答：,4.2,栈的应用举例,例,4.1,数制转换问题,十进制数,N,和其他,d,进制数,M,的转换是计算机实现,计算的基本问题，其解决方法很多，其中一个简单算法是,逐次除以基数,d,取余法，它基于下列原理：,N,=(,N,div,d,)*,d,+,N,mod,d,具体作法为：,首先用,N,除以,d,，得到的余数是,d,进制,数,M,的最低位,M,0,，接着以前一步得到的商作为被除数，,再除以,d,，得到的余数是,d,进制数,M,的次最低位,M,1,，依,次类推，直到商为,0,时得到的余数是,M,的最高位,M,s,（假,定,M,共有,s,+1,位）。,例如：,（,1348),10,=(2504),8,，其运算过程如下,(,除,8,取余法,),：,计算顺序,输出顺序,1348,8,8,8,8,168,4,21,0,2,5,0,2,商,余数,top,4,0,5,2,top,1348,168,21,top,2,top,0,top,N,：,2504,算法,4.1 void,conversion(),InitStack(S);,/,构造空栈,cin,N;,while,(N),Push(S,N,%,8);,/“,余数”入栈,N=N/8;/,商,while,(,!,StackEmpty(S),),/,求余所得相逆的顺序输出八进制的个位数,Pop(S,e);,cout 0&k=0)/,第,k,件物品可选，则,k,入栈,Push(S,k);T-=wk;/,背包剩余体积减少,wk,k+;/,继续考察下一件物品,if (T=0)StackTraverse(S);,/,输出一组解，之后回溯寻找下一组解,Pop(S,k);T+=wk;/,退出栈顶物品，背包剩余体积增添,wk,k+;/,继续考察下一件物品,while(!StackEmpty(S)|k=n);,/knapsack,例,4.4,表达式求值,运算规则,先乘除，后加减；,从左算到右；,先括号内，后括号外；,例：,求表达式,4+2,3-10/5,的值。,计算顺序为：,4+2,3-10/5=4+6-10/5=10-10/5=10-2=8,操作数或结果,运算符,#,4,+,2,3,6,10,-,10,/,5,8,2,算法思想,：,设定两栈,：,操作符栈,OPTR,，操作数栈,OPND,栈初始化,：设操作数栈,OPND,为空；操作符栈,OPTR,的栈底元素为表达式起始符,#,；,依次读入字符,：是操作数则入,OPND,栈，是操作符则要判断：,if,操作符,栈顶元素,，压入,OPTR,栈。,“,(”,对它之前后的运算符,起隔离作用,，,“,)”,可视为自相应左括弧开始的表达式的结束符。,栈的应用（表达式求值）,例,5,栈与递归的实现,递归：,一个直接调用自己或通过一系列的调用语句间接地调,用自己的函数，称做递归函数。,例：,阶乘函数,相应的,C,语言函数是：,float,fact,(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*,fact,(,n,-1);,return(,s,);,若求,5!,，则有,main(),printf(“5!=%fn”,fact(5);,当在一个函数的运行期间调用另一个函数时，在运行,该被调用函数之前，需先完成三件事：,将实参等传递给被调用函数，,保存返回地址,（,入栈,）,；,为被调用函数的局部变量,分配存储区,；,将,控制转移,到被调用函数的入口。,从被调用函数返回调用函数之前，应该完成：,保存,被调函数的,计算结果,；,释放,被调函数的,数据区,；,按被调函数保存的返回地址（,出栈,）将,控制转移,到调,用函数。,多个函数嵌套调用的规则是：,后调用先返回,。,此时的内存管理实行“,栈式管理,”。,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,递归调用执行过程：,主函数,main(),Printf(fact(5),第一层调用,n,=5,s,=5*fact(4),第二层调用,n,=4,s,=4*fact(3),第三层调用,n,=3,s,=3*fact(2),第四层调用,n,=2,s,=2*fact(1),第五层调用,n,=1,s,=1*fact(0),fact(5)=120,输出,s,=120.00,第六层调用,n,=0,s,=1,fact(4)=24,fact(3)=6,fact(2)=2,fact(1)=1,fact(0)=1,主,a,5,a,4,a,3,a,2,a,1,a,printf(“5!=%fn”,fact(5);,base,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,float fact(int,n,),float,s,;,if(,n,=0),s,=1;,else,s,=,n,*fact(,n,-1);,return(,s,);,n,=5,n,=4,n,=3,n,=2,n,=1,n,=0,4.3,队列,队列是什么？,队列有什么,特点,？,队列的,模型,队列如何在计算机中,实现,？,队列的,顺序,存储结构？,栈的,链式,存储结构？,?,!,【,教学内容,】,队列、存储结构、基本操作实现算法以及队列的应用。,【,教学要求,】,掌握队列逻辑结构的特点。,掌握链队列和循环队列两种队列的基本操作实现方法。,掌握队列的在实际问题应用。,【,重点与难点,】,链队列和循环队列两种存储基本操作实现算法,循环队列基本算法实现，假,溢出的解决方案，队空、队满的判定条件；队列的在实际问题中应用,4.3,队列 （,排队买票,）,4.3.1,队列的结构特点和操作,队列的定义,队列：,线性表,(queue),特点：先进先出,(FIFO,结构,),。,队尾,队头,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队头,队尾,当队列中没有元素时称为,空队列,。,表尾称为队尾,(rear),表头称为队头,(front),插入元素称为入队,删除元素称为出队,限定在表的一端插入、另一端删除,。,队列的抽象数据类型的定义,ADT Queue,数据对象：,D,a,i,|,a,i,ElemSet,i,=1,2,.,n,n,0,数据关系：,R1,|,a,i,-1,a,i,D,i,=2,.,n,约定其中,a,1,端为队列头，,a,n,端为队列尾。,基本操作：,InitQueue(&Q),操作结果：,构造一个空队列,Q,。,DestroyQueue(&Q),初始条件：,队列,Q,已存在。,操作结果：,队列,Q,被销毁，不再存在。,QueueEmpty(Q),初始条件：,队列,Q,已存在。,操作结果：,若,Q,为空队列，则返回,TRUE,，,否则返回,FALSE,。,QueueLength(Q),初始条件：,队列,Q,已存在。,操作结果：,返回,Q,的元素个数，即队列的长度。,GetHead(Q,&,e,),初始条件：,Q,为非空队列。,操作结果：,用,e,返回,Q,的队头元素。,ClearQueue(&Q),初始条件：,队列,Q,已存在。,操作结果：,将,Q,清为空队列。,EnQueue(&Q,e,),初始条件：,队列,Q,已存在。,操作结果：,插入元素,e,为,Q,的新的队尾元素。,DeQueue(&Q,&,e,),初始条件：,Q,为非空队列。,操作结果：,删除,Q,的队头元素，并用,e,返回其值。,ADT Queue,4.3.2,队列的表示和实现,一、链队列：,用链表表示的队列。,是限制仅在表头删除和表尾插入的单链表。,一个链队列由一个头指针和一个尾指针唯一确定,。,（因为仅有头指针不便于在表尾做插入操作）。,为了操作的方便，也给链队列添加一个头结点，,因此，空队列的判定条件是：,头指针和尾指针都指,向头结点。,front,rear,rear,front,图,4.8,链队列示意图,队头,队尾,队列是,特殊的线性表,，因此也有,两种不同存储,表示方法。,链队列示意图,讨论：,空队列的特征？,Q,(,队尾,),(,队首,),front,a1,a2,a3,rear,p,front,rear,怎样实现入队和出队操作？,入队（尾部插入）：,rear-next=S;rear=S;,出队（头部删除）：,front-next=p-next;,队列会满吗？,front=rear,一般不会，因为删除时有,free,动作。除非内存不足！,队列是,特殊的线性表,，链队列与线性表的单链表结点表示一致，用,C,语言定义链队列结构如下：,typedef struct LNode,Elemtype data;,struct LNode *next;,LNnode,*LinkList;/,定义队列的结点,typedef LinkList QueuePtr,;/,链队列的结点结构和单链表相同，所以书上这样定义链队列结点。,typedef struct,QueuePtr front;/,队头指针,QueuePtr rear;/,队尾指针,LinkQueue;/,链队列,Status InitQueue_L(LinkQueue&Q),/,构造一个只含头节点空队列,Q,Q.front=Q.rear=new LNode;,Q.front-next=NULL;,/InitQueue_L,队列的基本操作在链队列中的实现：,队列的初始化操作：,a,1,a,2,a,3,Q.front,Q.rear,销毁队列操作：,=null,=null,Status DestroQueue_L(LinkQueue&Q),while(Q.front),Q.rear=Q.front-next;,delete(Q.front);,Q.front=Q.rear;,/while,rear,front,x,y,插入操作在链队列中的实现,p,p,void,EnQueue_L(LinkQueue&Q,QElemType e),/,插入元素,e,为,Q,的新的队尾元素,p=new LNode;/,分配结点单元,p-data=e;,p-next=NULL;,Q.rear-next=p;,Q.rear=p;,/EnQueue_L,front,rear,y,x,删除操作在链队列中的实现,p,p,bool DeQueue_L(LinkQueue&Q,QElemType&e),/,若队列不空，则删除,Q,的队头元素，用,e,返回其值，,/,并返回,TRUE,；否则返回,FLASE,if(Q.front=Q.rear)return FLASE;,p=Q.front-next;,e=p-data;,Q.front-next=p-next;,if(Q.rear=p)Q.rear=Q.front;,delete(p);,return TRUE;,/DeQueue_L,二、循,环队列,队列的顺序存储表示和实现,是限制仅在表头删除和表尾插入的顺序表。,头尾,指针,利用一组,地址连续,的存储单元,依次存放,队列中的数据元素。,rear,front,rear,front,J,1,J,2,J,3,头、尾指针和队列元素之间的关系,rear,front,J,3,rear,front,在非空队列里，头指针始终指向队头元素,尾指针始终指向队尾元素的下一位置。,因为：,队头和队尾的位置是变化的,，,所以：,设头、尾指针,。,初始化时的初始值均应置为,0,。,入队，尾指针增,1,出队，头指针增,1,头尾指针相等时队列为空,顺序队示意图,Q,(,队尾,),(,队首,),front,a,1,a,2,a,3,data,a,4,0,.,.,.,.,.,.,.,99,rear,队列会满吗？,很可能会，因为数组前端空间无法释放。因此,数组应当有长度限制。,空队列的特征？,约定：,front=rear,队尾后地址,入队,(,尾部插入,),：,vrear=e;rear+;,出队,(,头部删除,),：,x=vfront;front+;,讨论：,假溢出,有缺陷,怎样实现入队和出队操作？,在顺序队列中，当尾指针已经指向了队列的最后一个,位置即数组上界时，若再有元素入队，就会发生“,溢出,”。,“,假溢出,”,队列的存储空间未满，却发生了溢出。,rear,front,J,1,J,2,J,3,J,4,rear,front,J,3,J,4,(1),、平移元素：把元素平移到队列的首部。,效率低,。,解决“假溢出”的问题有两种可行的方法：,(2),、将新元素插入到第一个位置上，构成,循环队列,，,入队和出队仍按“先进先出”的原则进行。,操作效率、空间利用率高,。,rear,front,J,3,J,4,front,rear,J,3,J,4,a3,a2,a1,0,1,2,3,N-1,rear,front,循环队列（臆造）,顺序队列,a3,a2,a1,front,rear,0,1,2,3,.,.,.,N-1,新问题：,在循环队列中，空队特征是,front=rear,；,队满时也会有,front=rear,；,判决条件将出现二义性！,解决方案有三：,加设标志位，,用一个布尔变量以区别队列的空和满；,使用一个计数器记录队列中元素个数（即队列长度）；,人为浪费一个单元，令,队满特征为,front=(rear+1)%N,；,队空条件,:,front=rear,(,初始化时：,front=rear),队满条件,：,front=(rear+1)%N,(N=maxsize),队列长度：,L=,（,N,rear,front,）,%N,J2 J3,J1,J4,J5,front,rear,选用,空闲单元法：,即,front,和,rear,之一指向实元素，另一指向空闲元素。,问,2,：,在具有,n,个单元的循环队列中，队满时共有多少个元素？,n-1,个,5,问,1,：,左图中队列长度,L=,？,J6 J5,J7,J8 J9,例,1,：,一循环队列如下图所示，由图可知，队头和队尾指针的初态分别为,front=1,和,rear=0,。若先删除,4,个元素，接着再插入,4,个元素，请问队头和队尾指针分别指向哪个位置,?,J2 J3,J1 J4,J5,front,rear,front,rear,解：,删除,4,个元素后,front=(1+4),%,6=5,；,再插入,4,个元素后，,rear=(0+4),%,6=4,front,front,front,front,front,例,2,：,数组,n,用来表示一个循环队列，,f,为当前队列头元素的,前一,位置，,r,为队尾元素的位置。假定队列中元素的个数小于,n,，计算队列中元素的公式为,:,（）,r,f,（）（,n,f,r,）,%n,（）,n,r,f,（）（,n,r,f,）,%n,4,种公式哪种合理？,当,r f,时（,A,）合理；,当,r,MAXQSIZE,),rear=0;,else,rear+;,0,1,2,3,4,5,J5,J4,J3,rear,front,利用模运算可简化为：,rear=(rear+1)%,MAXQSIZE,void,InitQueue_Sq(SqQueue&Q,int maxsize=QUEUE_INIT_SIZE,int incresize=QUEUEINCTREMENT),/,构造一个空队列,Q,Q.elem=new QElemTypemaxsize+1;/,为循环队列分配（比,/,实际多一个元素，解决对列满的二义性）空间,Q.front=Q.rear=0;/,空队列,Q.queuesize=maxsize;/,初始化最大容量值,Q.increment=incresize;/,初始化扩容增量,/,InitQueue_Sq,队列的基本操作在循环队列中的实现：,队列的初始化：,Status QueueLength(SqQueue Q),/,返回队列,Q,的元素个数,return(Q.rear-Q.front);,int QueueLength_L(SqQueue Q),/,返回队列,Q,的元素个数,return(Q.rear-Q.front,+Q.queuesize)%Q.queuesize,;,/QueueLength_L,求循环队列的长度,考虑到循环队列,front,rear,J,3,J,4,front,rear,J,3,J,1,J,2,void EnQueue_L(SqQueue&Q,QElemType e),/,插入元素,e,为,Q,的新的队尾元素,Q.baseQ.rear=e;,Q.rear=(Q.rear+1)%MAXQSIZE;,return OK;,/EnQueue_L,void,EnQueue_L(SqQueue&Q,QElemType e),/,插入元素,e,为,Q,的新的队尾元素,if(Q.rear+1)%Q.queuesize=Q.front),incrementQueuementsize(Q);,/,队列满,，,进行扩容,Q.elemQ.rear=e;/,在队尾插入元素,Q.rear=(Q.rear+1)%Q.queuesize;,/,尾指针加,1,，考虑到循环队列。,插入操作在循环队列中的实现,front,rear,J,3,J,4,J,5,rear,bool,DeQueue_L(SqQueue&Q,ElemType&e),/,若队列不空，则删除,Q,的队头元素，,/,用,e,返回其值，并返回,TRUE;,否则返回,FLASE,if(Q.front=Q.rear)return FLASE;/,队列为空,e=Q.elemQ.front;/,从队列头出队,Q.front=(Q.front+1)%MAXQSIZE;,/,队列的头指针加,1,，考虑到循环情况,return TRUE;,删除操作在循环队列中的实现,rear,front,front,rear,J,3,J,1,J,2,front,讨论：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）；,操作系统中多道作业的处理（一个,CPU,执行多个作业）；,3.,简化程序设计。,答：,4.4,队列的应用举例,1,1 1,2,1 2 1,3,1 3 3 1,4,1 4 6 4 1,利用循环队列的计算过程：,假设只计算,2,行，,队列的最大容量为,5,。,front,rear,0,1,1,0,0,1,1,0,1,front,rear,2,1,1,0,1,front,rear,2,1,1,0,1,front,rear,2,1,0,0,1,front,rear,例,4.6,：,杨辉三角的计算,某运动会设立,N,个比赛项目，每个运动员可以参加一至三个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。,若将此问题抽象成数学模型，则归属于,“,划分子集,”,问题。,N,个比赛项目构成一个大小为,n,的集合，有同一运动员参加的项目则抽象为,“,冲突,”,关系。,例如：某运动会设有,9,个项目,:,A=0,，,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,七名运动员报名参加的项目分别为：,（,1,，,4,，,8,）、（,1,，,7,）、（,8,，,3,）、,（,1,，,0,，,5,）、（,3,，,4,）、（,5,，,6,，,2,）、,（,6,，,4,）,它们之间的冲突关系为,:R=,（,1,，,4,）,（,4,，,8,）,（,1,，,8,）,（,1,，,7,）,（,8,，,3,）,（,1,，,0,）,（,0,，,5,）,（,1,，,5,）,（,3,，,4,）,（,5,，,6,）,（,5,，,2,）,（,6,，,2,）,（,6,，,4,）,将集合,A,划分成,k,个互不相交的子集,A,1,，,A,2,，,，,A,k,（,kn,），,使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。,“,划分子集,”,问题即为,:,对前述例子而言，问题即为,:,同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。,可利用,“,过筛,”,的方法来解决划分子集问题。从第一个元素考虑起，,凡不和第一个元素发生冲突的元素都可以和它分在同一子集中,，然后再,“,过筛,”,出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止。,0,1,2,3,4,5,6,7,8,0,0,1,0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,1,1,2,0,0,0,0,0,1,1,0,0,3,0,0,0,0,1,0,0,0,1,4,0,1,0,1,0,0,1,0,1,5,1,1,1,0,0,0,1,0,0,6,0,0,1,0,1,1,0,0,0,7,0,1,0,0,0,0,0,0,0,8,0,1,0,1,1,0,0,0,0,012345678,14568,458,8,0 1 0 0 0 1 0 0 0,0 1 0 0 0 2 1 0 0,0 1 0 0 1 2 1 0 1,0 2 0 0 1 2 1 0 1,为了减少重复察看,R,数组的时间，可另设一个数组,clashn,记录和当前已入组元素发生冲突的元素的信息。,每次新开辟一组时，令,clash,数组各分量的值均为,“,0,”,，当序号为,“,i,”,的元素入组时，将和该元素发生冲突的信息记入,clash,数组。,pre(,前一个出队列的元素序号,)=n;,组号,=0;,全体元素入队列,;,while,(,队列不空,),队头元素,i,出队列,;,if,(i pre)/,开辟新的组,组号,+;clash,数组初始化,;,if,(i,能入组,),i,入组，记下序号为,i,的元素所属组号,;,修改,clash,数组,;,else,i,重新入队列,;,pre=i;,划分子集算法的基本思想,:,补例,2,：,CPU,资源的竞争问题,在多用户计算机系统中，各个用户需要使用,CPU,运行自己的程序，它们分别向操作系统提出使用,CPU,的请求，操作系统按照每个请求在时间上的先后顺序，,将其排成一个队列，每次把,CPU,分配给队头用户使用，,当相应的程序运行结束，则令其出队，再把,CPU,分配,给新的队头用户，直到所有用户任务处理完毕。,补,例,3,：主机与外部设备之间速度不匹配的问题。,以主机和打印机为例来说明，主机输出数据给打印,机打印，主机输出数据的速度比打印机打印的速度要快,得多，若直接把输出的数据送给打印机打印，由于速度,不匹配，显然不行。,解决的方法,是设置一个打印数据缓,冲区，主机把要打印的数据依此写到这个缓冲区中，写,满后就暂停输出，继而去做其它的事情，打印机就从缓,冲区中按照先进先出的原则依次取出数据并打印，打印,完后再向主机发出请求，主机接到请求后再向缓冲区写,入打印数据，这样利用队列既保证了打印数据的正确，,又使主机提高了效率。,讨论（代本章小结）,线性表、栈与队的异同点,相同点：,逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即,受限的线性表,（只是对插入、删除运算加以限制）。,不同点：,运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表,LIFO,；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表,FIFO,。,用途不同，线性表比较通用；栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,选择题部分,1,、循环队列用数组,A0,m,-1,存放其元素值，已知其头尾指,针分别是,front,和,rear,则当前队列中的元素个数是（）。,(A)(rea