6. 队列（Queue）

完整示例代码请移步至GitHub | Gitee

如有错误，还请指正。

微信扫描下方二维码，一起学习更多计算机基础知识。

6. 队列（Queue）

前面讲过了一种受限的线性表——栈，它只能在一端操作（先入后出）。现在介绍另一种受限的线性表——队列。

6.0. 什么是队列？

先举一个日常例子，排队买饭。

6. 队列（Queue）

大家按先来后到的顺序，在窗口前排队买饭，先到先得，买完之后走开，轮到下一位买，新来的人排在队尾，不能插队。

可见，上面的“队”的特点是只允许从一端进入，从另一端离开。

这样的一个队，放在数据结构中就是“队列”。

首先，队列是一个线性表，所以它具有线性表的基本特点。

其次，队列是一个受限的线性表，受限之处为：只允许从一端进入队列，从另一端离开。

根据以上特点，可以画出示意图：

6. 队列（Queue）

出队元素 1，入队元素 4 之后：

6. 队列（Queue）

下面是几个相关名词：

入队：进入队列，即向队列中插入元素
出队：离开队列，即从队列中删除元素
队头：允许出队（删除）的一端
队尾：允许入队（插入）的一端
队头元素：队列中最先入栈的元素
队尾元素：队列中最后入栈的元素

我们可以直接将队头元素看作队头，队尾元素看作队尾。（这些名词概念，有所理解即可，不必细究）

队列的重要特性是在队尾进行入队操作，在队头进行出队操作，所以上图元素的入队顺序为：1、2、3，出队顺序为：1、2、3，也即，先入队的先出队（First In First Out, FIFO），后入队的后出队（Last In Last Out, LILO）.

总结一下，队列是一种只允许在一端进行插入操作，在另一端进行删除操作的先入先出的受限的线性表。

6.1. 队列的实现思路

和栈一样，队列也可以有两种实现方式：数组实现的顺序队列和链表实现的链队列。

6.1.0. 数组实现——顺序队列

一个用数组实现的顺序队列如下图所示：

6. 队列（Queue）

可以看到，要实现一个顺序队列，我们需要以下结构：

存储数据的数组 —— data[]
表示队列的最大容量的值 —— MAXSIZE
标识队头端的队头下标 —— front
标识队尾端的队尾下标 —— rear

front 和 rear 会随着入队和出队操作而变化，为了方便起见，我们规定在非空队列中，队尾下标是队尾元素的下一个元素的下标。

了解了结构之后，我们可以很容易使用 C 语言的结构体实现它：

#define MAXSIZE 5 //顺序队列的最大存储容量
/*顺序队列的结构体*/
typedef struct {
    int data[MAXSIZE];
    int front; //队头下标
    int rear; //队尾下标
} QueueArray;

6.1.1. 链表实现——链队列

我们使用带头节点的单链表来实现队列，如下图所示：

6. 队列（Queue）

可以看到，要实现一个链队列，需要以下结构：

单链表的基本单元结点 —— QueueNode
- 存储数据的数据域 —— data
- 指向下一个结点的指针域 —— next
指向链表的头指针 —— head
标识队头端的队头指针 —— front
标识队尾端的队尾指针 —— rear

其中，头指针 head 和队头指针 front 都指向了单链表的第一个结点，所以这个指针可以合二为一，队头指针即头指针。

如此一来，我们可以借助链表的尾插法实现队列的入队操作，借助链表的头删法实现队列的出队操作。

搞清了结构，用结构体实现如下：

/*单链表的结点的结构体*/
typedef struct QueueNode {
    int data; //数据域
    struct QueueNode *next; //指针域
} QueueNode;

/*链队列的结构体*/
typedef struct {
    QueueNode *front; //队头指针
    QueueNode *rear; //队尾指针
} QueueLink;

6.2. 队列的状态

6.2.0. 顺序队列（问题版）

【空队列】：空队列中没有元素，此时，队头下标和队尾下标均为 0，即front = rear = 0：

6. 队列（Queue）

【非空非满队列】：队列不是空队列且有剩余空间：

6. 队列（Queue）

【满队列】：顺序队列分配的固定空间用尽，没有多余空间，不能再插入元素，此时 front = 0，rear = MAXSIZE：

6. 队列（Queue）

从上图中可以看出，非空队列的队尾下标 rear 始终是队尾元素的下一个元素的下标。

6.2.1. 假满队列

以上是用数组实现的顺序队列的三种状态，但上图中三种队列是存在问题的，那就是队列的存储问题！

先再次明确队列的两条重要特性：

队列只允许在队头删除元素，在队尾插入元素
我们规定：front 是队头元素的下标，rear 是队尾元素的下标，二者会随着出队和入队操作而变化

由于上面的三幅图中 front 都在下标 0 处，所以不容易看出问题，请看下面的过程图：

6. 队列（Queue）

简单用文字描述以下上述过程：

图1：空队列

图2：进队 3 个元素：1、2、3

图3：出队 2 个元素：1、2

