雙向佇列的抽象資料結構
在本文中，我們仍然實作雙向佇列，但內部改以陣列來實作。
以下是此雙向佇列的抽象資料結構：
Q is a deque.
sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): sz
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基本上抽象資料結構是相同的，故不重覆說明。
雙向佇列的公開界面
以下是雙向佇列的公開界面：
#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 */基本上，和前一篇文章的雙向佇列的公開界面雷同，因為我們只抽換掉內部實作。
雙向佇列的型態宣告
以陣列為基礎的雙向佇列的圖示如下：
以陣列為基礎的類別宣告的 C 程式碼如下：
typedef struct deque deque_t;
struct deque_t {
size_t size;
size_t capacity;
size_t head;
size_t tail;
int *elements;
};雙向佇列的建構函式
以 C 語言實作建構函式如下：
deque_t * deque_new(void)
{
deque_t *dq = malloc(sizeof(deque_t));
if (!dq)
return dq;
dq->size = 0;
dq->capacity = 2;
dq->head = 0;
dq->tail = 0;
dq->elements = malloc(dq->capacity * sizeof(int));
if (!(dq->elements)) {
free(dq);
dq = NULL;
return dq;
}
return dq;
}一開始的 capacity 只要大於等於 2 即可；一般使用下可設 16，此處故意設 2 是為了看佇列擴張時是否會引發錯誤。
雙向佇列的解構函式
以下是 C 語言的雙向佇列解構函式：
void deque_delete(void *self)
{
if (!self) {
return;
}
int *elements = ((deque_t *) self)->elements;
if (elements) {
free(((deque_t *) self)->elements);
}
free(self);
}先釋放內部陣列後，再釋放佇列物件本身。
確認雙向佇列是否為空
IsEmpty(Q) 的 C 程式碼如下：
bool deque_is_empty(const deque_t *self)
{
assert(self);
return self->size <= 0;
}在我們的實作中，會儲存佇列大小的資訊，要檢查佇列是否為空時檢查此屬性即可。
檢視雙向佇列頭端的資料
PeekFront(Q) 的 C 程式碼如下：
int deque_peek_front(const deque_t *self)
{
assert(!deque_is_empty(self));
return self->elements[self->head];
}我們的 head 以數字做為索引值 (index value)，用來取代指標。
檢視雙向佇列尾端的資料
PeekRear(Q) 的虛擬碼如下：
int deque_peek_rear(const deque_t *self)
{
assert(!deque_is_empty(self));
return self->elements[self->tail];
}和 PeekFront(Q) 類似，以數字做為索引來取代指標。
將資料推入雙向佇列的尾端
要將資料推入雙向佇列尾端前，要先移動 tail，如下圖：
接著將資料寫入即可：
Push (或 PushRear) 的 C 程式碼如下：
bool deque_push(deque_t *self, int data)
{
if (!deque_extend(self)) {
return false;
}
if (deque_is_empty(self)) {
self->elements[self->tail] = data;
self->size += 1;
return true;
}
self->tail = (self->tail + 1) % self->capacity;
self->elements[self->tail] = data;
self->size += 1;
return true;
}一開始要視需求擴張雙向佇列，我們會在下文介紹 deque_extend() 函式的實作。
要注意佇列為空和非空時的處理方法不同，佇列為空時，索引值不會跳動，但佇列大小會加 1，之後則索引值和佇列大小皆會加 1。
擴張雙向佇列內部的陣列的原理是建立一個新的陣列後，將資料逐一拷貝到新的陣列上。如下圖：
一般會把新的陣列的最大容量設為原本陣列的大小的兩倍。
deque_extend() 部分的 C 程式碼如下：
static bool deque_extend(deque_t *self)
{
if (self->size < self->capacity) {
return true;
}
int *old_arr = self->elements;
self->capacity = self->size * 2;
int *new_arr = malloc(self->capacity * sizeof(int));
if (!new_arr) {
return false;
}
size_t sz = 0;
size_t i = self->head;
size_t j = self->head;
while (sz < self->size) {
new_arr[i] = old_arr[j];
i = (i + 1) % self->capacity;
j = (j + 1) % self->size;
sz += 1;
}
self->elements = new_arr;
free(old_arr);
return true;
}重點在佇列擴張時，新的內部陣列的大小是舊的內部陣列的兩倍大，處理索引值的分母相異。
將資料推入雙向佇列的頭端
若要將資料推入頭端，先移動 head。如下圖：
之後再將資料寫入即可。如下圖：
以下是 Unshift(Q) (或 PushFront(Q)) 的虛擬碼：
bool deque_unshift(deque_t *self, int data)
{
if (!deque_extend(self))
return false;
if (deque_is_empty(self)) {
self->elements[self->head] = data;
}
else {
self->head = self->head == 0 ? self->capacity - 1 : self->head - 1;
self->elements[self->head] = data;
}
self->size += 1;
return true;
}雖然佇列大小變大，但頭端是往回走，故要減 1 而非加 1，同樣要注意索引值為 0 時的處理方法。
將資料從雙向佇列尾端推出
將尾端資料拷貝出來後，移動 tail。如下圖：
其實在移動完 tail 後，整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖：
以下是 Pop(Q) (或 PopRear(Q)) 的虛擬碼：
int deque_pop(deque_t *self)
{
assert(!deque_is_empty(self));
int popped = self->elements[self->tail];
self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
self->size -= 1;
return popped;
}由於索引值不能為負，注意當索引值為 0 時的處理方式。
將資料從雙向佇列頭端推出
將頭端資料拷貝出來後，移動 head。如下圖：
其實在移動完 head 後，整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖：
以下是 Shift(Q) (或 PopFront(Q)) 的虛擬碼：
int deque_shift(deque_t *self)
{
assert(!deque_is_empty(self));
int popped = self->elements[self->head];
self->head = (self->head + 1) % self->capacity;
self->size -= 1;
return popped;
}雖然佇列大小變小，但索引是往後推，故索引值是加 1 而非減 1。
在演算法上的效率
此範例程式在演算法上的效率如下：
IsEmpty(Q)：O(1)PeekFront(Q)：O(1)PeekRear(Q)：O(1)Push(Q, data)：amortizedO(1)Unshift(Q, data)：amortizedO(1)Pop(Q)：O(1)Shift(Q)：O(1)
佇列在擴張時，其效率為 O(n)，若未擴張，其效率為 O(1)；經攤平分析法 (amortized analysis) 可知其攤平後的效率為 O(1)。