雙向佇列的抽象資料結構
雖然雙向佇列 (deque) 仍為受限制的線性資料結構，比起佇列，雙向佇列比較靈活一些，因為雙向佇列可以同時從頭端或尾端推入或推出資料。本文會以連結串列 (linked list) 實作雙向佇列。
雙向佇列的抽象資料結構如下：
Q is a deque.
sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): size >= 0
sub PeekFront(Q): data
sub PeekRear(Q): data
sub Push(Q, data): void
sub Pop(Q): data
sub Unshift(Q, data): void
sub Shift(Q): data由此抽象資料結構可知，雙向佇列至少有以下行為：
IsEmpty：檢查雙向佇列是否為空PeekFront：存取雙向佇列頭端的資料，不改變其大小PeekRear：存取雙向佇列尾端的資料，不改變其大小Push或PushRear：將資料由頭端推入雙向佇列，其大小加 1Pop或PopRear：將資料由頭端推出雙向佇列，其大小減 1Unshift或PushFront：將資料由尾端推入雙向佇列，其大小加 1Shift或PopFront：將資料由尾端推出雙向佇列，其大小減 1
以下行為則是選擇性的：
IsFull：檢查雙向佇列是否已滿Size：回傳該雙向佇列的大小
雙向佇列的公開界面：
以下是雙向佇列的公開界面：
#ifndef DEQUE_H
#define DEQUE_H
#ifndef __cplusplus
#include <stdbool.h>
#endif
typedef struct deque_t deque_t;
#ifdef __cplusplus
extern "C" {
#endif
deque_t * deque_new(void);
void deque_delete(void *self);
bool deque_is_empty(const deque_t *self);
int deque_peek_front(const deque_t *self);
int deque_peek_rear(const deque_t *self);
bool deque_push(deque_t *self, int data);
int deque_pop(deque_t *self);
bool deque_unshift(deque_t *self, int data);
int deque_shift(deque_t *self);
#ifdef __cplusplus
}
#endif
#endif /* DEQUE_H */雙向佇列可用的操作會比堆疊和佇列多，這是根據雙向佇列的抽象資料結構而來。
雙向佇列的型態宣告
由於我們使用串列實作雙向佇列，內部需要使用節點型態：
typedef struct node_t node_t;
struct node_t {
int data;
node_t *prev;
node_t *next;
};有節點型態後就可以宣告雙向佇列型態：
typedef struct deque_t deque_t;
struct deque_t {
node_t *head;
node_t *tail;
};雙向佇列的建構函式
根據上述宣告實作建構函式如下：
deque_t * deque_new(void)
{
deque_t *dq = \
(deque_t *) malloc(sizeof(deque_t));
if (!dq)
return dq;
dq->head = NULL;
dq->tail = NULL;
return dq;
}雙向佇列的解構函式
若要釋放雙向佇列的記憶體，會用到兩個額外的指標 curr 和 temp。curr 一開始指向內部節點的頭端，temp 指向 curr 所在的節點：
將 curr 移往下一個節點後，即可釋放 temp 所在的節點：
反覆這個過程，就可以釋放所有的內部節點。實際上，會把這個過程寫在迴圈中，以利重覆執行。
將上述動作以 C 語言寫成解構函式：
void deque_delete(void *self)
{
if (!self)
return;
node_t *curr = ((deque_t *) self)->head;
while (curr) {
node_t *temp = curr;
curr = curr->next;
free(temp);
}
free(self);
}要先逐一走訪內部節點並釋放後，再釋放佇列物件本身。
確認雙向佇列是否為空
IsEmpty(Q) 的 C 程式碼如下：
bool deque_is_empty(const deque_t *self)
{
assert(self);
return !(self->head) ? true : false;
}我們用指向頭端的指標是否為空來檢查佇列是否為空。
檢視雙向佇列頭端的資料
PeekFront(Q) 的 C 程式碼如下：
int deque_peek_front(const deque_t *self)
{
assert(!deque_is_empty(self));
return self->head->data;
}只要確認佇列不為空之後，直接存取頭端節點的資料即可。
檢視雙向佇列尾端的資料
PeekRear(Q) 也是採取類似的策略：
int deque_peek_rear(const deque_t *self)
{
assert(!deque_is_empty(self));
return self->tail->data;
}確認佇列不為空之後回傳尾端的資料即可。
從雙向佇列的尾端推入資料
要從尾端放入節點時，先將新節點 node 和 tail 節點相互連結：
接著再將指標 tail 重設到 node 即可：
將上述動作 (Push(Q) 或 PushRear(Q)) 寫成 C 程式如下：
bool deque_push(deque_t *self, int data) /* 1 */
{ /* 2 */
node_t *node = node_new(data); /* 3 */
if (!node) /* 4 */
return false; /* 5 */
if (!(self->tail)) { /* 6 */
self->head = node; /* 7 */
self->tail = node; /* 8 */
} /* 9 */
else { /* 10 */
self->tail->next = node; /* 11 */
node->prev = self->tail; /* 12 */
self->tail = node; /* 13 */
} /* 14 */
return true; /* 15 */
} /* 16 */在推入資料時，要考慮佇列是否為空，兩者處理方式不同。
第 6 行至第 9 行代表 deque 為空的情境，這時候頭端和尾端都會指向同一個節點。
第 10 行至第 14 行代表 deque 不為空的情境，這時候將節點推向尾端即可。
node_new 的部分可參考以下程式碼：
static node_t * node_new(int data)
{
node_t *node = \
(node_t *) malloc(sizeof(node_t));
if (!node)
return node;
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}從雙向佇列的頭端推入資料
要從頭端放入節點時，先將新節點 node 和 head 節點相互連結：
接著再將指標 head 重設到 node 即可：
上述動作 (Unshift 或 PushFront) 是從頭端推入資料，和前一節所介紹的 Push 採取類似的策略：
bool deque_unshift(deque_t *self, int data) /* 1 */
{ /* 2 */
node_t *node = node_new(data); /* 3 */
if (!node) /* 4 */
return false; /* 5 */
if (!(self->head)) { /* 6 */
self->head = node; /* 7 */
self->tail = node; /* 8 */
} /* 9 */
else { /* 10 */
node->next = self->head; /* 11 */
self->head->prev = node; /* 12 */
self->head = node; /* 13 */
} /* 14 */
return true; /* 15 */
} /* 16 */第 6 行至第 9 行代表 deque 為空的情境，這時候頭端和尾端都會指向相同的節點。
第 10 行至第 14 行代表 deque 不為空的情境，這時候將節點推入頭端即可。
這一節的實作和上一節的相似，讀者可相互比較。
從雙向佇列的尾端取出資料
若要從雙向佇列的尾端取出資料，要用一個額外的指標 curr，一開始先將 curr 指向 tail 節點：
將指標 tail 移往前一個節點後，就可以釋放指標 curr 所在的節點：
上述動作 (Pop 或 PopRear) 的 C 程式碼如下：
int deque_pop(deque_t *self) /* 1 */
{ /* 2 */
assert(!deque_is_empty(self)); /* 3 */
int popped = self->tail->data; /* 4 */
if (self->head == self->tail) { /* 5 */
free(self->tail); /* 6 */
self->head = NULL; /* 7 */
self->tail = NULL; /* 8 */
} /* 9 */
else { /* 10 */
node_t *curr = self->tail; /* 11 */
self->tail = curr->prev; /* 12 */
free(curr); /* 13 */
self->tail->next = NULL; /* 14 */
} /* 15 */
return popped; /* 16 */
} /* 17 */推出佇列時，要考慮三種情境：(1) 佇列為空，(2) 佇列僅存單一節點，(3) 佇列有多個節點。本例在一開始時排除情境 (1)，在情境 (2) 或 (3) 給予不同的處理方式。
當 deque 為空時，試圖從 deque 推出資料是不合法的 (invalid) 操作。所以我們在第 3 行中排除了 deque 為空的情境。
第 5 行至第 9 行代表 deque 只剩單一節點的情境，這時候將該節點釋放掉，頭端和尾端重新指向空指標。
第 10 行至第 15 行代表 deque 仍有多個節點的情境，這時候將尾端重新指向原節點的前一個節點，然後釋放掉尾端的節點。
從雙向佇列的頭端移出資料
若要從雙向佇列的頭端取出資料，要用一個額外的指標 curr，一開始先將 curr 指向 head 節點：
將指標 head 移往下一個節點後，就可以釋放指標 curr 所在的節點：
Shift(Q) (或 PopFront(Q)) 同樣也要考慮三種不同的情境：
int deque_shift(deque_t *self) /* 1 */
{ /* 2 */
assert(!deque_is_empty(self)); /* 3 */
int popped = self->head->data; /* 4 */
if (self->head == self->tail) { /* 5 */
free(self->head); /* 6 */
self->head = NULL; /* 7 */
self->tail = NULL; /* 8 */
} /* 9 */
else { /* 10 */
node_t *curr = self->head; /* 11 */
self->head = curr->next; /* 12 */
free(curr); /* 13 */
self->head->prev = NULL; /* 14 */
} /* 15 */
return popped; /* 16 */
} /* 17 */當 deque 為空時，試圖從 deque 推出資料是非法的 (invalid)，所以我們在第 3 行排除這個情境。
第 5 行至第 9 行代表 deque 僅存單一節點的情境。這時候會釋放掉該節點，然後將頭端和尾端重新指向空指標。
第 10 行至第 15 行代表 deque 還有多個節點的情境。這時候會將頭端重新指向原節點的次一個節點，然後釋放掉原節點。
本節的實作和上一節相似，讀者可將兩者相互比較。
在演算法上的效率
根據本範例的實作，可得到在演算法上的效率如下：
IsEmpty(Q)：O(1)PeekFront(Q)：O(1)PeekRear(Q)：O(1)Push(Q, data)(或PushRear)：O(1)Unshift(Q, data)(或PushFront)：O(1)Pop(Q)(或PopRear)：O(1)Shift(Q)(或PopFront)：O(1)