队列
队列是一种特殊形式的线性表。它的插入和删除操作分别在表的两端进行，我们称插入的一端为队尾，删除的一端为队首。 其插入和删除操作分别被称为进队(enqueue)和出队(dequeue)。这种进队出队的操作，能够保证最早进队的数据也是最早出队的。 这就是所谓的先进先出的特性，即First-In, First-Out, FIFO。这一特性的最形象对比就是排队买东西，新来的人排在队尾，排在队伍最前面的人买完东西之后离开队伍。 显然，先来的人先买到东西走人。
和栈一样，队列中的数据之间前驱和后继关系仍然存在，我们同样可以以数组或者链表的形式来实现它。 链表因为其本身的动态特性，实现起来比较方便，效率也比较高。而数组的实现还需要两个指针来标记队首和队尾，如果超出了已经申请的内存大小，还需要动态的申请新的存储空间， 或者报错退出。
本文中，我们先使用比较简单的链表形式来介绍队列的工作机制。再以静态数组的队列为例，来说明基于数组的队列的边界处理方式。 我们还提供了动态数组和C++模板形式的队列，由于它们的思想都是一样的，这里不再详述。
1. 基于链表的队列
1.1 list_head的队列操作
参照栈一文，我们以哨兵节点的后继为表首，其前驱为表尾。它们也分别是这里的队首和队尾。 同样的使用一个嵌有list_head的数据类型double_node，来实现一个存储double类型数据的队列结构。它有两个字段，其中key保存实际的数据，list则是链表结构。 我们可以通过宏定义list_entry来根据字段list的地址获取包含该链表节点的double_node的数据对象地址。
struct double_node {
double key;
struct list_head list;
};
接着，定义一个哨兵节点用于标记队列。我们通过函数init_list_head对其进行初始化，让其next和prev指针都指向自身，形成一个双向循环链表。 在以后的运行过程中，next将指向队首，prev指向队尾。
struct list_head queue;
init_list_head(&queue);
然后，创建一个double_node的数组，并依次对其进行初始化，之后通过函数list_add_tail依次将它们从表尾进队。按照下面的for循环，我们依次进队了5个数分别是 1.1, 1.2, 1.3, 1.4, 1.5。
struct double_node *nodes = (struct double_node *)malloc(5 * sizeof(struct double_node));
for (int i = 0; i < 5; i++) {
nodes[i].key = 1.1 + 0.1 * i;
init_list_head(&(nodes[i].list));
list_add_tail(&(nodes[i].list), &queue);
}
下面我们再依次从队首中将刚刚进队的数据取出，并在下面的第3行中判定出队的数据与我们进队时的数据相同。
for (int i = 0; i < 5; i++) {
struct double_node *pnode = list_entry(queue.next, struct double_node, list);
assert((pnode->key) == (1.1 + 0.1 * i));
list_del(queue.next);
}
我们也可以交换队首和队尾的角色，通过函数list_add从表首进队，并从表尾出队。除了哨兵的前驱后继指针的含义不一样之外，并不会引入什么额外的操作。
|
|
1.2 DataList的队列操作
现在，我们将对模板类DataList进行扩展，为之赋予队列的特性。先以表尾作为队尾实现进队函数enqueue， 该函数只有一个参数接收需要入栈的数据，在函数中通过DataList的接口函数insert_prev将新的数据插入哨兵节点之前，也就是队尾。
DataListNode * enqueue(T const & v) {
return insert_prev(&mHead, v);
}
我们提供了两个版本的出队函数dequeue，它们都是把队首中的数据保存到一个缓存中，再将队首的节点从链表中移除。左边的函数将缓存的数据作为函数的返回值，这种方式适用于比较简单的数据结构。 对于一些复杂的数据结构它可能需要大量的拷贝工作，效率会很低。右边的函数，以一个引用作为输入，并在函数中把缓存的数据直接写道这个引用中。它没有显式的返回，而是通过引用来输出出栈的数据， 效率上会高一点，但是使用起来不是很直接，适用于那些比较复杂的数据结构。
|
|
2. 静态数组的队列
数组形式的队列需要两个指针分别指示队首和队尾的位置，数组一文中定义的结构不能满足它的需要。 所以这里我们重新定义一系列的结构体来实现队列。我们先从最简单的静态数组开始，使用数组一文中的宏方式， 来实现一种类似C++模板的机制。为了突出静态数组形式的队列特性，下面左边定义结构体前缀为s_queue，右边是按照宏定义展开后的结构体，其中的double可以替换为其它类型。
|
|
这里定义了四个指针，其中begin指示队首，end指示队尾，stor_begin和stor_end分别指示存储空间的起始和结束位置。
此外还额外定义了一个联合体union queue_flag，其定义如下，我们通过一个结构体的位定义来描述队列的属性。
目前只有一个overwrite的属性，说明了当队列满的时候，是否用新的数据覆盖队首的数据。
|
|
联合体中的各个字段实际上对应的是同一个物理内存，也就是说我们通过bits或者all访问的都是同一个对象，只是解释的方式不同而已。
通过bits我们可以具体的访问到struct queue_flag_bits定义的各个字段。all则将整个字段当作一个无符号的32位数据来对待。
因为字段overwrite的定义对应着uint32的最低位，所以我们通过位运算修改all的第0位，与通过bits来直接调整overwrite的值是一样的效果。
即下面左右两边的代码是等价的。
|
|
2.1 初始化
下面的代码就是静态队列的初始化函数，它又三个参数，其中q为将要初始化的队列对象，buf指示了队列的存储空间的起始地址，capacity则是队列容量。 这个初始化函数的内容很简单，就是对结构体的几个成员指针赋予初值。在第8行中，我们设定overwrite值为0。默认情况下，当队列满时新的数据是不能覆盖队首中的数据。 我们也可以在使用过程中修改这一特性。
int TEMPLATE_FUNCTION(s_queue, init)(TEMPLATE_TYPE(s_queue) *q, T *buf, int capacity) {
q->stor_begin = buf;
q->stor_end = q->stor_begin + capacity;
q->begin = q->stor_begin;
q->end = 0;
q->flags.bits.overwrite = 0;
return 0;
}
由于静态数组是针对没有内存管理单元的系统设计的，所以不能在运行过程中动态的申请内存，这就要求我们在编译之初就能够提供队列的存储空间和容量。 下面就是一种比较常用的形式。通过一个宏来指明数组的容量，这样可以提高代码的自解释性。然后定义一个数组缓存和数组，并调用s_queue_T_init进行队列的初始化。
#define QUEUE_BUF_LEN 1024
double queue_buf[QUEUE_BUF_LEN];
s_queue_double queue;
s_queue_double_init(&queue, queue_buf, QUEUE_BUF_LEN);
由于链表具有较高的插入和删除的效率，很适合用来实现队列，而且不需要过多的关注边界问题。而数组的实现就相对麻烦一些，虽然我们可以用两个指针指示队首和队尾， 每次进队之后队尾就会后移一个单元，而每次出队之后队首指针加一。但是多次进队出队操作之后，队首和队尾指针就会超出分配的内存边界。实际上每次出队之后原来的存储单元就是空闲的， 可以写入新的数据。为了充分的利用内存，防止超出存储边界，我们需要一种循环的存储机制，这点由进队和出队操作的边界处理方式来保证。下面让我们先来看下进队操作。
2.2 进队操作
对于基于数组的队列操作，最主要的是处理它的边界问题。下面是进队的操作函数，有两个参数，其中q为目标队列对象，data是需要进队的数据。
首先，我们需要检查队列是否已满。后面我们会看到，进队和出队的操作将始终保证队首指针begin指向队列中第一个元素。并且只要队列不空， 队尾指针end将始终指向第一个空闲单元。当队尾指针与队首指针相等时，它们所指的是同一个对象，就会形成一个矛盾。此时，end所指就不再是空闲的了， 也就是说队列已满。
int TEMPLATE_FUNCTION(s_queue, enqueue)(TEMPLATE_TYPE(s_queue) *q, T data) {
// 队列已满
if (q->end == q->begin) {
如果已满，那么我们需要根据队列的配置overwrite来判定是否需要覆盖队首的数据。overwrite为0则直接报告队列已满并返回。
if (0 == q->flags.bits.overwrite)
return QUEUE_FULL;
否则，将队首指针后移一个单元。这样原来的队首位置就是一个空闲的存储空间，可以写入新的数据。存在一种情况就是，队首指针指向了存储的边界stor_end。 此时需要重置队首指针指向存储开始的位置上，如此形成一个循环，保证队首指针始终在队列的存储空间中。
q->begin++;
if (q->begin == q->stor_end)
q->begin = q->stor_begin;
}
当队列为空时，队尾指针end的值一定为0。此时队列中所有的空间都是空闲的，其中队首指针所指的单元可以认为是第一个空闲单元，以后的数据应当从该单元开始存储。 所以这里令队尾指针指向这一空闲单元。
// 队列为空
if (0 == q->end)
q->end = q->begin;
此时，我们能够保证队尾指针end一定指向队列中第一个空闲单元，所以这里直接对该单元赋值，让其保存需要进队的数据。
q->end[0] = data;
接下来，我们需要调整队尾指针，保证该函数退出之后，end始终指向第一个空闲的存储单元。首先让end自增，然后判断end是否到达了存储单元的边界， 保证end始终在队列的存储空间中。
q->end++;
if (q->end == q->stor_end)
q->end = q->stor_begin;
最后完成进队操作，报告没有错误，并返回。
return QUEUE_NOERR;
}
2.3 出队操作
进队操作主要是在处理队尾指针end的边界问题，出队操作则主要是在处理队首指针begin的边界问题。下面是出队操作的函数，它有两个参数，其中q为目标队列对象， buf是用于保存出队数据的缓存。
首先我们确认队列中有数据，若为空，则报错返回。
int TEMPLATE_FUNCTION(s_queue, dequeue)(TEMPLATE_TYPE(s_queue) *q, T *buf) {
// 队列为空
if (0 == q->end)
return QUEUE_EMPTY;
由于队首指针begin始终指向队列中第一个有效的数据，所以，我们可以直接将之写入输出缓存中。
*buf = *(q->begin);
接下来处理队首指针的边界问题，首先后移一个单元，若到达了存储边界则返回指向存储的开始位置。
q->begin++;
if (q->begin == q->stor_end)
q->begin = q->stor_begin;
此外，出队操作可能导致队列为空的情况。该情况的判定条件就是在处理队首指针的边界问题时，达到了队尾指针的位置上，此时说明队首指针之后再没有可用的数据了。 因此，我们需要将队尾指针end指向0来标记队列为空。
if (q->begin == q->end)
q->end = 0;
最后完成进队操作，报告没有错误，并返回。
return QUEUE_NOERR;
}
2.4 队列长度和有效数据范围
在入队和出队操作过程中，我们通过begin和end两个指针循环的使用着内存。这就意味着end指针不总是大于egin，下面的函数用于计算队列的长度，也就是保存的数据量。 通过它可以了解这个循环使用内存的方式下有效的数据范围。
int TEMPLATE_FUNCTION(s_queue, size)(TEMPLATE_TYPE(s_queue) *q) {
队尾指针end为零标识着队列为空，所以直接返回0
if (0 == q->end)
return 0;
在队列非空的情况下，我们有一个循环不变式，就是对首指针始终指向队列中的第一个数据，而队尾指针始终指向第一个空闲的单元。 所以当begin < end的时候，有效的数据范围就是[begin, end)这个前开后闭的区间，队列长度为end - begin。
if (q->begin < q->end)
return q->end - q->begin;
否则，意味着end曾接触到了队列的存储边界，并因此返回到存储的起始位置上过。此时有效的数据范围就是[begin, stor_end) 和 [stor_begin, end)两段，这里特意将begin放在end之前， 是为了突出在逻辑上[begin, stor_end)实际在[stor_begin, end)之前，而物理存储上前者在后者之后。
else
return (q->stor_end - q->begin) + (q->end - q->stor_begin);
}
3. 完
队列在线性表的一端插入数据，另一端删除数据，对应的操作称为进队和出队。这种操作可以保证其中保存的数据具有先进现出的特性。 链表具有较高的插入和删除效率，实现起来比较简单，不需要过多的讨论边界问题。而数组的实现方式，我们需要至少两个指针分别指示着队首和队尾，为了充分的利用存储空间，防止超出存储边界， 我们设计了一种循环的存储机制。