提要钩玄：本文次要介绍队列的构造、基本原理及操作，波及到两种实现：程序队列和链队列。

1. 什么是队列？

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

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

可见，下面的“队”的特点是只容许从一端进入，从另一端来到。

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

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

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

依据以上特点，能够画出示意图：

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

上面是几个相干名词：

入队：进入队列，即向队列中插入元素
出队：来到队列，即从队列中删除元素
队头：容许出队（删除）的一端
队尾：容许入队（插入）的一端
队头元素：队列中最先入栈的元素
队尾元素：队列中最初入栈的元素

咱们能够间接将队头元素看作队头，队尾元素看作队尾。（这些名词概念，有所了解即可，不用细究）

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

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

2. 队列的实现思路

和栈一样，队列也能够有两种实现形式：数组实现的程序队列和链表实现的链队列。

2.1. 数组实现——程序队列

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

能够看到，要实现一个程序队列，咱们须要以下构造：

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

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

理解了构造之后，咱们能够很容易应用 C 语言的构造体实现它：

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

2.2. 链表实现——链队列

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

能够看到，要实现一个链队列，须要以下构造：

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

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

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

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

/*单链表的结点的构造体*/typedef struct QueueNode {    int data; //数据域    struct QueueNode *next; //指针域} QueueNode;/*链队列的构造体*/typedef struct {    QueueNode *front; //队头指针    QueueNode *rear; //队尾指针} QueueLink;

3. 队列的状态

3.1. 程序队列（问题版）

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

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

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

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

3.2. 假满队列

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

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

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

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

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

图1：空队列

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

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

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

到此为止，一切正常。

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

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

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

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

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

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

显然是能够的，这样就形成了一个“循环”，咱们称这种 front 和 rear能够循环利用的队列为循环队列。

3.3. 循环队列

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

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

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

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

请留神，空队列的条件并不是 front = rear = 0，比方一个空队列通过 3 次入队和 3 次出队操作后仍为空队列：

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

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

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

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

这就产生误会了。

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

咱们规定，front 呈现在 rear 的下一个地位时，队列为满队列。

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

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

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

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

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

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

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

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

3.4. 链队列

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

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

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

4. 初始化

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

4.1. 程序队列

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

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

4.2. 链队列

发明出头结点，而后将队头指针和队尾指针均指向头结点即可。

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

5. 入队操作

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

5.1. 程序队列

后面咱们规定，程序队列的队尾下标为队尾元素的下一个元素，所以间接将待入队元素放入队尾下标处，而后队尾下标“加一”。（留神：循环队列中的加一要对 MAXSIZE 取模）

/** * 入队操作 * 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;}

5.2. 链队列

链队列的入队操作实质是单链表的尾插法：

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

6. 出队操作

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

6.1. 程序队列

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

/** * 出队操作 * 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.2. 链队列

链队列的出队操作实质上是单链表的头删法。留神，如果出队的是队列中最初一个元素，须要在出队后，将队尾指针从新指向头结点，从新造成空队列。

/** * 出队操作 * 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);}

7. 遍历操作

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

程序队列有队头下标和队尾下标，链队列有队头指针和队尾指针，咱们要做的就是借助一个长期变量，从队头下标一一遍历到队尾下标即可。

7.1. 程序队列

借助长期变量 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 之间的地位关系是不确定的。

左图 rear < front，咱们能够将其长度看成两局部组成：

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

所以长度为 rear - front + MAXSIZE

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

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

7.2. 链队列

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

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

以上就是队列的基本原理及操作。
残缺代码请移步至 GitHub | Gitee 获取
如有谬误，还请斧正。
如果感觉写的不错，能够点个赞和关注。后续会有更多数据结构和算法相干文章。

【举荐浏览】

【数据结构】用具体图文把「栈」搞明确（原理篇）
详解 | 写完这篇文章我终于搞懂链表了
如何把握 C 语言的一大利器——指针？
用图和代码让你搞懂程序构造线性表