双端队列
通过对数据结构栈和队列的分析， 我们知道在同一端进行插入和删除操作就可以得到栈，在一端插入另一端删除就可以得到队列。有些时候，我们可能需要组合这些操作， 于是就有了所谓的双端队列，它与栈和队列没什么太大的差别，就是可以在线性表的两端插入和删除数据。
同样的双端队列也可以通过链表和数组两种形式来实现。链表的实现方式比较简单，不需要过多的讨论边界问题。 比如说Linux内核所用的list，通过list_add和list_add_tail两个函数就可以分别在队首和队尾插入新的数据； 而函数list_del有一个输入参数可以移除指定的链表节点，所以需要删除队首就把队首节点的地址作为参数调用list_del就可以，要删除队尾就传递队尾的地址。
数组形式双端链表实现就要相对麻烦一些，需要谨慎的处理边界问题。在本文中我们详细介绍动态数组形式的双端队列deque，该队列可以动态的申请内存， 理论上只要计算机的内存够用它可以存放任意多的数据，使用起来比较方便。
1. 定义和初始化
与数组形式的队列的实现一样，双端队列也需要两个指针分别指示队首和队尾的位置。 这里我们通过一些宏定义实现一种类似C++模板的双端队列，下面左边定义了前缀为deque的结构体，右边是按照宏定义展开后的结构体，其中double可以替换为其它类型。
|
|
在结构体中，我们定义了四个指针，begin,end, stor_begin, stor_end分别用于指示队首、队尾、存储空间的起始位置和结束位置。我们通过下面的函数deque_T_init完成双端队列的初始化工作， 其中T表示具体的队列元素类型。在该函数的一开始，我们就通过malloc申请4个单元的存储空间，并用stor_begin标记。接下来判定内存是否成功申请，若是则分别设定其它几个指针的初值。
int TEMPLATE_FUNCTION(deque, init)(TEMPLATE_TYPE(deque) *q) {
q->stor_begin = (T*)malloc(4 * sizeof(T));
if (0 == q->stor_begin)
return 1;
q->stor_end = q->stor_begin + 4;
q->begin = q->stor_begin;
q->end = 0;
return 0;
}
正如它的名字那样，双端队列是一个可以在两端自由的插入和移除数据的线性表。我们为之提供了push_front、push_back、pop_front、pop_back四个接口函数，分别用于在两端插入和移除数据。
2. push_front
下面是push_front的实现，它有两个参数。其中q是一个指示着目标队列的指针，data则是将要插入的数据。
int TEMPLATE_FUNCTION(deque, push_front)(TEMPLATE_TYPE(deque) *q, T data) {
接下来，先检查队列是否已满，判定的依据就是指针end和begin指向了相同的地址。如果队列已满，我们就通过接口函数adjust_capacity将队列的存储空间扩大两倍。
if (q->end == q->begin) {
int c = TEMPLATE_FUNCTION(deque, capacity)(q);
TEMPLATE_FUNCTION(deque, adjust_capacity)(q, c*2);
}
然后根据end是否为0，判定队列是否为空。如果队列空，则让end指向队列的起始位置，表示该位置是第一个空闲的地址。在整个队列的维护过程中，我们都在维护begin和end两个指针， 让begin始终指向队列中的第一个元素，end始终指向第一个空闲空间。
if (0 == q->end)
q->end = q->begin;
由于push_front需要再队首中插入数据，所以需要指针begin后退一个单元。
q->begin--;
这后退一个单元，可能导致begin超出已经申请的存储范围。此时，让begin指向存储空间的最后一个单元，循环的使用内存。因为在函数之处我们就已经处理了队列满的情况，所以此时该单元一定是空闲的。
if (q->begin < q->stor_begin)
q->begin = q->stor_end - 1;
在处理了所有的边界条件之后，我们就可以将新的数据写入队首了，并返回了。
q->begin[0] = data;
return DEQUE_NOERR;
}
3. push_back
下面是push_back函数的实现，其参数列表与push_front一样，分别指示了目标队列和将要插入的数据。
int TEMPLATE_FUNCTION(deque, push_back)(TEMPLATE_TYPE(deque) *q, T data) {
同样的，在函数的一开始我们就需要检查队列是否已满或者为空。如果已满则申请更大的内存，如果为空则调整队尾指针end。
if (q->end == q->begin) {
int c = TEMPLATE_FUNCTION(deque, capacity)(q);
TEMPLATE_FUNCTION(deque, adjust_capacity)(q, c*2);
}
if (0 == q->end)
q->end = q->begin;
由于我们始终保持end指向第一个空闲空间，所以这里可以直接将目标数据写入该空间中。
q->end[0] = data;
写入新数据后，end所指的空间将不再空闲，需要将之后移一个单元。但是后移操作可能导致end超出存储边界，此时循环的将之指向存储空间的起始位置。 因为在函数的起始，我们就已经处理了队列为满的情况，所以此时存储空间的起始位置一定是空闲的。
q->end++;
if (q->end == q->stor_end)
q->end = q->stor_begin;
处理完边界问题之后，我们就可以返回推出了。
return DEQUE_NOERR;
}
3. pop_front
下面是pop_front函数的实现，它从队首移除一个数据，有两个参数。其中q为目标队列，buf则是用于保存从队首中移除的数据。
int TEMPLATE_FUNCTION(deque, pop_front)(TEMPLATE_TYPE(deque) *q, T *buf) {
首先我们需要确定队列中有数据，否则报错退出。
if (0 == q->end)
return DEQUE_EMPTY;
然后用队首中的数据填充输出缓存buf。
*buf = *(q->begin);
接下来的工作就是移除队首数据，并处理各种边界条件。队首指针自加一就可以移除队首数据。
q->begin++;
队首指针自加一后，可能会超出存储边界。此时让指针begin指向存储空间的起始位置，以循环地使用存储空间。
if (q->begin == q->stor_end)
q->begin = q->stor_begin;
移除队首数据之后，队列可能为空，此时表现就是队首指针begin指向了end所指引的空闲空间。我们令队尾指针end为0，标记队列已空。
if (q->begin == q->end) {
q->begin = q->stor_begin;
q->end = 0;
}
最后返回退出。
return DEQUE_NOERR;
}
4. pop_back
下面是pop_back函数的实现，它从队尾移除一个数据，有两个参数。其中q为目标队列，buf则是用于保存从队尾中移除的数据。
int TEMPLATE_FUNCTION(deque, pop_back)(TEMPLATE_TYPE(deque) *q, T *buf) {
接下来仍然是先判定队列是否为空。
if (0 == q->end)
return DEQUE_EMPTY;
由于end始终指向队列中的第一个空闲单元，所以需要令其后退一个单元。
q->end--;
end后退一个单元可能超出存储边界，需要调整令其指向存储空间中的最后一个单元。
if (q->end < q->stor_begin)
q->end = q->stor_end - 1;
此刻，end就指向了队尾的数据，我们用它来填充输出缓存buf。
*buf = *(q->end);
刚刚我们调整队尾指针end的过程就相当于是将队尾的数据从队列中移除。移除操作可能导致队列为空，此时为end赋值为0，标记空对列。
if (q->begin == q->end) {
q->begin = q->stor_begin;
q->end = 0;
}
最后返回退出。
return DEQUE_NOERR;
}
5. 完
双端队列可以在队首或者队尾插入和删除数据，如果我们只在一端完成插入和删除操作就得到了一个栈，如果再一端插入另一端删除就得到了一个队列。我们还可以任意组合这些操作，具有更宽泛的应用。