佇列的抽象資料結構
佇列 (queue) 是另一種受限制的線性資料結構。其操作方式為從尾端推入，從頭端推出，是一種 FIFO (First-In, First-Out) 的資料結構。在現實生活中，佇列就像是在大賣場排隊結帳的人，先排隊的人可以先結帳。本文以串列實作佇列。
以下是佇列的抽象資料結構：
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由此抽象資料結構可知，佇列至少有以下公開行為：
IsEmpty(Q)：確認佇列是否為空Peek(Q)：檢視佇列頭端的資料，不改變佇列大小Enqueue(Q, data)：從佇列尾端推入資料，佇列長度加 1Dequeue(Q)：從佇列頭端推出資料，佇列長度減 1
以下方法是選擇性的：
IsFull(Q)：檢查佇列是否已滿Size(Q)：回傳佇列的大小PeekRear(Q)：存取佇列尾端的資料，不改變佇列大小
佇列的公開界面
以下是佇列的公開界面：
#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 */除了佇列的標準操作外，這個佇列沒什麼額外的操作，算是中規中矩的佇列。
佇列的型態宣告
如同其他的串列結構，我們會用輔助性的 node_t 類別來儲存資料：
typedef struct node_t node_t;
struct node_t {
int data;
node_t *prev;
node_t *next;
};有內部節點後就可以宣告佇列型態：
typedef struct queue_t queue_t;
struct queue_t {
node_t *head;
node_t *tail;
};佇列的建構函式
以下是以 C 程式碼實作的建構函式：
queue_t * queue_new(void)
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return q;
}
q->head = NULL;
q->tail = NULL;
return q;
}佇列的解構函式
為了要釋放佇列的內部節點，我們需要額外的兩個指標。curr 一開始指向內部節點的頭端，而 temp 是暫存值，指向 curr 所在的節點：
當我們把 curr 移往下一個節點時，就可以把 temp 所在的節點釋放掉：
重覆這個動作，就可以把所有的節點釋放掉。我們會把這個動作寫在迴圈裡，用來自動執行。
將上述動作寫到以下解構函式中，用來釋放記憶體：
void queue_delete(void *self)
{
if (!self)
return;
node_t *curr = ((queue_t *) self)->head;
while (curr) {
node_t *temp = curr;
curr = curr->next;
free(temp);
}
free(self);
}要先釋放佇列的內部節點，再釋放佇列物件本身。
確認佇列是否為空
以下是 IsEmpty 的 C 程式碼：
bool queue_is_empty(const queue_t *self)
{
assert(self);
return !(self->head) ? true : false;
}我們的做法是檢查頭端的指標是否為空。如果在類別中有存放佇列大小的欄位，也可用該欄位檢查佇列大小。
檢視佇列頭端的資料
以下是 Peek 的 C 程式碼：
int queue_peek(const queue_t *self)
{
assert(!queue_is_empty(self));
return self->head->data;
}在我們的實作中，我們會確認佇列不為空，之後直接存取頭端節點的資料即可。
將資料放入佇列
要將資料放入節點時，先建立新的資料節點 node，將 tail 節點和其相接：
再將 tail 重新把向 node 節點即可：
將上述動作 (Enqueue) 以 C 語言實作如下：
bool queue_enqueue(queue_t *self, int data)
{
assert(self);
node_t *node = node_new(data);
if (!node) {
return false;
}
if (!(self->head)) {
self->head = node;
self->tail = node;
return true;
}
self->tail->next = node;
node->prev = self->tail;
self->tail = node;
return true;
}在推入資料時，要考慮佇列是否為空，兩個情境的處理方式相異。
有關 node_new 的部分可以參考以下程式碼：
static node_t * node_new(int data)
{
node_t *node = malloc(sizeof(node_t));
if (!node)
return node;
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}將資料移出佇列
要將資料節點移出佇列時，需要使用額外的指標 curr，該指標指向 head 所在的節點：
將 head 移往下一個節點後，就可以釋放 curr 所在的節點：
將上述動作 (Dequeue) 寫成 C 程式碼如下：
int queue_dequeue(queue_t *self)
{
assert(!queue_is_empty(self));
int popped = self->head->data;
if (self->head == self->tail) {
free(self->head);
self->head = NULL;
self->tail = NULL;
}
else {
node_t *curr = self->head;
self->head = curr->next;
free(curr);
}
return popped;
}將資料推出佇列時，有三個情境：(1) 佇列為空，(2) 佇列頭端和尾端指向同一個節點，(3) 佇列包含多個節點。本範例排除情境 (1)，根據情境 (2) 或 (3) 給予相對應的處理。
在演算法上的效率
根據本文的實作得到的演算法上的效率如下：
IsEmpty(Q):O(1)Peek(Q):O(1)Enqueue(Q, data):O(1)Dequeue(Q):O(1)