队列及其实现-ppt课件

1、队列及其实现队列及其实现排队上车rearBus Stopfront排队上车Bus StopfrontrearBus Stop QueueBus Stopfrontrear队列的特点 队列也是一种特殊的线性表，是一种只允许在队列也是一种特殊的线性表，是一种只允许在表的一端进展插入操作，而在另一端进展删除表的一端进展插入操作，而在另一端进展删除操作的线性表。允许进展删除的这一端叫队列操作的线性表。允许进展删除的这一端叫队列的头，允许进展插入的这一的头，允许进展插入的这一 端叫队列的尾。当端叫队列的尾。当队列中没有任何元素时，称为空队列。队列中没有任何元素时，称为空队列。 队列的插入操作通常称为进队

2、列或入队列，队队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。列的删除操作通常称为退队列或出队列。 队列也称作先进先出表(First In First Out表，简称FIFO表图4.7是队列的表示图队列的根本运算1. Queue createEmptyQueue ( void ) 创建一个空队列2. int isEmptyQueue ( Queue qu ) 判队列qu能否为空队列，当qu为空队列时取真值，否那么取假值 3. void enQueue ( Queue qu, DataType x ) 往队列qu中插入一个值为x的元素4. void deQueue (

3、 Queue qu ) 从队列qu中删除一个元素 5. DataType frontQueue ( Queue qu ) 求队列qu头部元素的值 队列的实现顺序表示 队列的顺序表示，商定：队头指针指出实践队头元素所在的位置，而队尾指针指出实践队尾元素所在位置的下一个位置。 构造定义： #define MAXNUM / 队列中最大元素个数struct SeqQueue/ 顺序队列类型定义 DataType qMAXNUM; int f,r; /f 指向队列头，r 指向队列尾 ;typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */ 设paqu是

4、PSeqQueue类型的变量，那么头变量paqu-f存放即将要被删除的元素的下标，尾变量paqu-r存放即将要被插入的元素当前还不是队列中的元素的下标。 初始时paqu-f = paqu-r = 0。 队列中元素的个数可以用paqu-r - paqu-f计算得到，当paqu-r = paqu-f时，元素的个数为0，即为空队列。 例子：察看变化过程商定根本运算PSeqQueue createEmptyQueue_seq( void )创建一个空队列，前往指向空队列的指针。2. int isEmptyQueue_seq( PSeqQueue paqu )判别paqu所指的队列能否为空队列，当paq

5、u所指的队列为空队列时，那么前往1，否那么前往0。PSeqQueue createEmptyQueue_seq( void )/ 创建一个空队列，前往指向空队列的指针 PseqQueue psqu; psqu=(PseqQueue) malloc(sizeof(struct SeqQueue); if (psqu!=NULL)psqu-r=0;psqu-f= psqu-r; return(psqu);int isEmptyQueue_seq( PSeqQueue paqu )/ 判别paqu所指的队列能否为空队列，当paqu所指的队/ 列为空队列时，那么前往1，否那么前往0 return(pa

6、qu-r= =0);void enQueue_seq( PSeqQueue paqu, DataType x )进队列运算，表示往paqu所指的队列中插入一个值为的元素。 void deQueue_seq( PSeqQueue paqu )出队列运算，表示从paqu所指的队列中删除一个元素。DataType frontQueue_seq( PSeqQueue paqu )当paqu所指的队列不空时，求队列头部元素的值，队列坚持不变。本人实现上述三个算法！ 当队列满时，再作进队操作，这种景象称为上溢； 当队空时，作删除操作，这种景象称为下溢。 溢出景象在运算中都要思索。 当paqu-r = MA

7、XNUM时，再作插入运算就会产生溢出，假设这时队列的前端还有许多空的可用的位置，这种景象称为假溢出。队列的溢出 处理假溢出通常采用的方法是：把数组paqu-qMAXNUM从逻辑上看成一个环，即规定paqu-q0是paqu-qMAXNUM - 1的下一个元素。当paqu-qMAXNUM - 1曾经插入元素以后，就把paqu-r置成0，再有元素要插入时，就插到paqu-q0的位置上，这种队列也称为环形队列 环形队列空与满的区别：牺牲队列中的一个结点，当队列中已有MAXNUM - 1个结点时就称满，再要插入就发生溢出 见图4.9环形队列中队列根本运算的算法1. PSeqQueue createEmp

8、tyQueue_seq( void )为队列构造恳求空间，创建一个空队列。 *创建一个空队列同前创建一个空队列同前 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); int isEmptyQueue_seq( PSeqQueue paqu )判别paqu所指的队列能否为空队列。

9、请与前面非循环队列区别int isEmptyQueue_seq( PSeqQueue paqu ) return (paqu-f = paqu-r); 3. void enQueue_seq( PSeqQueue paqu, DataType x )当队列不满时，将元素x插入paqu所指的队列中。 void enQueue_seq( PSeqQueue paqu, DataType x )/* 在队列中插入一元素x */ if( (paqu-r + 1) % MAXNUM = paqu-f ) printf( Full queue.n ); else paqu-qpaqu-r = x; paq

10、u-r = (paqu-r + 1) % MAXNUM; 4. void deQueue_seq( PSeqQueue paqu )出队列运算，当队列不空时，从paqu所指的队列中删除一个元素void deQueue_seq( PSeqQueue paqu )/* 删除队列头部元素 */ if( paqu-f = paqu-r )printf( Empty Queue.n ); elsepaqu-f = (paqu-f + 1) % MAXNUM;5. DataType frontQueue_seq( PSeqQueue paqu )当paqu所指的队列不空时，取队列头部元素，队列本身坚持不变

11、。 DataType frontQueue_seq( PSeqQueue paqu )/* 对非空队列,求队列头部元素 */ return (paqu-qpaqu-f); 链接表示lastNodeabcdenullfirstNodefrontrear队列的链接表示 链接结点的构造定义：struct Node;typedef struct Node *PNode;struct Node/ 结点构造 DataType info; PNode link; ;队列的链接构造封装struct LinkQueue / 链接队列类型定义 PNode f; / 头指针 PNode r; / 尾指针 ;实践运用

12、中，经常运用的是链接队列类型的指针类型，因此常有如下定义：typedef struct LinkQueue *PLinkQueue;链接队列中根本运算的实现1. PLinkQueue createEmptyQueue_link( )恳求队列构造空间，创建一个空队列。 PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; plqu-r = NULL; else printf(Ou

13、t of space! n); return (plqu); 2. int isEmptyQueue_link( PLinkQueue plqu )判别plqu所指的队列能否为空队列，当plqu所指的队列为空队列时，那么前往1，否那么前往0。 判别链接表示队列能否为空队列 int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL); 3. void enQueue_link( PLinkQueue plqu, Datatype x )进队列运算，往plqu所指的队列中插入一个值为x的元素。 void enQueue_link(

14、 PLinkQueue plqu, Datatype x ) PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!); else p-info = x; p-link = NULL; if (plqu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r-link = p; plqu-r = p; 4. void deQueue_link( PLinkQueue plqu ) 出队列运算，表示从plqu所指的队列中删除队列头部元素。void deQueue_link( PLinkQueue plqu ) PNode p; if( plqu-f = NULL ) printf( Empty queue.n ); else p = plqu-f;plqu-f = plqu-f-link;free(p); 5. Datatype frontQueue_link( PLinkQueue plqu )当plqu所指的队列不为空时，取队列头部元素的值，队列坚持不变。Datatype frontQueue_link( PLinkQueue plqu )/* 在非空队列中求队头元素 */ return (