队列和循环队列定义


队列定义


队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

image.png

队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。


循环队列定义

我们在思考队列的时候不难发现，当队列的头尾指针都在最后一个位置的时候，看起来已经没有空间可以使用了，而前面的空间都被浪费掉了。所以，循环队列的出现就能解决这一浪费存储空间的问题。当然也可以在入队的时候判断如果队尾指针已经是最后的位置了，这个时候如果有新的数据入队，可以将此时队头指针和队尾指针之间的数据，整体搬移到数组中 0 到 尾指针-头指针 的位置。这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度就不一样了，使用均摊法分析可知，在 n - 1 种情况下，都不会涉及到搬移数据的操作，这些情况下的入队操作时间复杂度为 O(1)，而剩下的一种情况就会涉及到最多 n 个数据的搬移操作，这种情况下的入队操作时间复杂度为 O(n)，所以将这种情况摊还到 n - 1 种情况下之后，入队操作的平均时间复杂度就是 O(1)。

循环队列，顾名思义，长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

image.png

我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

image.png

通过这样的方法，我们成功避免了数据搬移操作。这里有一个注意点，尾指针 tail 在第一次入队操作之后，就会指向最后一个元素的下一个位置，相当于会浪费一个存储空间。因为这样就不会导致队列判空和判满冲突的情况。

顺序队列具体实现

顺序队列实现

顺序队列我们可以使用数组来实现，关于队列的操作有初始化，入队，出队等操作，接下来我们一一实现。
在具体实现前还是老规矩，先给出一些基本的数据结构定义。

在实现顺序队列之前，我们先看下面两幅图，通过这两幅图相信可以帮助你理解为什么队列需要头指针和尾指针。
image.png

当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。


当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

image.png

上面都是比较普遍的场景，但是我们可以发现，当队尾指针 tail 移动到了分配的连续存储空间的最后一个位置时，如果一直有数据出队，那么头指针 head 会一直往后移动，刚好移动到最后一个位置时，此时头尾指针相遇，表面上看起来队列已经满了，但其实此时队列是空的。这就是队列的局限之处，无法最大化利用内存空间，我们在下一节的循环队列中就会解决这个问题。

接下来我们来看一下顺序队列的基础数据结构的定义，代码如下:

  1. #define OK 1
  2. #define ERROR 0
  3. #define TRUE 1
  4. #define FALSE 0
  5. #define MAXSIZE 20 /* 存储空间初始分配量 */
  7. typedef int Status;
  8. typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
  10. /* 循环队列的顺序存储结构 */
  11. typedef struct
  12. {
  13.     QElemType data[MAXSIZE];    /* 存放队列数据的数组 */
  14.     int front;                   /* 头指针 */
  15.     int rear;                    /* 尾指针 */
  16. }Queue;

顺序队列初始化

因为我们在定义顺序队列的时候，已经声明了一个数据类型为数组的属性，所以在初始化的时候我们就不需要去手动 malloc 来分配内存空间了。我们只需要让队头和队尾指针都为空即可。

// 初始化顺序存储的队列
Status InitQueue(Queue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

将队列置空

要将一个顺序队列置空，也很简单，因为是顺序存储结构，所以只需要改变头尾指针的值即可。代码如下:

Status ClearQueue(Queue *Q)
{
    Q->front = Q->rear = 0;
    return OK;
}

判断顺序队列是否为空

要判断一个顺序队列是否为空，我们简单思考一下就能得到结论，当头尾指针都等于 0 的时候就表示队列为空，那么延伸到头尾指针相等情况下呢，我们想一下，如果队头和队尾都相等但不等于 0 ，其实也是队列为空的场景。所以代码如下:

Status QueueEmpty(Queue *Q)
{
    if (Q.front == Q.rear)
    {
        return TURE;
    }
    else 
    {
        return FALSE:
    }
}

获取顺序队列的长度

因为顺序队列的头尾指针关系肯定是头指针小于等于尾指针，所以队列的长度可以直接使用尾指针减去头指针。代码实现如下：

int QueueLength(Queue Q) 
{
    return Q.rear - Q.font;
}

获取顺序队列的队头元素

注意，获取队头元素不等于出队，所以我们并不需要修改 head 指针，但是在获取队头元素之前还需要判断一下队列是否为空，如果为空的话就返回 ERROR，代码如下:

Status GetHead(Queue Q,QElemType *e){
    //队列已空
    if (Q.front == Q.rear)
        return ERROR;

    *e = Q.data[Q.front];
    return OK;
}

顺序队列入队

入队操作的判断条件很简单，只要队列还有空间就能入队，也就是说我们判断一下队列空间是否已满，如果满了就返回 ERROR，如果没满，就直接入队即可。这里判断队列已满的条件我们不难得出：当队尾指针指向了数组的最后一个位置的时候。

Status EnQueue(Queue *Q, QElemType e)
{
    // 队列已满，无法入队
    if (Q->rear == MAXSIZE - 1)
    {
        return ERROR;
    }
    // 赋值并移动尾指针到下一个位置
    Q->data[Q->rear++] = e;
    return OK;
}

顺序队列出队

出队操作与入队操作相反，需要判断队列是否为空，判断是否为空我们前面已经探索过了，这里直接给出代码实现:

Status DeQueue(Queue *Q, QElemType *e)
{
    // 队列为空，返回 ERROR
    if (Q->front == Q->rear)
    {
        return ERROR;
    }
    // 取出值，将队头指针向后移动一个位置
    *e = Q->data[Q->front++];
    return OK;
}

顺序队列遍历

要遍历一个顺序队列，我们只需要从队头遍历到队尾即可。

Status QueueTraverse(Queue Q)
{
    for(int i = Q.font;i <= Q.rear;i++)
    {
        printf("%d\n", Q.data[i]);
    }
    printf()
}

链式队列实现

实现一个链式队列，我们可以借助一个空的头节点来保持队头 top 指针不用变化。当入队时，改变队尾指针的指向即可。我们先定义一下基础的数据结构。

// 链式队列节点
typedef struct QNode
{
    QElemType data;
    struct Node *next;
}QNode, *QueuePtr;

// 链式队列
typedef struct 
{
    // 队头指针
    QueuePtr front;
    // 队尾指针
    QueuePtr rear;
}LinkQueue;


链式队列初始化

初始化一个链式队列，我们要先创建一个空的头节点，然后让队头指针和队尾指针都指向这个头节点即可。具体实现代码如下：

// 链式队列初始化
Status InitQueue(LinkQueue *Q)
{
    // 创建头节点
    QueueNode head = (QueueNode)malloc(sizeof(Node));
    if(head == NULL) return ERROR;
    Q->front = head;
    Q->rear = head;
    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;
    }
    return OK;
}

