3.3　队　列

视频二维码（扫码观看）

一、抽象数据类型队列的定义

1队列的基本概念

队列（Queue）：也是运算受限的线性表。是一种先进先出（First In First Out，简称FIFO）的线性表。只允许在表的一端进行插入，而在另一端进行删除。

队首（front）：允许进行删除的一端称为队首。

队尾（rear）：允许进行插入的一端称为队尾。

队列中没有元素时称为空队列。在空队列中依次加入元素a₁，a₂，…，a_n之后，a₁是队首元素，a_n是队尾元素。显然退出队列的次序也只能是a₁，a₂，…，a_n，即队列的修改是依先进先出的原则进行的，如图3-5所示。

图3-5　队列示意图

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

二、链队列——队列的链式表示和实现

1队列的链式存储表示

队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。

需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点，如图3-6所示。

图3-6　链队列结点示意图

数据元素结点类型定义：

指针结点类型定义：

2链队运算及指针变化

链队的操作实际上是单链表的操作，只不过是删除在表头进行，插入在表尾进行。插入、删除时分别修改不同的指针。链队运算及指针变化如图3-7所示。

图3-7（a）　空队列指针

图3-7（b）　x入队后指针变化

图3-7（c）　y再入队后指针变化

图3-7（d）　x出队后指针变化

3链队列的基本操作

（1）基本操作的函数原型说明

Status Initqueue(LinkQueue &Q);//构造一个空队列Q。

Status DestroyQueue(LinkQueue &Q);//销毁队列Q，Q不再存在。

Status ClearQueue(LinkQueue &Q);//将Q清为空队列。

Status Queue Empty(LinkQueue Q);//若队列Q为空队列，则返回TRUE，否则返回FALSE。

int queueLength(LinkQueue Q);//返回Q的元素个数，即为队列的长度。

Status GetHead(LinkQueue Q,QElemlype &e);//若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR。

Status EnQueue(LinkQueue &0,QElem Type e);//插入元素e为Q的新的队尾元素。

Status DeQueue(LinkQueue &Q,QElem Type &e);//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR。

Status QueueTraverse(LinkQueue Q,visit());//从队头到队尾依次对队列Q中每个元素调用函数visit（），一且visit失败，则操作失败。

（2）部分基本操作的算法描述

①链队列的初始化

②链队列的入队操作

③链队列的出队操作

④链队列的撤消

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

1队列的顺序存储表示

设立一个队首指针front，指向队首元素；一个队尾指针rear，指向队尾元素的下一位置。

初始化：front＝rear＝0。

入队：将新元素插入rear所指的位置，然后rear加1。

出队：删去front所指的元素，然后front加1并返回被删元素。

队列为空：front＝rear。

队满：rear＝MAX_QUEUE_SIZE－1或front＝rear。

在非空队列里，队首指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。

顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针已超出向量空间的上界而不能做入队操作。该现象称为假溢出。如图3-8所示是数组大小为5的顺序队列中队首、队尾指针和队列中元素的变化情况。

图3-8　顺序队列中队首、队尾指针和队列中元素的变化情况

2循环队列

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列（Circular Queue）。

在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当队首、队尾指针指向向量上界（MAX_QUEUE_SIZE－1）时，其加1操作的结果是指向向量的下界0。

这种循环意义下的加1操作可以描述为：

if(i+1==MAX_QUEUE_SIZE)
    i=0;
else
    i++;

其中，i代表队首指针（front）或队尾指针（rear）

用模运算可简化为：i＝（i＋1）%MAX_QUEUE_SIZE；

显然，为循环队列所分配的空间可以被充分利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，真正实用的顺序队列是循环队列。

【例】有循环队列QU[0，5]，其初始状态是front＝rear＝0，各种操作后队列的头、尾指针的状态变化情况如下图3-9所示。

图3-9（a）　空队列指针

图3-9（b）　d，e，b，g入队后指针变化情况

图3-9（c）　d，e出队后指针变化情况

图3-9（d）　i，j，k入队后指针变化情况

图3-9（e）　b，g出队后指针变化情况

图3-9（f）　r，p入队后指针变化情况

入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过front＝rear来判断队列“空”还是“满”。解决此问题的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即：

rear所指的单元始终为空。

循环队列为空：front＝rear。

循环队列满：（rear＋1）%MAX_QUEUE_SIZE＝front。

3部分循环队列的基本操作：

①循环队列的初始化

Status InitQueue(SqQueue &Q)
{//构造一个空队列Q
    Q.base=(QElemType*)malloc(MAXQSIZE *sizeof(QElemType));
    i(!Q.base)
        exit(OVERFLOW);
    Q.front=Q.rear=0
    return OK;
}

②入队操作

Status EnQueue(SqQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
    if((Q.rear+1)% MAXQSIZE)==Q.front)
        return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear +1)%MAXOSIZE;
    return OK
}

③出队操作

Status DeQueue(SqQueue &Q,QelemType &e)
{//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR。
    if(Q.front==Q.rear)
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}