图4：入队 2 个元素：4、5

到此为止，一切正常。

图5：入队 1 个元素，但在图4中 rear = 5已经超出数组的最大范围，所以图5入队一个元素会报错，这个队列不能再插入元素了。

图5的队列满了吗？没满！能继续插入元素吗？不能！有剩余空间却不能用，这就好比有空房的酒店不让客户入住，这叫不会做生意。

满队列的是空间用尽，不能再插入元素的队列，虽然图5的队列也不能继续插入元素了，但它还有剩余空间，所以这样的队列还不能称之为满队列，可称之为假满队列。

之所以假满队列存在问题，是因为顺序队列的空间是有限的，通过若干入队操作之后，我们的 rear “跑”到数组外从而导致越界了。

6. 队列（Queue）

明明才存储了一个元素，却因为假满，整个队列不能再存储了。这样的队列肯定不是合格的数据结构。

怎么解决呢？报错是 rear 越界导致，而队列的前大部分都是空闲的，所以当 rear 越界时，我们可不可以将其移动到下标 0 处呢？

6. 队列（Queue）

显然是可以的，这样就构成了一个“循环”，我们称这种 front 和 rear可以循环利用的队列为循环队列。

6.2.2. 循环队列

为了突出“循环”二字，我们将这种顺序队列画成一个圆：

6. 队列（Queue）

循环队列的 rear 和 front 能够在队列中一圈一圈地转，像钟表的时针和分针一样。不会再出现不能利用的空间了。

顺序队列的形式从“直的”变成这种可循环的之后，对于状态的判断也改变了。

【空队列】：队列中没有元素，如上图。

请注意，空队列的条件并不是 front = rear = 0，比如一个空队列经过 3 次入队和 3 次出队操作后仍为空队列：

6. 队列（Queue）

所以，循环队列为空队列时，条件应该为 front = rear

【满队列】：队列中没有空闲空间

6. 队列（Queue）

上图是一个最大容量为 8 的空队列，入队 7 个元素后，队列中还剩 1 个空闲位置，如果此时我们再入队 1 个元素：

6. 队列（Queue）

此时队列中确实没有空闲空间了，但注意，此时队列满足了 rear = front ，但满足 rear = front的队列不应该是空队列吗？

这就产生误会了。

不如我们退一步海阔天空，少用一个元素，借此来消除误会。如下图，规定这样是一个满队列。

6. 队列（Queue）

我们规定，front 出现在 rear 的下一个位置时，队列为满队列。

比如在上图的满队列中， front = 3 在 rear = 2 的下一个位置。

所以队列为满队列的判定条件为：rear + 1 = front，但这的条件是不准确的。

因为循环队列中的 front 和 rear 都是循环使用的，就像钟表的时针一样，所以我们仅根据下标的大小来判断位置是不合理的。下面两个均是满队列，右图不满足rear + 1 = front：

6. 队列（Queue）

就像钟表的时针满 12 归零一样，front 和 rear 也应该满某个数后归零，这个数就是 MAXSIZE。

比如 rear = 7 时，如果按平常做法来，下一步应该是 rear = 8，但在这里，我们让其归零，所以下一步应该是 rear = 0。

用数学公式来表示上面的归零过程就是：rear % MAXSIZE

所以满队列的判断条件应该为：(rear + 1) % MAXSIZE = front。

【非空非满队列】 很好理解，不再赘述。

6.2.3. 链队列

我们使用带头结点的单链表来实现链队列。

【空队列】：即一个空链表，此时队头指针（兼链表头指针）和队尾指针均指向头结点。

6. 队列（Queue）

【非空队列】：不像顺序队列那样有空间的限制，链队列的空间是不受限制的（只要你的内存足够大），所以自然不存在“满队列”“循环队列”的概念。

6.3. 初始化

在进行队列的操作前，应该先将其初始化出来，即初始化一个空队列出来。

6.3.0. 顺序队列

将队列的队头下标和队尾下标置为 0 即可。

/**
 * 初始化顺序队列：将队头下标和队尾下标置为0
 * queue: 指向队列的指针
 */
void init(QueueArray *queue)
{
    queue->front = 0;
    queue->rear = 0;
}

6.3.1. 链队列

创造出头结点，然后将队头指针和队尾指针均指向头结点即可。

/**
 * 初始化链队列：将队头指针和队尾指针指向头结点
 */
void init(QueueLink *queue)
{
    //创造头结点
    QueueNode *head_node = create_node(0);
    //队头指针 队尾指针指向头结点
    queue->front = head_node;
    queue->rear = head_node;
}

6.4. 入队操作

入队操作只允许元素从队尾进。

6.4.0. 顺序队列

前面我们规定，顺序队列的队尾下标为队尾元素的下一个元素，所以直接将待入队元素放入队尾下标处，然后队尾下标“加一”。（注意：循环队列中的加一要对 MAXSIZE 取模）

6. 队列（Queue）

/**
 * 入队操作
 * queue: 指向队列的指针
 * elem: 入队的数据
 * return: 0失败，1成功
 */