清空链式队列

// 清空链式队列(保留头节点)
Status ClearQueue(LinkQueue *Q)
{
    QueuePtr p, q;
    // 先让尾指针移动到头指针的位置
    Q->rear = Q->front;
    // 让临时指针变量 p 指向头节点的后继节点
    p = Q->front->next;
    // 将头节点的后继指针域置为空
    Q->front->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

判断链式队列是否为空

和顺序队列一样，链式队列的判空条件也是头尾指针相等。

Status QueueEmpty(LinkQueue *Q)
{
    if (Q->front == Q->rear) return TRUE;
    else return FALSE;
}

获取链式队列的长度

获取链式队列的长度有两种方式。一种是在定义链式队列的结构的时候增加一个 length 属性，但是这样会在入队和出队的时候多做一些操作。第二种方式是遍历整个链式队列。我们这里采取第二种方式，代码如下

int QueueLength(LinkQueue Q)
{
    int i = 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p)
    {
        i++;
        p = p->next;
    }
    return i;
}

链式队列入队

这里并不需要判断队列是否为空，因为初始化的时候已经有头节点了。同时由于是链式存储结构，也没必要判断队列是否为满，因为理论上链式队列可以无限延伸。

Status EnQueue(LinkQueue *Q, QElemType e)
{
    // 创建新节点
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (s == NULL) return ERROR;
    s->data = e;
    s->next = NULL;

    // 更新尾指针指向
    Q->rear->next = s;
    Q->rear = s;

    return OK;
}

链式队列出队

出队时需要判断队列是否为空，也就是判断头尾指针是否相等。

Status DeQueue(LinkQueue *Q, QElemType *e)
{
    // 如果队列为空，返回 ERROR
    if (Q->front == Q->rear) return ERROR;

    QueuePtr p;
    p = Q->front->next;
    *e = p->data;

    // 移动头节点的后继节点指向
    Q->front->next = p->next;
    // 如果出队的节点刚好是尾指针指向的节点，那么让尾指针指向头节点
    if (Q->rear == p) Q->rear = Q->front;
    // 释放掉临时指针变量
    free(p);
    return OK;
}

获取链式队列的队头元素

同样的，获取链式队列的队头元素也需要判断队列是否为空。

Status GetHead(LinkQueue Q, QElemType *e)
{
    if (Q->font != Q->rear)
    {
        *e = Q.front->next->data;
        return TRUE;
    }
    return FALSE;
}

链式队列的遍历

遍历链式队列的话比较简单，实现如下:

