日常生活中随处可见队列的例子。任何一次排队的过程都形成一个队列,排队的规则是不允许“插队”,新加入的成员只能排在队尾,而且队中全体成员只能按顺序向前移动,当到达队头(并得到服务)后离队。它反映了“先来先服务”的处理原则。例如,排队购物或排队等车,新来的成员总是排在队尾(进队),每次出队得到服务的人总是站在队头的成员。当最后一个人离队后,队列为空。
队列(Queue)简称队,是限制在表的一端进行插入操作,而在表的另一端进行删除操作的线性表,也是一种操作受限的线性表。我们把允许插入数据的一端称之为队尾(rear),而把允许删除数据的一端称之为队头或队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队,元素离队后,其后继元素成为新的队首元素。由于队列的插入、删除操作各在一端进行,所以每个元素出队的次序必然就是进队的次序。队列又称之为FIFO(First In,First Out)或先进先出表。
如图3-10是一个队列的示意图。
图3-10 队列的示意图
队列(简称队)以线性表为逻辑结构,其基本运算如下:
(1)初始化队列InitQueue(qu)。其作用是设置一个空队列qu。
(2)进队列EnQueue(qu,x)。其作用是将x插入到队列qu的队尾。若原队列非空,则插入后x为原队尾节点的后继,同时是新队列的队尾节点。
(3)出队列DeQueue(qu,x)。若队列qu非空,则将队头元素赋给x,并删除队头节点。而该节点的后继成为新的队头节点。
(4)取队头元素GetHead(qu,x)。若队列qu非空,则由x返回队头节点的值;否则返回NULL。
(5)判断队列空QueueEmpty(qu)。若队列qu为空,则返回1;否则返回0。
【例3-5】跟踪以下代码,显示每次调用后队列中的内容。
InitQueue(qu); /*设置一个空队列qu*/
EnQueue(qu,'A'); /*将A插入到队列qu的队尾*/
EnQueue(qu,'B'); /*将B插入到队列qu的队尾*/
EnQueue(qu,'C'); /*将C插入到队列qu的队尾*/
DeQueue(qu,x); /*将队头元素赋给x,并删除队头节点*/
DeQueue(qu,x); /*将队头元素赋给x*/
EnQueue(qu,'D'); /*将D插入到队列qu的队尾*/
EnQueue(qu,'E'); /*将E插入到队列qu的队尾*/
EnQueue(qu,'F'); /*将F插入到队列qu的队尾*/
DeQueue(qu,x); /*将队头元素赋给x,并删除队头节点*/
EnQueue(qu,'G'); /*将G插入到队列qu的队尾*/
DeQueue(qu,x); /*将队头元素赋给x,并删除队头节点*/
DeQueue(qu,x); /*将队头元素赋给x,并删除队头节点*/
DeQueue(qu,x); /*将队头元素赋给x,并删除队头节点*/
解:显示队列中的内容如下。
InitQueue(qu); /*空队列*/
EnQueue(qu,'A'); /*队中内容:A*/
EnQueue(qu,'B'); /*队中内容:A,B*/
EnQueue(qu,'C'); /*队中内容:A,B,C*/
DeQueue(qu,x); /*队中内容:B,C*/
DeQueue(qu,x); /*队中内容:C*/
EnQueue(qu,'D'); /*队中内容:C,D*/
EnQueue(qu,'E'); /*队中内容:C,D,E*/
EnQueue(qu,'F'); /*队中内容:C,D,E,F*/
DeQueue(qu,x); /*队中内容:D,E,F*/
EnQueue(qu,'G'); /*队中内容:D,E,F,G*/
DeQueue(qu,x); /*队中内容:E,F,G*/
DeQueue(qu,x); /*队中内容:F,G*/
DeQueue(qu,x); /*队中内容:G*/
队列的链式存储结构简称为链队,它实际上是一个同时带有首指针和尾指针的单链表。首指针指向队头节点,尾指针指向队尾节点,即单链表的最后一个节点,如图3-11所示。
图3-11 链队示意图
链队的类型定义如下:
typedef struct QNode
{
ElemType data;
struct QNode *next;
} QType; /*链队中节点的类型*/
typedef struct qptr
{
QType *front,*rear;
} LinkQueue; /*链队类型*/
链队lq的四要素如下:
· 队空 lq->front==lq->next==NULL
· 队满 不存在
· 进队操作 lq->rear->next=s; lq->rear=s
· 出队操作 lq->front=lq->front->next
在链队上实现队列基本运算算法如下。
其主要操作是:置节点*lq的rear和front均为NULL。
void InitQueue(LinkQueue *&lq) /*lq为引用型参数*/
{
lq=(LinkQueue *)malloc(sizeof(LinkQueue));
lq->rear=lq->front=NULL; /*初始情况*/
}
其主要操作是:创建一个新节点,将其链接到链队的末尾,并由rear指向它。
void EnQueue(LinkQueue *&lq,ElemType x) /*进队运算,lq为引用型参数*/
{
QType *s;
s=(QType *)malloc(sizeof(QType)); /*创建新节点,插入到链队的末尾*/
s->data=x;s->next=NULL;
if(lq->front==NULL && lq->rear==NULL) /*空队*/
lq->rear=lq->front=s;
else
{
lq->rear->next=s;
lq->rear=s;
}
}
其主要操作是:将*front节点的data域值赋给x,并删除该节点。
int DeQueue(LinkQueue *&lq,ElemType &x) /*出队运算,lq和x均为引用型参数*/
{
QType *p;
if(lq->front==NULL && lq->rear==NULL) /*空队*/
return 0;
p=lq->front;
x=p->data;
if(lq->rear==lq->front) /*若原队列中只有一个节点,删除后队列变空*/
lq->rear=lq->front=NULL;
else
lq->front=lq->front->next;
free(p);
return 1;
}
其主要操作是:将*front节点的data域值赋给x。
int GetHead(LinkQueue *lq,ElemType &x) /*取队头元素运算,x为引用型参数*/
{
if (lq->front==NULL && lq->rear==NULL) /*队空*/
return 0;
x=lq->front->data;
return 1;
}
其主要操作是:若链队为空,则返回1;否则返回0。
int QueueEmpty(LinkQueue *lq) /*判断队空运算*/
{
if(lq->front==NULL && lq->rear==NULL)
return 1;
else
return 0;
}
当链队的基本运算函数设计好后,给出以下程序调用这些基本操作函数,读者可以对照程序执行结果进行分析,进一步体会链队各种操作的实现过程。
void main()
{
LinkQueue *lq; /*定义链队lq*/
ElemType e;
InitQueue(lq); /*创建链队lq*/
printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空")); /*判断链队是否为空*/
printf("a进队\n");EnQueue(lq,'a'); /*将a插入到队列lq的队尾*/
printf("b进队\n");EnQueue(lq,'b'); /*将b插入到队列lq的队尾*/
printf("c进队\n");EnQueue(lq,'c'); /*将c插入到队列lq的队尾*/
printf("d进队\n");EnQueue(lq,'d'); /*将d插入到队列lq的队尾*/
printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空")); /*判断链队是否为空*/
GetHead(lq,e); /*取队头元素,赋值给e*/
printf("队头元素:%c\n",e);
printf("出队次序:");
while (!QueueEmpty(lq)) /*队不为空时循环*/
{
DeQueue(lq,e); /*将队头元素赋给e,并删除队头节点*/
printf("%c",e);
}
printf("\n");
}
【例3-6】若使用循环链表来表示队列,p指向链表的尾节点。试基于此结构给出队列的进队(EnQueue)和出队(DeQueue)算法,并给出p为何值时队列空。
解:这里使用的循环链表不带头节点,规定p始终指向队尾节点,p->next即为队头节点。当p==NULL时队列为空。队列的进队和出队算法如下。
typedef struct node
{
ElemType data;
struct QNode *next;
} QNode;
void EnQueue(QNode *&p,ElemType x) /*p为引用型参数*/
{
QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=x;
if(p==NULL)
{
p=s;p->next=p;
}
else
{
s->next=p->next; /*将s作为*p之后的节点*/
p->next=s;
p=s; /*p指向*s*/
}
}
int DeQueue(QNode *&p,ElemType &x) /*p,x均为引用型参数*/
{
QNode *s;
if(p==NULL) return 0;
if(p->next==NULL) /*只有一个节点*/
{
free(p);
p=NULL;
}
else /*有一个以上的节点*/
{
s=p->next;x=s->data; /*将*p之后节点的data域值赋给x,然后删除之*/
p->next=s->next;
free(s);
}
return 1;
}
与栈类似,队列通常有两种存储结构,即顺序存储结构和链式存储结构。队列的顺序存储结构简称为顺序队,它由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成,这两个变量分别称为“队头指针”和“队尾指针”(它们并非指针变量,而是数组的下标)。通常约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置。
顺序队列的类型定义如下:
#define QueueSize /*队列的容量*/
typedef struct sqqueue
{
ElemType data[QueueSize]; /*保存队中元素*/
int front,rear; /*队头和队尾指针*/
} SqQueue;
顺序队列定义为一个结构类型,该类型变量有3个域:data、front、rear。其中data为存储队列中元素的一维数组。队头指针front和队尾指针rear定义为整型变量,实际取值范围是0~QueueSize-1。图3-12所示为顺序队列的几种状态。
图3-12 顺序队列的几种状态
(a)表示空队列,sq.rear=sq.front=0。
(b)元素A进队后,sq.rear=1,sq.front=0。
(c)B、C、D依次进队后,sq.rear=4,sq.front=0。
(d)A出队后,sq.rear=4,sq.front=1。
(e)B、C、D出队后,sq.rear=sq.front=4。
从图3-12中还可以看到,在队列刚建立时,先对它进行初始化,令front=rear=0(有的书中令front=rear= -1)。每当加入一个新元素时,令队尾指针rear增1,再将新元素添加到rear所指位置,因而指针rear指示了实际的队尾位置。而队头指针front则不然,它实际指示的是真正的队头元素所在位置的前一位置。所以,如果要出队时,应当首先让队头指针front加1,再把front所指位置上的元素值返回。
从图3-12中还可以看到,如果队头指针front==rear,则队列为空,如图3-12(a)所示;而当rear==QueueSize-1时,队列为满,如图3-12(e)所示;如果再加入新元素,就会产生“溢出”。
但是,这种“溢出”并不是真正的溢出,在data数组的前端可能还有空位置,所以这是一种假溢出。为了能够充分地使用数组中的存储空间,我们把数组的前端和后端连接起来,形成一个环形的表,即把存储队列元素的表从逻辑上看成一个环,成为环形队列。如图3-13为环形队列的几种状态。
图3-13 环形队列的几种状态
(a)表示空队列,sq.rear=sq.front=0。
(b)元素A进队后,sq.rear=1,sq.front=0。
(c)B、C、D依次进队后,sq.rear=4,sq.front=0。
(d)A出队后,sq.rear=4,sq.front=1。
(e)B、C、D出队后,sq.rear=sq.front=4。
环形队列首尾相连,当队头指针front=QueueSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算(%)来实现。
队头指针进1:front=(front+1)% QueueSize
队尾指针进1:rear=(rear+1)% QueueSize
环形队列的队头指针和队尾指针初始化时都置0:front=rear=0。在队尾插入新元素和删除队头元素时,指针都按逆时针方向进1。当它们进到QueueSize-1时,并不表示表的终结,如图3-13(e)所示,只要有需要,利用“%”运算可以前进到数组的0号位置。
如果环形队列读取元素的速度快于存入元素的速度,即队头指针很快追上了队尾指针,则一旦达到了front==rear时,队列就变成了空队列;反之,如果队列存入元素的速度快于读取元素的速度,即队尾指针很快就赶上了队头指针,则一旦队列满就不能再加入新元素了。为了区别于队列空条件,用(rear+1)%QueueSize==front来判断是否队已满;也就是说,让rear指到front的前一位置就认为队列已满。此时,因队头指针指示实际队头的前一个位置,所以在队列满时实际空了一个元素位置。如果不留这个空位置,让队尾指针rear一直存到这个位置,必然有rear==front,则队列空条件和队列满条件就混淆了。除非另加队空或队满标志,否则无从分辨到底是队列空,还是队列满。
环形队列的四要素:
· 队空 qu.front==qu.rear
· 队满 (qu.rear+1)%QueueSize==qu.front
· 进队操作 qu.rear=(qu.rear+1)%QueueSize;qu.data[qu.rear]=x
· 出队操作 qu.front=(qu.front+1)%QueueSize;x=qu.data[qu.front]
环形队列的基本运算算法如下。
创建一个队列节点,用qu指向该队列节点,并指定qu.front=qu.rear=0。
void InitQueue(SqQueue &qu) /*qu为引用型参数*/
{
qu.rear=qu.front=0; /*指针初始化*/
}
其主要操作是:先判断队列是否已满,若不满,则令队尾指针增1,在该位置存放x。
int EnQueue(SqQueue &qu,ElemType x) /*进队运算,qu为引用型参数*/
{
if((qu.rear+1)%QueueSize==qu.front) /*队满*/
return 0;
qu.rear=(qu.rear+1)%QueueSize; /*队尾指针进1*/
qu.data[qu.rear]=x;
return 1;
}
其主要操作是:先判断队列是否已空,若不空,则令队头指针增1,将该位置处的元素值赋给x。
int DeQueue(SqQueue &qu,ElemType &x) /*出队运算,qu和x为引用型参数*/
{
if(qu.rear==qu.front)
return 0;
qu.front=(qu.front+1)%QueueSize; /*队头指针进1*/
x=qu.data[qu.front];
return 1;
}
其主要操作是:先判断队列是否已空,若不空,则将队头指针上一个位置处的元素值赋给x。
int GetHead(SqQueue qu,ElemType &x) /*取队头元素运算,x为引用型参数*/
{
if(qu.rear==qu.front) /*队空*/
return 0;
x=qu.data[(qu.front+1)%QueueSize];
return 1;
}
其主要操作是:若队列为空,则返回1;否则返回0。
int QueueEmpty(SqQueue qu) /*判断队空运算*/
{
if(qu.rear==qu.front) /*队空*/
return 1;
else
return 0;
}
当顺序队列的基本运算函数设计好后,给出以下程序调用这些基本操作函数,读者可以对照程序执行结果进行分析,进一步体会顺序队列各种操作的实现过程。
void main()
{
SqQueue qu;
ElemType e;
InitQueue(qu);
printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));
printf("a进队\n");EnQueue(qu,'a');
printf("b进队\n");EnQueue(qu,'b');
printf("c进队\n");EnQueue(qu,'c');
printf("d进队\n");EnQueue(qu,'d');
printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));
GetHead(qu,e);
printf("队头元素:%c\n",e);
printf("出队次序:");
while (!QueueEmpty(qu))
{
DeQueue(qu,e);
printf("%c ",e);
}
printf("\n");
}
上述程序的执行结果如下:
队空
a进队
b进队
c进队
d进队
队不空
队头元素:a
出队次序:a b c d
【例3-7】对于环形队列,写出求队列中元素个数的公式。
解:根据环形队列的特点,有以下情况。
0 队空,即front=rear
元素个数=
rear-front 若rear>front
rear+QueueSize-front 若rear<front
QueueSize-1 若队满即(rear+1)%QueueSize==front
归纳起来,环形队列元素个数的计算公式如下:
(rear+QueueSize-front)%QueueSize
【例3-8】如果用一个循环数组qu[QueueSize]表示队列时,该队列只有一个头指针front,不设队尾指针rear,而设置计数器count,用以记录队列中的元素个数。
(1)试分析队列中最多能容纳多少个元素。
(2)设计实现队列基本运算的算法。
解:
(1)队列中最多可容纳QueueSize个元素,因为这里不需要空出一个位置以区分队列空和队列满的情况。
(2)队列为空的条件是count==0;队列满的条件是count==QueueSize;队尾元素的位置是(front+count)%QueueSize;队头元素的位置是(front+1)%QueueSize。在这种队列上实现队列的基本运算算法如下。
void InitQueue(SqQueue *&qu) /*qu为引用型参数*/
{
qu=(SqQueue *)malloc(sizeof(SqQueue));
qu->front=qu->count=0;
}
int EnQueue(SqQueue *sq,ElemType x)
{
if(sq->count==QueueSize) /*队满*/
return 0;
sq->count++; /*队中元素个数增1*/
sq->data[(sq->front+sq->count)%QueueSize]=x;
return 1;
}
int DeQueue(SqQueue *sq,ElemType &x) /*x为引用型参数*/
{
if(sq->count==0) /*队空*/
return 0;
sq->count--; /*队中元素个数减1*/
sq->front=(sq->front+1)%QueueSize;
x=sq->data[sq->front];
return 1;
}
int GetHead(SqQueue *sq,ElemType &x) /*x为引用型参数*/
{
if(sq->count==0) /*队空*/
return 0;
x=sq->data[(sq->front+1)%QueueSize];
return 1;
}
int QueueEmpty(SqQueue *sq)
{
if(sq->count==0) /*队空返回1*/
return 1;
else /*队不空返回0*/
return 0;
}