佇列的抽象資料結構
在本文中，我們會實作佇列 (queue)，但內部實作不是用這類教材常見的串列 (linked list)，而是使用陣列 (array)，讀者可以和先前的文章比較一下。其 ADT 如下：
Q is a queue.
sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): sz
sub Peek(Q): data
(Optional) PeekRear(Q): data
sub Enqueue(Q, data): void
sub Dequeue(Q): data我們採用和前文相同的抽象資料結構，故不重覆說明。
佇列的公開界面
以下是佇列的公開界面：
#ifndef QUEUE_H
#define QUEUE_H
#ifndef __cplusplus
#include <stdbool.h>
#endif
typedef struct queue_t queue_t;
#ifdef __cplusplus
extern "C" {
#endif
queue_t * queue_new(void);
void queue_delete(void *self);
bool queue_is_empty(const queue_t *self);
int queue_peek(const queue_t *self);
bool queue_enqueue(queue_t *self, int data);
int queue_dequeue(queue_t *self);
#ifdef __cplusplus
}
#endif
#endif /* QUEUE_H */基本上，公開界面的部分是雷同的，因為我們只是換掉內部實作。
佇列的型態宣告
以陣列實作佇列時，其內部構造如下：
對應上述構造，宣告如下的型態：
typedef struct queue_t queue_t;
struct queue_t {
size_t size;
size_t capacity;
size_t head;
size_t tail;
int *elements;
};在此類別中，有兩個屬性和佇列的大小相關，一個是佇列當下的大小 size，一個是佇列的最大容量 capacity。另外有兩個和佇列頭、尾端位置相關的屬性，由於我們內部以陣列儲存元素，故頭、尾端是索引值而非指標。
佇列的建構函式
在此類別宣告下的建構函式的參考實作如下：
queue_t * queue_new(void)
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return q;
q->size = 0;
/* We start with a small capacity intentionally
to test queue expansion. */
q->capacity = 2;
q->head = 0;
q->tail = 0;
q->elements = malloc(q->capacity * sizeof(int));
if (!(q->elements)) {
free(q);
q = NULL;
return q;
}
return q;
}佇列的解構函式
以下是 C 語言的解構函式：
void queue_delete(void *self)
{
if (!self)
return;
int *elements = ((queue_t *) self)->elements;
if (elements)
free(((queue_t *) self)->elements);
free(self);
}要先釋放佇列內部的陣列後，再釋放佇列物件本身。由於此佇列內部以陣列儲存，是整塊的記憶體，不需使用迴圈。
檢查佇列是否為空
IsEmpty(Q) 的 C 程式碼如下：
bool queue_is_empty(const queue_t *self)
{
assert(self);
return self->size == 0;
}直接檢查 size 屬性是否為零即可。
檢視佇列頭端的資料
Peek(Q) 的 C 程式碼如下：
int queue_peek(const queue_t *self)
{
assert(!queue_is_empty(self));
return self->elements[self->head];
}在本文中，我們用 head 取代指標，指向佇列的頭端所在的位置。
將資料放入佇列
要將資料放入佇列時，先將 tail 移動：
之後再放入新的資料即可：
有些細心的讀者可能會擔心容量爆掉的情境，實際上在放入資料前會視需求擴展容量。
將上述過程 (Enqueue) 寫成 C 程式碼如下：
bool queue_enqueue(queue_t *self, int data)
{
if (!queue_expand(self)) {
return false;
}
if (self->size == 0) {
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;
}一開始要先視需求擴展容量，下文會說明 queue_expand() 部分的程式碼。
在推入佇列時，要考慮目前佇列是否為空，兩者的處理方式不同，否則 tail 指向的位置會差 1，讀者可試著自行追蹤虛擬碼即可了解。
要擴展佇列時，會先建立一個新的陣列，再將原陣列的資料逐一拷貝到新陣列上：
新的容量是原陣列大小的兩倍。
以下是 queue_expand() 部分的 C 程式碼：
static bool queue_expand(queue_t *self)
{
if (self->size < self->capacity) {
return true;
}
int *oldArr = self->elements;
self->capacity = self->size * 2;
int *newArr = malloc(self->capacity * sizeof(int));
if (!newArr) {
return false;
}
size_t sz = 0;
size_t i = self->head;
size_t j = self->head;
while (sz < self->size) {
newArr[i] = oldArr[j];
i = (i + 1) % self->capacity;
j = (j + 1) % self->size;
sz += 1;
}
self->elements = newArr;
self->tail = (self->head + self->size - 1) % self->capacity;
free(oldArr);
return true;
}我們同樣用環狀陣列的手法拷貝元素，要注意 i 和 j 的平移距離不同，因 old_arr 和 new_arr 的大小不同。
將資料移出佇列
要將資料移出佇列時，先移動 head：
其實這樣就完成了。日後新增節點時會自動覆蓋掉該位置的資料：
將上述動作 (Dequeue) 寫成 C 程式碼：
int queue_dequeue(queue_t *self)
{
assert(!queue_is_empty(self));
int popped = self->elements[self->head];
self->head = (self->head + 1) % self->capacity;
self->size -= 1;
return popped;
}由於推出資料時，head 是向後推移，故其值為加 1 而非減 1，同樣要用環狀陣列的手法平移。
在演算法上的效率
根據本文的實作，得到的演算法效率如下：
IsEmpty:O(1)Peek:O(1)Enqueue: amortizedO(1)Dequeue:O(1)
如同先前堆疊的例子，在執行 Enquene 時若陣列有擴張，其效率為 O(n)，但以攤平分析法 (amortized analysis) 來分析可知其效率為 O(1)。