Status QueueTravese(LinkQueue Q)
{
    QueuePtr p;
    p = Q.front->next;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

循环队列具体实现

循环队列前面我们已经讲过相关的定义了，这里我们来实现这种数据结构。还是老规矩，我们先给出基础的数据结构定义，这里我们采用顺序存储的方式来实现循环队列。

typedef struct 
{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

循环队列初始化

我们根据前面循环队列的定义以及相关的示意图可知，初始化循环队列的时候，头尾指针都指向同一个起始位置 0。

// 初始化顺序存储的队列
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

将循环队列置空

同样的，由于是顺序存储的空间，要置空一个循环队列，只需要让头尾指针回归到初始的位置即可。

Status ClearQueue(SqQueue *Q)
{
    Q->front = Q->rear = 0;
    return OK;
}

判断循环队列是否为空

和普通的队列一样，判断循环队列是否为空，也只需要判断头尾指针是否相遇即可。

Status QueueEmpty(SqQueue *Q)
{
    if (Q.front == Q.rear)
    {
        return TURE;
    }
    else 
    {
        return FALSE:
    }
}

获取队列的长度

在一般情况下，队列的长度我们最先想到的就是用队尾减去对头的值，但是当队尾小于队头时呢？所以这里就不能是简单的队尾减队头了。我们不妨多分析几个不同的场景来找出答案。

我们设队列的空间大小为 10，初始化的时候队头和队尾都为 0。随着不停地入队出队操作，队头和队尾的位置也在一直发生着变化。

1.队头的值小于队尾的值
比如队头为 2，队尾为 8，那么显然队列的长度就是 8 - 2 = 6
比如队头为 4， 队尾为 10，那么队列的长度就是 10 - 4 = 6
2.队头的值大于队尾的值
比如队尾为 2，队头为 8，那么队列的长度就是 (10 - 8 + 2) = 4
比如队尾为 4，队头为 10，那么队列的长度就是 (10 - 10 + 4) = 4
3.队头的值等于队尾的值
这种情况，显然队列的长度就是 0 了

针对于上面这三种情况，我们不难得出队列的长度 = (队尾 - 队头 + 队列空间大小) % 队列空间大小。
比如队头为 2，队尾为 8，那么 (8 - 2 + 10) % 10 = 6
比如队头为 4，队尾为 10，那么 (10 - 4 + 10) % 10 = 6
比如队尾为 2，队头为 8，那么 (2 - 8 + 10) % 10 = 4
比如队尾为 4，队头为 10，那么 (4 - 10 + 10) % 10 = 4

对于循环队列 空间长度为N 是固定的

举个简单例子 空间 位置为 1，2，3，4，5，6， 空间长度为6

本体中 front 不存数据

如果front <= rear 则（rear－front）> 0 实际空间长度就是 （rear-front）举例 front ＝ 1 ，rear ＝ 4

如果front > rear 则（rear－front）< 0 实际长度 就是 （rear＋N－front） 举例front ＝ 5 ，rear＝ 2

为了统一两种情况 所以给出的结果为（rear－front＋N）％ N

所以最终代码实现如下:

int QueueLength(SqQueue Q) 
{
    return (Q.rear - Q.font + MAXSIZE) % MAXSIZE;
}

获取循环队列的队头元素

获取队头元素并不等于出队，所以不需要改变队头指针的指向，但是要判断一下队列是否为空。

Status GetHead(SqQueue Q,QElemType *e){
    //队列已空
    if (Q.front == Q.rear)
        return ERROR;

    // 取出队头元素
    *e = Q.data[Q.front];
    return OK;
}

循环队列入队

循环队列的入队相比于普通的队列，也是需要移动队尾指针，不过这里有一个注意点，队尾指针在第一个元素入队之后，指向的是下一个位置，也就是说循环队列会浪费一个存储空间。同时，由于是循环队列，那么就不需要去判断队列是否为满了。但是对于尾指针移动来说，普通的队列只需要往后移动一位即可，体现在代码上就是 rear + 1，但对于循环队列来说，有可能发生队尾移动到起始位置。所以需要进行一下取余的操作，具体代码实现如下：

Status EnQueue(SqQueue *Q, QElemType e)
{
    // 将元素放入尾指针指向的节点
    Q->data[Q->rear] = e;

    // 移动尾指针到下一个位置
    Q->rear = (Q->rear + 1) % MAXSIZE;

    return OK;
}

循环队列出队

循环队列的出队操作相比入队，是需要判断队列是否为空的，出队操作需要移动头指针到下一个位置，按照同样的逻辑，头指针也可能发生入队时尾指针移动到起始位置的情况，同理代码实现如下;

Status DeQueue(SqQueue *Q, QElemType *e)
{
    // 如果队列为空，返回 ERROR
    if (Q->front == Q->rear) return ERROR;

    *e = Q->data[Q->front];

    Q->front = (Q->front + 1) % MAXSIZE;

    return OK;
}

遍历循环队列

最后我们要实现的是遍历循环队列，在遍历普通的队列的时候，是从头指针遍历到尾指针，并且递增条件是 i++。而在遍历循环队列的时候，显然就不能是简单的 i++ 了，因为会有 i 「溢出」的情况，所以需要进行简单的取余操作。具体实现如下:

Status QueueTraverse(SqQueue *Q)
{
    int i = Q->front;
    while (i != Q->rear)
    {
        printf("%d ", Q->data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}