您的位置: 网站首页 > 程序开发 > 数据结构 > 第3章 栈和队列 > 【3.4 队 列】

3.4 队 列

 

3.4     

日常生活中随处可见队列的例子。任何一次排队的过程都形成一个队列,排队的规则是不允许“插队”,新加入的成员只能排在队尾,而且队中全体成员只能按顺序向前移动,当到达队头(并得到服务)后离队。它反映了“先来先服务”的处理原则。例如,排队购物或排队等车,新来的成员总是排在队尾(进队),每次出队得到服务的人总是站在队头的成员。当最后一个人离队后,队列为空。

3.4.1  抽象数据类型队列的定义

队列(Queue)简称队,是限制在表的一端进行插入操作,而在表的另一端进行删除操作的线性表,也是一种操作受限的线性表。我们把允许插入数据的一端称之为队尾(rear),而把允许删除数据的一端称之为队头或队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队,元素离队后,其后继元素成为新的队首元素。由于队列的插入、删除操作各在一端进行,所以每个元素出队的次序必然就是进队的次序。队列又称之为FIFOFirst InFirst 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.4.2  链队列—队列的链式表示和实现

队列的链式存储结构简称为链队,它实际上是一个同时带有首指针和尾指针的单链表。首指针指向队头节点,尾指针指向队尾节点,即单链表的最后一个节点,如图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

在链队上实现队列基本运算算法如下。

1.初始化队列运算算法

其主要操作是:置节点*lqrearfront均为NULL

void InitQueue(LinkQueue *&lq)          /*lq为引用型参数*/

{   

   lq=(LinkQueue *)malloc(sizeof(LinkQueue));

   lq->rear=lq->front=NULL;                  /*初始情况*/

}

2.进队运算算法

其主要操作是:创建一个新节点,将其链接到链队的末尾,并由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;

  }

}

3.出队运算算法

其主要操作是:将*front节点的data域值赋给x,并删除该节点。

int DeQueue(LinkQueue *&lq,ElemType &x)     /*出队运算,lqx均为引用型参数*/

{

    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;

}

4.取队头元素运算算法

其主要操作是:将*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;

}

5.判断队空运算算法

其主要操作是:若链队为空,则返回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)          /*px均为引用型参数*/

{

    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;

}

3.4.3  循环队列——队列的顺序表示和实现

与栈类似,队列通常有两种存储结构,即顺序存储结构和链式存储结构。队列的顺序存储结构简称为顺序队,它由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成,这两个变量分别称为“队头指针”和“队尾指针”(它们并非指针变量,而是数组的下标)。通常约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置。

顺序队列的类型定义如下:

#define QueueSize                       /*队列的容量*/

typedef struct sqqueue

{  

    ElemType data[QueueSize];           /*保存队中元素*/

    int front,rear;                     /*队头和队尾指针*/

} SqQueue;

顺序队列定义为一个结构类型,该类型变量有3个域:datafrontrear。其中data为存储队列中元素的一维数组。队头指针front和队尾指针rear定义为整型变量,实际取值范围是0QueueSize-1。图3-12所示为顺序队列的几种状态。

3-12  顺序队列的几种状态

a)表示空队列,sq.rear=sq.front=0

b)元素A进队后,sq.rear=1sq.front=0

cBCD依次进队后,sq.rear=4sq.front=0

dA出队后,sq.rear=4sq.front=1

eBCD出队后,sq.rear=sq.front=4

从图3-12中还可以看到,在队列刚建立时,先对它进行初始化,令front=rear=0(有的书中令front=rear= -1)。每当加入一个新元素时,令队尾指针rear1,再将新元素添加到rear所指位置,因而指针rear指示了实际的队尾位置。而队头指针front则不然,它实际指示的是真正的队头元素所在位置的前一位置。所以,如果要出队时,应当首先让队头指针front1,再把front所指位置上的元素值返回。

从图3-12中还可以看到,如果队头指针front==rear,则队列为空,如图3-12a)所示;而当rear==QueueSize-1时,队列为满,如图3-12e)所示;如果再加入新元素,就会产生“溢出”。

但是,这种“溢出”并不是真正的溢出,在data数组的前端可能还有空位置,所以这是一种假溢出。为了能够充分地使用数组中的存储空间,我们把数组的前端和后端连接起来,形成一个环形的表,即把存储队列元素的表从逻辑上看成一个环,成为环形队列。如图3-13为环形队列的几种状态。

3-13  环形队列的几种状态

a)表示空队列,sq.rear=sq.front=0

b)元素A进队后,sq.rear=1sq.front=0

cBCD依次进队后,sq.rear=4sq.front=0

dA出队后,sq.rear=4sq.front=1

eBCD出队后,sq.rear=sq.front=4

环形队列首尾相连,当队头指针front=QueueSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算(%)来实现。

队头指针进1front=(front+1)% QueueSize

队尾指针进1rear=(rear+1)% QueueSize

环形队列的队头指针和队尾指针初始化时都置0front=rear=0。在队尾插入新元素和删除队头元素时,指针都按逆时针方向进1。当它们进到QueueSize-1时,并不表示表的终结,如图3-13e)所示,只要有需要,利用“%”运算可以前进到数组的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]

环形队列的基本运算算法如下。

1.初始化队列运算算法

创建一个队列节点,用qu指向该队列节点,并指定qu.front=qu.rear=0

void InitQueue(SqQueue &qu)             /*qu为引用型参数*/

{

   qu.rear=qu.front=0;                   /*指针初始化*/

}

2.进队运算算法

其主要操作是:先判断队列是否已满,若不满,则令队尾指针增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;

}

3.出队运算算法

其主要操作是:先判断队列是否已空,若不空,则令队头指针增1,将该位置处的元素值赋给x

int DeQueue(SqQueue &qu,ElemType &x)        /*出队运算,qux为引用型参数*/

{

    if(qu.rear==qu.front)

        return 0;

    qu.front=(qu.front+1)%QueueSize;         /*队头指针进1*/

    x=qu.data[qu.front];

    return 1;

}

4.取队头元素运算算法

其主要操作是:先判断队列是否已空,若不空,则将队头指针上一个位置处的元素值赋给x

int GetHead(SqQueue qu,ElemType &x)         /*取队头元素运算,x为引用型参数*/

{

    if(qu.rear==qu.front)                   /*队空*/

        return 0;

    x=qu.data[(qu.front+1)%QueueSize];

    return 1;

}

5.判断队空运算算法

其主要操作是:若队列为空,则返回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                rearfront

                      rear+QueueSize-front      rearfront

              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;

}