《队列及其实现》ppt课件

《《队列及其实现》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、队列及其实现1HoufengWang,ICLofPKU排队上车rearBusStopfront排队上车BusStopfrontrearBusStopQueueBusStopfrontrear队列的特点队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的这一端叫队列的头，允许进行插入的这一端叫队列的尾。当队列中没有任何元素时，称为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。5HoufengWang,ICLofPKU队列也称作先进先出表(FirstInFirstOut表，简称FIFO表）图4.7

2、是队列的示意图6HoufengWang,ICLofPKU队列的基本运算1.QueuecreateEmptyQueue(void)创建一个空队列2.intisEmptyQueue(Queuequ)判队列qu是否为空队列，当qu为空队列时取真值，否则取假值3.voidenQueue(Queuequ,DataTypex)往队列qu中插入一个值为x的元素4.voiddeQueue(Queuequ)从队列qu中删除一个元素5.DataTypefrontQueue(Queuequ)求队列qu头部元素的值7HoufengWang,ICLofPKU队列的实现8HoufengWang,ICLofPKU顺

3、序表示队列的顺序表示，约定：队头指针指出实际队头元素所在的位置，而队尾指针指出实际队尾元素所在位置的下一个位置。结构定义：#defineMAXNUM//队列中最大元素个数structSeqQueue//顺序队列类型定义{DataTypeq[MAXNUM];intf,r;//f指向队列头，r指向队列尾};typedefstructSeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/9HoufengWang,ICLofPKU设paqu是PSeqQueue类型的变量，则头变量paqu->f存放即将要被删除的元素的下标，尾变量paqu->r存放即将要被插入的元素（当前还不是队列

4、中的元素）的下标。初始时paqu->f=paqu->r=0。队列中元素的个数可以用paqu->r-paqu->f计算得到，当paqu->r=paqu->f时，元素的个数为0，即为空队列。例子：观察变化过程约定10HoufengWang,ICLofPKU11HoufengWang,ICLofPKU基本运算PSeqQueuecreateEmptyQueue_seq(void)创建一个空队列，返回指向空队列的指针。2.intisEmptyQueue_seq(PSeqQueuepaqu)判断paqu所指的队列是否为空队列，当paqu所指的队列为空队列时，则返回1，否则返回0。12Houfeng

5、Wang,ICLofPKUPSeqQueuecreateEmptyQueue_seq(void)//创建一个空队列，返回指向空队列的指针{PseqQueuepsqu;psqu=(PseqQueue)malloc(sizeof(structSeqQueue));if(psqu!=NULL){psqu->r=0;psqu->f=psqu->r;}return(psqu);}13HoufengWang,ICLofPKUintisEmptyQueue_seq(PSeqQueuepaqu)//判断paqu所指的队列是否为空队列，当paqu所指的队//列为空队列时，则返回1，否则返回0{ret

6、urn(paqu->r==0);}14HoufengWang,ICLofPKUvoidenQueue_seq(PSeqQueuepaqu,DataTypex)进队列运算，表示往paqu所指的队列中插入一个值为ｘ的元素。voiddeQueue_seq(PSeqQueuepaqu)出队列运算，表示从paqu所指的队列中删除一个元素。DataTypefrontQueue_seq(PSeqQueuepaqu)当paqu所指的队列不空时，求队列头部元素的值，队列保持不变。自己实现上述三个算法（！！）15HoufengWang,ICLofPKU当队列满时，再作进队操作，这种现象称为上溢；当队空时，

7、作删除操作，这种现象称为下溢。溢出现象在运算中都要考虑。当paqu->r=MAXNUM时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）位置，这种现象称为假溢出。队列的溢出16HoufengWang,ICLofPKU解决假溢出通常采用的方法是：把数组paqu->q[MAXNUM]从逻辑上看成一个环，即规定paqu->q[0]是paqu->q[MAXNUM-1]的下一个元素。当paqu->q[MAXNUM-1]已经插入元素以后