队列(Queue)new

1、13.4 队列(Queue)队列是一种队列是一种先进先出先进先出(First In First Out-(First In First Out-FIFOFIFO) ) 的线性表的线性表. .它只允许在表的一端进行插入它只允许在表的一端进行插入, ,而在另一端删除元素而在另一端删除元素. .),(21naaaqa1a2a3an.入队列队头队尾队头（队头（front）: 线性表的表头端，即可删除端。线性表的表头端，即可删除端。队尾（队尾（rear）: 线性表的表尾端，即可插入端。线性表的表尾端，即可插入端。考考2),(21naaaq出队列a1a2a3an.队头队尾队列是一种先进先出(First I

2、n First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列(Queue)3),(21naaaq出队列a1a2a3an.队头队尾队列是一种先进先出(First In First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列(Queue)4),(21naaaq出队列a1a2a3an.队头队尾队列是一种先进先出(First In First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列(Queue)5),(21naaaq出队列a1a2a3

3、an.队头队尾队列是一种先进先出(First In First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列(Queue)6),(21naaaq出队列a1a2a3an.队头队尾队列是一种先进先出(First In First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列(Queue)7),(21naaaqa1a2a3an.出队列入队列队头队尾队列是一种先进先出(First In First Out-FIFOFIFO) 的线性表.它只允许在表的一端进行插入,而在另一端删除元素.3.4 队列

4、(Queue)80n , 2 , 1,|niElemSetaaDii队列的抽象数据类型数据对象:数据关系:端为队列尾端为队列头约定n1111a ,a , 2 , 1,| ,niDaaaaRiiiiADT Queue 9 (1) InitQueue (&Q) /构造空队列 (2) DestroyQueue (&Q) /销毁队列 (3) ClearQueue (&Q) /清空队列 (4) QueueEmpty(Q) /判空. 空-TRUE (5) QueueLength(Q) /求队列长度 (6) GetHead (Q,&e) /取队头元素, (7) EnQueue

5、 (&Q,e) /入队列 (8) DeQueue (&Q,&e) /出队列 (9) QueueTraverse(Q,visit() /遍历ADT Queue基本操作:10Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear 3.4.2 3.4.2 队列的顺序存储队列的顺序存储 循环队列循环队列6 6重点重点!11Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J1入队：入队：Q.rear=Q.rear+112Q.frontQ.front0 01 12 23 34 45 5Q.

6、rearQ.rear队列的顺序存储6 6J1J2入队：入队：Q.rear=Q.rear+113Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J1J2J3入队：入队：Q.rear=Q.rear+114Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J1J2J3J4入队：入队：Q.rear=Q.rear+1出队：出队：Q.front=Q.front+115Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J2J3J4J1

7、入队：入队：Q.rear=Q.rear+1出队：出队：Q.front=Q.front+1“逻辑上”删除16Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J3J4J1J2出队：出队：Q.front=Q.front+1入队：入队：Q.rear=Q.rear+1“逻辑上”删除17Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J4J2J1J3出队：出队：Q.front=Q.front+1入队：入队：Q.rear=Q.rear+1“逻辑上”删除18Q.frontQ.front0 0

8、1 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J4J5J2J1J3出队：出队：Q.front=Q.front+1入队：入队：Q.rear=Q.rear+1“逻辑上”删除19Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储6 6J4J5J6J2J1J3出队：出队：Q.front=Q.front+1入队：入队：Q.rear=Q.rear+1“逻辑上”删除20Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rear队列的顺序存储“假溢出假溢出”6 6J4J5J6J7J2J1J3出队：出队

9、：Q.front=Q.front+1入队：入队：Q.rear=Q.rear+1“逻辑上”删除非循环队列非循环队列缺点缺点!21n队空：队空：Q.front=Q.rearn队满：队满：Q.rear=maxsize（假溢出）（假溢出）求队长：求队长： Q.rear-Q.frontn 入队：新元素按入队：新元素按 rear 指示位置加入，指示位置加入，再将队尾指针加一再将队尾指针加一 ，即，即 rear = rear + 1n 出队：将出队：将front指示的元素取出，再将队指示的元素取出，再将队头指针加一，即头指针加一，即front = front + 1，非循环队列非循环队列考考22Q.fron

10、tQ.front0 01 12 23 34 45 5Q.rearQ.rear6 6J4J5J6J7循环队列J2J1J30 01 12 23 34 45 56 6J4J5J6J7Q.frontQ.frontQ.rearQ.rearJ2J1J3如何解决“假溢出”？ 为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾

11、指针仍要加。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不，朝前移动。只不过当头尾指针指向向量上界（过当头尾指针指向向量上界（QueueSize-1）时，其加）时，其加1操作的结果是指向向量的下操作的结果是指向向量的下界界0。230 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rear入队列：入队列：Q.front=(Q.front+1) % N出队列：出队列：Q.rear=(Q.rear+1) % N队列长度队列长度：(Q.rear-Q.front+N) % NJ2J1J3240123456J4J5J6J7循环

12、队列Q.frontQ.frontQ.rearQ.rearJ8J2J3250 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J3260 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”270 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”0 01 12 23 34 45 56 6J4J5J6J7Q.frontQ.frontQ.re

13、arQ.rearJ2J1J3280 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”0 01 12 23 34 45 56 6J5J6J7Q.frontQ.frontQ.rearQ.rearJ2J1J3J4290 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”0 01 12 23 34 45 56 6J6J7Q.frontQ.frontQ.rearQ.rearJ4J2J1J3J5300 01 12 23

14、 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”0 01 12 23 34 45 56 6J7Q.frontQ.frontQ.rearQ.rearJ6J4J2J1J3J5310 01 12 23 34 45 56 6J4J5J6J7循环队列Q.frontQ.frontQ.rearQ.rearJ8J9J10队列队列“满满”0 01 12 23 34 45 56 6Q.frontQ.frontQ.rearQ.rear队列队列“空空”Q.front=Q.rear ?J7J6J4J2J1J3J5 由于入队时尾指针向前追赶头

15、指针，出队时头指针向前追由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过通过Q.front=Q.rear来判断队列来判断队列“空空”还是还是“满满”。32如何解决判断队列如何解决判断队列“空空”还是还是“满满”？解决此问题的方法：解决此问题的方法： 其一是另设一个标志位其一是另设一个标志位(布尔变量布尔变量)以区别队列的以区别队列的空和满；空和满； 其二是少用一个元素的空间，约定入队前，测试其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加尾指针在循环意义下加1后是否等

16、于头指针，若相后是否等于头指针，若相等则认为队满等则认为队满(注意：注意：rear所指的单元始终为所指的单元始终为空空); 其三是设置一个计数器其三是设置一个计数器,设为设为count,初始时置为初始时置为0,每当有一个元素入队列操作成功每当有一个元素入队列操作成功,则则count加加1,每当每当有一个元素出队列操作成功有一个元素出队列操作成功,则则count减减1.则可以通则可以通过判断过判断count是否等于是否等于0来判断队列是否空来判断队列是否空,而队列而队列满的判断方法为满的判断方法为count=MaQueueSize. 33队空：Q.count=0队满： Q.count= maxS

17、ize 或 Q.count0&Q.rear=Q.front入队: Q.rear = (Q.rear + 1) % maxSize出队: Q.front = (Q.front + 1) % maxSize;求队长:Q.count总结：循环队列总结：循环队列 (采用上面的第三种方法采用上面的第三种方法) 显然，因为循环队列元素的空间可以被利用，显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，溢。因此，除一些简单的应用外，真正实用的顺序队真正实用的顺序队列是循环队列。列是循环队列

18、。考考34循环队列的存储结构#define MAXQSIZE 100 /最大队列长度typedef struct QDataType queueMAXQSIZE; /初始化的动态分配存储空间 int front; /头指针,若队列不空,指向队列头元素. int rear; /尾指针,若队列不空,指向队列尾元素的下一个位置队列尾元素的下一个位置. int count; /计数器SqQueue; SqQueue Q;rearfrontbaseQElemTypeQ考考属于属于顺序顺序存储结构存储结构!下下标标35int InitQueue (SqQueue *pQ) /构造一个空队列Q pQ-fro

19、nt=pQ-rear=pQ-count=0; return 1;/InitQueue(1)循环队列初始化00baseQ012maxsize36 int QueueEmpty (SqQueue Q) if (Q.count!=0) return 1; else return 0; / QueueEmpty(4)队列是否为空543210Q.rearQ.front37 int QueueLength (SqQueue Q) return Q.count; / QueueLength(5)求队列长度543210J3J4J5Q.rearQ.front38 int GetHead (SqQueue Q,

20、DataType *e) if(Q.count=0) return 0; *e=Q.queueQ.front; return 1; / GetHead(6)取队头元素543210J3J4J5Q.rearQ.front39int EnQueue(SqQueue *pQ,DataType e) if(pQ-count0 & pQ-rear=pQ-front) return 0;/队列满 pQ-queuepQ-rear=e; pQ-rear=(pQ-rear+1)%MAXQSIZE; pQ-count+; return 1;/EnQueue(7)入队列543210J3J4J5pQ-queue

21、pQ-rear=epQ-rear=(pQ-rear+1)%NepQpQ-front-frontQ.rearQ.rearpQpQ-rear-rear考考40int DeQueue (LinkQueue *pQ,DataType *e) if(pQ-count=0) return 0; *e=pQ-queuepQ-front; pQ-front=(pQ-front+1)%MAXQSIZE; pQ-count-; return 1;/DeQueue(8)出队列543210J3J4J5Q.frontQ.frontpQpQ-rear-rearpQpQ-front-front *e=pQ-queuepQ-

22、front; pQ-front=(pQ-front+1)%MAXQSIZE;考考413.4.2 3.4.2 链队列链队列( (了解了解!)!) 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针头指针和尾指针尾指针唯一确定。42null*qq.frontq.rear非空队列q.frontq.rearnull空队列*qn链队列示意图43单链队列-队列的链式存储结构Typedef struct QNode QElemType data; struct Qnode

23、 *next;Qnode, *QueuePtr;Typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue; .datanext队头队尾Q.frontQ.rear 和顺序队列类似，我们也是和顺序队列类似，我们也是将这两个指针封装在一起，将将这两个指针封装在一起，将链队列的类型链队列的类型LinkQueue定义定义为一个结构类型：为一个结构类型：44(1)链队列初始化Status InitQueue (LinkQueue &Q) Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNo

24、de); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;/InitQueueQ.frontQ.rear45(5)入队列a1a2anQ.rearQ.frontepQ.rearp-data=ep-next=NULLQ.rear-next=pQ.rear=pStatus EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p;

25、 Q.rear=p; return OK;/EnQueue46Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; /只有一个元素时只有一个元素时 free(p); return OK;/DeQueue(6)出队列a1a2anQ.rearQ.frontpp=Q.front-nextQ.front-next=p-next47Statu

26、s DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK:/ DestroyQueue(7)销毁队列a1a2anQ.rearQ.front48队列的应用队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。 第一个例子第一个例子就是就是CPUCPU资源的竞争问题。在具有多个终资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用端的计算机系统中，

27、有多个用户需要使用CPUCPU各自运行自各自运行自己的程序，它们分别通过各自终端向操作系统提出使用己的程序，它们分别通过各自终端向操作系统提出使用CPUCPU的请求，操作系统按照每个请求在时间上的先后顺序，的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把将其排成一个队列，每次把CPUCPU分配给队头用户使用，当分配给队头用户使用，当相应的程序运行结束，则令其出队，再把相应的程序运行结束，则令其出队，再把CPUCPU分配给新的分配给新的队头用户，直到所有用户任务处理完毕。队头用户，直到所有用户任务处理完毕。银行!49第二个例子第二个例子就是主机与外部设备之间速度不匹配的就

28、是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事这个缓冲区中，写满后就暂停输出，继而去做

29、其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。打印数据的正确，又使主机提高了效率。50 例例3.6 什么是队列的上溢现象和假溢出现象？解决什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？它们有哪些方法？ 答答:在队列的顺序存储结构中在队列的顺序存储结构中,设头指针为设头指针为front,队尾队尾指针指针re

30、ar,队的容量队的容量(存储空间的大小存储空间的大小)为为MaxSize。当有。当有元素加入到队列时元素加入到队列时,若若 rear=MaxSize(初始时初始时rear=0)则则发生队列的上溢现象发生队列的上溢现象,该元素不能加入队列。该元素不能加入队列。 特别要注意的是队列的假溢出现象特别要注意的是队列的假溢出现象:队列中还有剩队列中还有剩余空间但元素却不能进入队列余空间但元素却不能进入队列,造成这种现象的原因是造成这种现象的原因是由于队列的操作方法所致。由于队列的操作方法所致。 队列的应用例子队列的应用例子51 解决队列上溢的方法有以下几种解决队列上溢的方法有以下几种: (1)建立一个足够大的存储空间建立一个足够大的存储空间,但这样做会造成空间但这样做会造成空间的使用效率降低。的使用效率降低。 (2)当出现假溢出时可采用以下几种方