同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

ADT 队列(Queue)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitQueue(*Q):    初始化操作，建立一个空队列Q。
    DestroyQueue(*Q): 若队列Q存在，则销毁它。
    ClearQueue(*Q):   将队列Q清空。
    QueueEmpty(Q):    若队列Q为空，返回true，否则返回false。
    GetHead(Q, *e):   若队列Q存在且非空，用e返回队列Q的队头元素。
    EnQueue(*Q, e):   若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
    DeQueue(*Q, *e):  删除队列Q中队头元素，并用e返回其值。
    QueueLength(Q):   返回队列Q的元素个数
endADT

循环队列

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

队列顺序存储的不足

入队

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为。

image-20200419152755353

出队

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为。

image-20200419152844578

可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，

image-20200419153129368

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列列如图所示，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

image-20200419153516257

假溢出

出队a1、a2，则front指针指向下标为2的位置，rear不变，如图4-12-5的左图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？如下图的右图所示。

image-20200419153806567

假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

循环队列的定义

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

如果将rear的指针指向下标为0的位置，那么就不会出现指针指向不明的问题了，如下图所示。

image-20200419154148062

接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如下图的左图所示。若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下图的右图所示。

image-20200419154312681

问题

• 此时问题又出来了，我们刚才说，空队列时，front等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？
• 办法一是设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。

• 办法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如图4-12-8所示，我们就认为此队列已经满了，也就是说，我们不允许上图的右图情况出现。

  
  image-20200419154505860

由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。

所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize==front（取模“%”的目的就是为了整合rear与front大小为一圈问题）。比如上面这个例子，QueueSize=5，上图的左图中front=0，而rear=4，(4+1)%5=0，所以此时队列满。

再比如图下图中的，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。

image-20200419160342448

而对于下图，front=2而rear=0，(0+1)%5=1，1≠2，所以此时队列并没有满。

image-20200419154148062

另外，当rear>front时，此时队列的长度为rear-front。

但当rear<front时，，队列长度分为两段，一段是QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列满队公式为：

(rear-front+QueueSize)%QueueSize = front;

顺序队列的结构

// QElemType类型根据实际情况而定，这里假设为int
typedef int QElemType;

typedef struct {
    QElemType data[MAXSIZE];
    // 头指针
    int front;
    // 尾指针，若队列不空，指向队列尾元素的下一个位置
    int rear;
    
} SqQueue;

初始化

// 初始化一个空队列Q
Status InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

求队列的长度

// 返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

入队

// 若队列未满，则插入元素e为Q新的队尾元素
Status EnQueue(SqQueue *Q, QElemType e) {
    // 满队
    if ((Q->rear - Q->front + MAXSIZE) % MAXSIZE == Q->front) {
        return ERROR;
    }
    // 将元素插入队尾，指针后移一位
    Q->data[Q->rear] = e;
    // 如果到最后，就将rear指向数组的头部
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return OK;
}

出队

// 若队列不空，则删除Q中队头元素，用e返回其值
Status DeQueue(SqQueue *Q, QElemType *e) {
    // 判断队列是否为空队
    if (Q->front == Q->rear) {
        return ERROR;
    }
    *e = Q->data[Q->front];
    // 将front指针后移
    Q->front = (Q->front + 1) % MAXSIZE;
    return OK;
}

总结

单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

链式队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

image-20200419163616107

空队列时，front和rear都指向头结点。

image-20200419163709359

链队列的结构为：

// QElemType类型根据实际情况而定，这里假设为int
typedef int QElemType;       
// 结点结构
typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

// 队列的结构
typedef struct {
    // 对头，对尾
    QueuePtr front, rear;
}LinkQueue;

初始化

初始化一个空队列

// 初始化一个空队列Q
Status InitQueue(LinkQueue *Q) {
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    if (!head) {
        // 分配内存失败
        return ERROR;
    }
    // 头结点可以用来存储队列的长度
    head->data = 0;
    head->next = NULL;
    Q->front = head;
    Q->rear = head;
    return OK;
}

入队

入队操作时，其实就是在链表尾部插入结点，如图所示。

image-20200419164242591

// 插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e) {
    if (!Q) {
        return ERROR;
    }
    QNode *node = (QNode *)malloc(sizeof(QNode));
    if (!node) {
        // 分配内存失败
        return ERROR;
    }
    node->data = e;
    node->next = NULL;
    // 将新结点插入在队尾
    Q->rear->next = node;
    // 更新尾指针
    Q->rear = node;
    // 更新队列的长度
    Q->front->data++;
    return OK;
}

出队

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图所示。

image-20200419165543930

// 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
Status DeQueue(LinkQueue *Q, QElemType *e) {
    if (!Q) {
        return ERROR;
    }
    QueuePtr p = Q->front->next;
    *e = p->data;
    
    Q->front->next = p->next;
    
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    // 释放要删除的结点
    free(p);
    // 更新队列的长度
    Q->front->data--;
    return OK;
    
}

总结

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

栈和队列也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。

image-20200419170946766