《数据结构32队列》由会员分享，可在线阅读，更多相关《数据结构32队列（26页珍藏版）》请在金锄头文库上搜索。
1、3.4 队列队列3.4.1 队列的定义队列的定义队列队列：只允许在表的一端进行插入操作：只允许在表的一端进行插入操作( (入队入队列列) )，在另一端进行删除操作（，在另一端进行删除操作（出队列出队列）的）的线性表。线性表。队头队头( (front)front)：允许删除的一端。允许删除的一端。队尾队尾( (rear)rear)：允许插入的一端。允许插入的一端。出队列出队列 入队列入队列 a1 a2 an 队头元素队头元素 队尾元素队尾元素1队列的基本运算：队列的基本运算：（1 1）队列初始化：）队列初始化：InitQueue(Q)InitQueue(Q) 结果：设置一个空队列结果：设置一个空
2、队列Q Q。（2 2）入队列：入队列：EnQueue(Q,x)EnQueue(Q,x) 结果：将结果：将x x插入到队列插入到队列Q Q的队尾。的队尾。（3 3）出队列：）出队列：OutQueue(Q,x)OutQueue(Q,x) 结果：将队头元素赋给结果：将队头元素赋给x x，并删除队头。并删除队头。（4 4）判队列空：）判队列空：EmptyQueue(Q)EmptyQueue(Q) 结果：若队列为空，返回结果：若队列为空，返回1 1，否则返回，否则返回0 0。（5 5）读队头：）读队头：GetHead(Q,x)GetHead(Q,x) 结果：将队头元素赋给结果：将队头元素赋给x x，不删
3、除队头。不删除队头。23.4.2 队列的存储结构和基本运算的实现队列的存储结构和基本运算的实现 一、队列的顺序存储结构一、队列的顺序存储结构 在顺序存储结构中，除了用容量足够大的在顺序存储结构中，除了用容量足够大的数组数组外，还需要两个指针：外，还需要两个指针： 尾指针尾指针：指向队尾元素在队列中的：指向队尾元素在队列中的当前当前位置。位置。 头指针头指针：指示队列中队头元素的：指示队列中队头元素的前一个前一个位置。位置。3 队列的类型定义队列的类型定义： # #define MAXSIZE 100 /define MAXSIZE 100 /最大队列长度最大队列长度 typedef struc
4、t typedef struct DataType dataMAXSIZE; / DataType dataMAXSIZE; / 动态分配存储空间动态分配存储空间 int rear; /int rear; /尾指针，若队列不空，指向队列尾元素尾指针，若队列不空，指向队列尾元素 int front;/int front;/头指针，若队列不空，指向队列头元素头指针，若队列不空，指向队列头元素 / / 的前一个位置的前一个位置 SqQueueSqQueue; ; 如：如：SqQueue sq; sqSqQueue sq; sq是一个顺序队列是一个顺序队列4 sqsq是一顺序队列是一顺序队列 队尾队尾
5、 . . 4 d sq.rear 3 c 2 b 1 a 0 sq.front 队头队头空队列空队列：sqsq.front=.front=sqsq.rear=0.rear=0入队列：入队列：入队列时尾指针加入队列时尾指针加1 1sq.rear=sq.rear+1;sq.rear=sq.rear+1;sq.datasq.rear=x;sq.datasq.rear=x;出队列：出队列：出队列时头指针加出队列时头指针加1 1 sq.front=sq.front+1;sq.front=sq.front+1;假溢出现象假溢出现象( (队头有空间队头有空间) )：当当sq.rear=MAXSIZE-1sq
6、.rear=MAXSIZE-1时，无时，无法再继续入队列。法再继续入队列。MAXSIZE-15为了有效地利用存储空间，将队列看成是一个循为了有效地利用存储空间，将队列看成是一个循环队列。环队列。即即sq.data0sq.data0接在接在sq.dataMAXSIZE-1sq.dataMAXSIZE-1之后，之后，如果如果sq.rear+1=MAXSIZE,sq.rear+1=MAXSIZE,则令则令sq.rear=0sq.rear=0。 601234567front01234567front01234567frontrearAABCrearrear空队列空队列A进进队队B, C进进队队0123
7、456701234567A退退队队B退退队队01234567D,E,F,G,H,I 进进队队 队满队满frontB CrearfrontCrearfrontCrearDEF GHI7入队列入队列：sq.rear=(sq.rear+1)%MAXSIZE;sq.datasq.rear = x;出队列出队列：sq.front = (sq.front +1 )% MAXSIZE;队空的条件队空的条件： sq.rear = =sq.front;8队满的条件队满的条件：(sq.rear + 1) % MAXSIZE = sq.front;队列中的元素个数为队列中的元素个数为：(sq.rear-sq.fro
8、nt+ MAXSIZE)% MAXSIZE91.1.循环队列的初始化循环队列的初始化（1 1）主要步骤主要步骤：将头指针和尾指针设为：将头指针和尾指针设为0 0（2 2）算法描述算法描述：void InitCyQueue(SqQueue *sq)void InitCyQueue(SqQueue *sq)sq-front=sq-rear=0;sq-front=sq-rear=0; 基本算法的实现基本算法的实现102.2.循环队列的入队循环队列的入队（1 1）主要步骤主要步骤：判断队满判断队满计算队尾指针计算队尾指针rearrear的值，并放入入队的数据元素的值，并放入入队的数据元素（2 2）算法
9、描述算法描述：int EnCyQueue(SqQueue *sq,DataType x)int EnCyQueue(SqQueue *sq,DataType x)if(sq.rear+1)%MAXSIZE=sq.front)if(sq.rear+1)%MAXSIZE=sq.front) error( error(“队满队满”););return 0;return 0; else sq.rear=(sq.rear+1)%MAXSIZE; else sq.rear=(sq.rear+1)%MAXSIZE; sq.datasq.rear=x;return 1; sq.datasq.rear=x;re
10、turn 1; 113.3.循环队列的出队循环队列的出队（1 1）主要步骤主要步骤：判断队空判断队空计算队头指针计算队头指针frontfront的值，并将队头的数据元素出队的值，并将队头的数据元素出队（2 2）算法描述算法描述：int DeCyQueue(SqQueue *sq,DataType *x)int DeCyQueue(SqQueue *sq,DataType *x)if(sq.rear=sq.front)if(sq.rear=sq.front) error( error(“队空队空”););return 0;return 0; else sq.front=(sq.front+1)%
11、MAXSIZE; else sq.front=(sq.front+1)%MAXSIZE; *x=sq.datasq.front;return 1; *x=sq.datasq.front;return 1; 124 4. .判循环队列的队空判循环队列的队空（1 1）主要步骤主要步骤： 判断队头指针与队尾指针是否相等判断队头指针与队尾指针是否相等（2 2）算法描述算法描述：int EmptyCyQueue(SqQueue sq)int EmptyCyQueue(SqQueue sq)if(sq.rear=sq.front)return 1;if(sq.rear=sq.front)return 1;
12、 else return 0; else return 0; 135.5.读循环队列的队头读循环队列的队头（1 1）主要步骤主要步骤：判断队空判断队空计算队头指针计算队头指针frontfront的值，读队头的数据元素。的值，读队头的数据元素。（2 2）算法描述算法描述：int GetCyHead(SqQueue sq,DataType *x)int GetCyHead(SqQueue sq,DataType *x)if(sq.rear=sq.front)if(sq.rear=sq.front) error( error(“队空队空”););return 0;return 0; else i=(
13、sq.front+1)%MAXSIZE; else i=(sq.front+1)%MAXSIZE; *x=sq.datai;return 1; *x=sq.datai;return 1; 14二、队列的链式存储结构：链队列二、队列的链式存储结构：链队列 在链队列中，可以附设在链队列中，可以附设头结点头结点。 头指针头指针frontfront始终指向头结点。始终指向头结点。 尾指针尾指针rearrear指向队尾元素结点。指向队尾元素结点。 链队列的类型定义链队列的类型定义 typedef struct QNode typedef struct QNode DataType data;DataTy
14、pe data; struct QNode *next;struct QNode *next; QNodeQNode, *, *QueuePtrQueuePtr; ;15 typedef struct typedef struct QueuePtr front; / QueuePtr front; / 队头指针队头指针 QueuePtr rear; / QueuePtr rear; / 队尾指针队尾指针 LinkQueueLinkQueue; ; 如：如：LinkQueue Q;QLinkQueue Q;Q是一个链队列是一个链队列16 Q为一个链队列为一个链队列Q.front /Q.rear
15、lq 队头元素队头元素 队尾元素队尾元素基本操作：基本操作：（1 1） 设置一个空的链队列。设置一个空的链队列。 void InitQueue(LinkQueue *lq)/ void InitQueue(LinkQueue *lq)/构造构造一个空队列一个空队列 lq-front=lq-rear= lq-front=lq-rear= (QueuePtr)malloc(sizeof(QNode); (QueuePtr)malloc(sizeof(QNode); lq-front-next=NULL; lq-front-next=NULL; 17 P x / Q.front / Q.rear l
16、q 队头元素队头元素 队尾元素队尾元素(2) (2) 入队列：在队列中插入一个新的队尾元素入队列：在队列中插入一个新的队尾元素x x。int EnQueue(LinkQueue *lq, DataType x)p=(QueuePtr)malloc(sizeof(QNode); /申请申请新结点新结点 if(p=NULL)return 0;else p-data=x; p-next= NULL; ( (*lq).rear)-next=p; (*lq).rear=p; return 1;18 pQ.front x /Q.rear lq 队头元素队头元素 队尾元素队尾元素(3) (3) 出队列：将队
17、头元素出队列：将队头元素x x出队。出队。int DeQueue(LinkQueue *lq, DataType *x) if(*lq).front=(*lq).rear)error(“队空队空”)；return 0; p=(*lq).front)-next; *x=p-data;/p指向队头元素指向队头元素(*lq).front)-next=p-next;/front指向新队头元素指向新队头元素if(*lq).rear=p)(*lq).rear=(*lq).front; /出队列后是空队列出队列后是空队列free(p);/释放原队头释放原队头 return 1;19Q.front x /Q.
18、rear 队头元素队头元素 队尾元素队尾元素(4) (4) 读队头：读队头元素。读队头：读队头元素。int GetHead(LinkQueue Q, DataType *x) if(Q.front=Q.rear)error(“队空队空”)；return 0; p=(Q.front)-next; *x=p-data;/p是指向队头元素是指向队头元素return 1;20Q.front x /Q.rear 队头元素队头元素 队尾元素队尾元素(5) (5) 判队空：判队空：int EmptyQueueEmptyQueue(LinkQueue Q) if(Q.front=Q.rear)return 1
19、; else return 0;213.5 队列的应用队列的应用例：假设在周末舞会上，男士们和女士们例：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一对。跳舞开始进入舞厅时，各自排成一对。跳舞开始时，依次从男队和女队的队头各出一人时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞较长的那一队中未配对者等待下一轮舞曲。写一算法模拟上述舞伴配对问题。曲。写一算法模拟上述舞伴配对问题。22该问题具有典型的先进先出特性，可用队列完成该问题具有典型的先进先出特性，可用队列完成本题采用循环队列本题采用循环队列ty
20、pedef structtypedef structchar name20;char name20;char sex;Person;char sex;Person;void DancePartners(Person dancer,int num)void DancePartners(Person dancer,int num)/结构体数组结构体数组dancerdancer中存放跳舞的男女，中存放跳舞的男女，numnum是是 / /跳舞的人数。跳舞的人数。23int i; Person p;int i; Person p;SqQueue Mdancers,Fdancers;SqQueue Mda
21、ncers,Fdancers;InitCyQueue(&Mdancers);/InitCyQueue(&Mdancers);/男士队列初始化男士队列初始化InitCyQueue(&Fdancers);/InitCyQueue(&Fdancers);/女士队列初始化女士队列初始化for(i=0;inum;i+)for(i=0;inum;i+) p=danceri;p=danceri; if(p.sex= if(p.sex=F F) ) EnCyQueue(&Fdancers,p.name);/ EnCyQueue(&Fdancers,p.name);/进女队进女队 else else EnCyQ
22、ueue(&Mdancers,p.name);/ EnCyQueue(&Mdancers,p.name);/进男队进男队 printf(printf(“参加跳舞的人是：参加跳舞的人是： n n”););24while(! EmptyCyQueue(Fdancers)& while(! EmptyCyQueue(Fdancers)& ! EmptyCyQueue(Mdancers) ! EmptyCyQueue(Mdancers) /依次输出男女舞伴名依次输出男女舞伴名 char c20; char c20; DeCyQueue(&Fdancers,c);/ DeCyQueue(&Fdancer
23、s,c);/女士出队女士出队 printf( printf(“%sn%sn”,c);/,c);/输出出队女士名输出出队女士名 DeCyQueue(&Mdancers,c); / DeCyQueue(&Mdancers,c); /男士出队男士出队 printf( printf(“%sn%sn”,c);/,c);/输出出队男士名输出出队男士名 25if(! Emptyif(! EmptyCyCyQueue (Fdancers)Queue (Fdancers)/输出剩余女队人数及队头女士的名字输出剩余女队人数及队头女士的名字 printf(printf(“有有% %d d个女士等待下一轮个女士等待下
24、一轮 n n”, , CyQueuelength(Fdancers);CyQueuelength(Fdancers); GetCyHead(Fdancers,c); GetCyHead(Fdancers,c); printf( printf(“%s%s是首次配对是首次配对 n n”,c);,c); else else if(! Emptyif(! EmptyCyCyQueue (Mdancers)Queue (Mdancers)/输出剩余男队人数及队头男士的名字输出剩余男队人数及队头男士的名字printf(printf(“有有% %d d个男士等待下一轮个男士等待下一轮 n n”, , CyQueuelength(Mdancers);CyQueuelength(Mdancers); GetCyHead(Mdancers,c); GetCyHead(Mdancers,c);printf(printf(“%s%s是首次配对是首次配对 n n”,c);,c); /DancerPartres/DancerPartres26
