数据结构——队列

1.队列的定义

和栈相反，队列(queue)是一种先进先出（FIFO）的线性表。

它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端叫做队尾，允许删除的一端叫做队头。

队列的抽象数据类型定义如下：

ADT Queue{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={|ai-1,ai∈D, i=1,2, …,n }
//约定a1为队列头，an为队列尾。
//基本操作：
   InitQueue( &Q )
     操作结果：构造一个空队列Q。
   DestroyQueue ( &Q )
     初始条件：队列Q已存在。
     操作结果：销毁队列Q。
   ClearQueue ( &Q )
     初始条件：队列Q已存在。
     操作结果：将Q清为空队列。
   QueueEmpty( Q )
     初始条件：队列Q已存在。
     操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
   QueueLength( Q )
     初始条件：队列Q已存在。
     操作结果：返回Q的数据元素个数，即队列的长度。
   GetHead( Q, &e )
     初始条件：队列Q已存在且非空。
     操作结果：用e返回Q的队头元素。
   EnQueue( &Q, e )
     初始条件：队列Q已存在。
     操作结果：插入元素e为Q的新的队尾元素。
   DeQueue( &Q, &e )
     初始条件：队列Q已存在且非空。
     操作结果：删除Q的队头元素，并用e返回其值。
QueueTraverse( Q, visit() )
     初始条件：队列Q已存在且非空。
     操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT Queue

双端队列：

2.链队列

用链表表示的队列简称链队列。一个链队列显然需要两个分别指示队头和队尾的指针才能唯一确定。

存储结构不再列举

下面列举部分基本操作的描述

typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;


Status InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
    return ok;
}
Status DestroyQueue(LinkQueue &Q){
    while(Q.front)
    {
        Q.rear=Q.front->next;
        free(Q.front);
        Q.front=Q.rear;
    }
}
Status EnQueue(LinkQueue &Q,QElemType e){
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e; p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return ok;
}

3.循环队列

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别之时队列头元素和队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

假设当前为队列分配的最大空间为6，则当队列处于图4(d)的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间，如图5所示，称之为循环队列。指针和队列元素之间关系不变，如图6所示循环队列中，队列头元素时J3，队列尾元素是J5，之后J6、J7和J8相继插入，则队列空间均被占满，如图6(b)所示，此时 $Q.front=Q.rear$ ​；反之，若J3、J4和J5相继从图6(a)的队列中删除，使队列呈“空”的状态，如图所示。此时亦存在关系式$Q.front=Q.rear$，由此可见，只凭等式$Q.front=Q.rear$无法判别队列空间是“空”还是“满”。可由两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。

从上述分析可见，在C语言中不能用动态分配的一组一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若无法预估，则宜使用链队列。

循环队列类型模块说明：

#define MAXQSIZE 100
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

Status InitQueue(SqQueue &Q)
{
    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}
int QueueLength(SqQueue Q)
{
    return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e){
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}