队列及其实现.ppt
《队列及其实现.ppt》由会员分享,可在线阅读,更多相关《队列及其实现.ppt(35页珍藏版)》请在三一文库上搜索。
1、Houfeng Wang, ICL of PKU,1,队列及其实现,排队上车,排队上车,Bus Stop Queue,Houfeng Wang, ICL of PKU,5,队列的特点,队列也是一种特殊的线性表,是一种只允许在表的一端进行插入操作,而在另一端进行删除操作的线性表。允许进行删除的这一端叫队列的头,允许进行插入的这一 端叫队列的尾。当队列中没有任何元素时,称为空队列。 队列的插入操作通常称为进队列或入队列,队列的删除操作通常称为退队列或出队列。,Houfeng Wang, ICL of PKU,6,队列也称作先进先出表(First In First Out表,简称FIFO表)图4.7
2、是队列的示意图,Houfeng Wang, ICL of PKU,7,队列的基本运算,1. Queue createEmptyQueue ( void ) 创建一个空队列 2. int isEmptyQueue ( Queue qu ) 判队列qu是否为空队列,当qu为空队列时取真值,否则取假值 3. void enQueue ( Queue qu, DataType x ) 往队列qu中插入一个值为x的元素 4. void deQueue ( Queue qu ) 从队列qu中删除一个元素 5. DataType frontQueue ( Queue qu ) 求队列qu头部元素的值,Hou
3、feng Wang, ICL of PKU,8,队列的实现,Houfeng Wang, ICL of PKU,9,顺序表示,队列的顺序表示,约定:队头指针指出实际队头元素所在的位置,而队尾指针指出实际队尾元素所在位置的下一个位置。 结构定义: #define MAXNUM / 队列中最大元素个数 struct SeqQueue / 顺序队列类型定义 DataType qMAXNUM; int f,r; /f 指向队列头,r 指向队列尾 ; typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */,Houfeng Wang, ICL of PKU
4、,10,设paqu是PSeqQueue类型的变量,则头变量paqu-f存放即将要被删除的元素的下标,尾变量paqu-r存放即将要被插入的元素(当前还不是队列中的元素)的下标。 初始时paqu-f = paqu-r = 0。 队列中元素的个数可以用paqu-r - paqu-f计算得到,当paqu-r = paqu-f时,元素的个数为0,即为空队列。 例子:观察变化过程,约定,Houfeng Wang, ICL of PKU,11,Houfeng Wang, ICL of PKU,12,基本运算,PSeqQueue createEmptyQueue_seq( void ) 创建一个空队列,返回指
5、向空队列的指针。 2. int isEmptyQueue_seq( PSeqQueue paqu ) 判断paqu所指的队列是否为空队列,当paqu所指的队列为空队列时,则返回1,否则返回0。,Houfeng Wang, ICL of PKU,13,PSeqQueue createEmptyQueue_seq( void ) / 创建一个空队列,返回指向空队列的指针 PseqQueue psqu; psqu=(PseqQueue) malloc(sizeof(struct SeqQueue); if (psqu!=NULL) psqu-r=0; psqu-f= psqu-r; return(p
6、squ); ,Houfeng Wang, ICL of PKU,14,int isEmptyQueue_seq( PSeqQueue paqu ) / 判断paqu所指的队列是否为空队列,当paqu所指的队/ 列为空队列时,则返回1,否则返回0 return(paqu-r= =0); ,Houfeng Wang, ICL of PKU,15,void enQueue_seq( PSeqQueue paqu, DataType x ) 进队列运算,表示往paqu所指的队列中插入一个值为的元素。 void deQueue_seq( PSeqQueue paqu ) 出队列运算,表示从paqu所指的
7、队列中删除一个元素。 DataType frontQueue_seq( PSeqQueue paqu ) 当paqu所指的队列不空时,求队列头部元素的值,队列保持不变。 自己实现上述三个算法(!),Houfeng Wang, ICL of PKU,16,当队列满时,再作进队操作,这种现象称为上溢; 当队空时,作删除操作,这种现象称为下溢。 溢出现象在运算中都要考虑。 当paqu-r = MAXNUM时,再作插入运算就会产生溢出,如果这时队列的前端还有许多空的(可用的)位置,这种现象称为假溢出。,队列的溢出,Houfeng Wang, ICL of PKU,17,解决假溢出通常采用的方法是:把数
8、组paqu-qMAXNUM从逻辑上看成一个环,即规定paqu-q0是paqu-qMAXNUM - 1的下一个元素。当paqu-qMAXNUM - 1已经插入元素以后,就把paqu-r置成0,再有元素要插入时,就插到paqu-q0的位置上,这种队列也称为环形队列 环形队列空与满的区别:牺牲队列中的一个结点,当队列中已有MAXNUM - 1个结点时就称满,再要插入就发生溢出 (见图4.9),Houfeng Wang, ICL of PKU,18,Houfeng Wang, ICL of PKU,19,环形队列中队列基本运算的算法,1. PSeqQueue createEmptyQueue_seq(
9、 void ) 为队列结构申请空间,创建一个空队列。,Houfeng Wang, ICL of PKU,20,*创建一个空队列(同前),PSeqQueue createEmptyQueue_seq( void ) PSeqQueue paqu; paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (paqu=NULL) printf(“Out of space! n“); else paqu-f = 0; paqu-r = 0; return (paqu); ,Houfeng Wang, ICL of PKU,21,int isEmptyQ
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列 及其 实现
链接地址:https://www.31doc.com/p-2588627.html