int en_queue(QueueArray *queue, int elem)
{
    //判断队列是否已满
    if ((queue->rear + 1) % MAXSIZE == queue->front) {
        printf("队列已满，无法继续入队。\n");
        return 0;
    }
    //元素入队
    queue->data[queue->rear] = elem;
    //队尾下标加一
    queue->rear = (queue->rear + 1) % MAXSIZE;
    return 1;
}

6.4.1. 链队列

链队列的入队操作本质是单链表的[尾插法](###2.7.3. 尾插法)：

/** * 入队操作
 * queue: 指向队列的指针
 * elem: 入队的数据
 */
void en_queue(QueueLink *queue, int elem)
{
    //创造新结点
    QueueNode *new = create_node(elem);
    //入队（尾插法）
    queue->rear->next = new;
    queue->rear = new;
}

6.5. 出队操作

出队操作只允许元素从队头出。

6.5.0. 顺序队列

将队头下标处的元素出队，然后将队头下标“加一”（对 MAXSIZE 取模）。

6. 队列（Queue）

/**
 * 出队操作
 * queue: 指向队列的指针
 * elem: 指向保存出队数据的变量
 * return: 0失败，1成功
 */
int de_queue(QueueArray *queue, int *elem)
{
    //判读队列是否为空
    if (queue->front == queue->rear) {
        printf("队列空，无元素可出。\n");
        return 0;
    }
    //元素出队
    *elem = queue->data[queue->front];
    //队头下标加一
    queue->front = (queue->front + 1) % MAXSIZE;
    return 1;
}

6.5.1. 链队列

链队列的出队操作本质上是单链表的头删法。注意，如果出队的是队列中最后一个元素，需要在出队后，将队尾指针重新指向头结点，重新形成空队列。

/**
 * 出队操作
 * queue: 指向队列的指针
 * elem: 指向保存变量的指针
 * return: 0失败，1成功
 */
int de_queue(QueueLink *queue, int *elem)
{
    //判读队列是否为空
    if (queue->front == queue->rear) {
        printf("队列空，无元素可出。\n");
        return 0;
    }
    QueueNode *front_node = queue->front->next; //队头元素
    //保存数据
    *elem = front_node->data;
    //队头元素出队（头删法）
    queue->front->next = front_node->next;
    //如果元素出完，队尾指针重新指向头结点
    if (front_node == queue->rear)
        queue->rear = queue->front;
    free(front_node);
}

6.6. 遍历操作

这里以打印整个队列为例，介绍如何遍历队列。

顺序队列有队头下标和队尾下标，链队列有队头指针和队尾指针，我们要做的就是借助一个临时变量，从队头下标逐个遍历到队尾下标即可。

6.6.0. 顺序队列

借助临时变量 i，从队头下标开始逐个“加一”直到队尾下标结束。

开始标志为：i = front

加一操作为：i = (i + 1) % MAXSIZE

结束标志为：i % MAXSIZE = rear

/**
 * 打印队列
 */
void output(QueueArray queue)
{
    int i = queue.front;
    while (i % MAXSIZE != queue.rear) {
        printf("%d ", queue.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}

如何计算顺序队列的长度？当然你可以遍历队列然后借助计数变量来存储长度，这样比较麻烦。因为顺序队列是使用数组实现的，所以顺序队列的长度我们可以直接根据下标计算出来。

如果是一个非循环队列，那很简单，直接 rear - front 就是队列的长度了。

但循环队列不能这样直接减了，因为 rear 和 front 之间的位置关系是不确定的。

6. 队列（Queue）

左图 rear < front，我们可以将其长度看成两部分组成：

下标 0 到 rear，长度为 rear - 0
下标 MAXSIZE - 1 到 rear，长度为 MAXSIZE - front

所以长度为 rear - front + MAXSIZE

为了满足右图 rear > front 的情况，如果按照上式，则此时多加了一个 MAXSIZE，所以需要对其再对 MAXIZE 取余。

所以循环队列的长度为 (rear - front + MAXSIZE) % MAXSIZE（空队列也满足）。

6.6.1. 链队列

借助指针 p 从队头元素遍历至队尾元素即可。

/**
 * 打印队列
 */
void output(QueueLink *queue)
{
    QueueNode *p = queue->front->next; //p指向队头元素
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

6.0. 什么是队列？

6.1. 队列的实现思路

6.1.0. 数组实现——顺序队列

6.1.1. 链表实现——链队列

6.2. 队列的状态

6.2.0. 顺序队列（问题版）

6.2.1. 假满队列

6.2.2. 循环队列

6.2.3. 链队列

6.3. 初始化

6.3.0. 顺序队列

6.3.1. 链队列

6.4. 入队操作

6.4.0. 顺序队列

6.4.1. 链队列

6.5. 出队操作

6.5.0. 顺序队列

6.5.1. 链队列

6.6. 遍历操作

6.6.0. 顺序队列

6.6.1. 链队列

热门文章