01

—

隊列簡介

隊列是種先進先出的數(shù)據(jù)結(jié)構，有個元素進入隊列稱為入對（enqueue），刪除元素稱為出隊（dequeue），隊列有對頭（head）和對尾（tail），當有元素進入隊列時就放在對尾的位置。

02

—

環(huán)形隊列的實現(xiàn)

要想將元素放入隊列我們必須知道對頭和隊尾，在隊列長度不能無限大的條件下我們還要知道隊列的最大容量，我們還想知道隊列大小，所以隊列內(nèi)部能必須記錄當前元素數(shù)量?，F(xiàn)在我們定義一個結(jié)構體如下用于描述隊列。

#define NAN （0xFFFFFE） typedef struct queue_arr{ int head; int tail; int cap; int size; int *arr; }queue_arr_t;

head是對列頭，tail是對尾，cap記錄隊列的最大容量，size記錄當前隊列大小，arr指針保存一塊內(nèi)存的首地址。下面我們定義隊列操作函數(shù)。

extern void queue_arr_init（queue_arr_t *q， int capacity）; //隊列初始化 extern void enqueue_arr（queue_arr_t *q， int data）; //入隊 extern int dequeue_arr（queue_arr_t *q）; //出隊 extern void queue_arr_destroy（queue_arr_t *q）; //銷毀隊列 extern bool queue_arr_is_full（queue_arr_t *q）; //判斷隊列是否滿 extern bool queue_arr_is_empty（queue_arr_t *q）; //判斷隊列是否為空 extern int queue_arr_length（queue_arr_t *q）; //獲取隊列長度

隊列初始化

void queue_arr_init（queue_arr_t *q， int capacity）{ if（q == NULL || capacity 《= 0）{ return; } q-》head = 0; q-》tail = 0; q-》size = 0; q-》arr = malloc（capacity * sizeof（int））; q-》cap = capacity; }

入隊

void enqueue_arr（queue_arr_t *q， int data）{ if（q == NULL）{ return; } if（queue_arr_is_full（q））{ return; } //循環(huán)重用使用過的內(nèi)存 if（q-》tail 》= q-》cap）{ q-》tail = 0; } q-》arr［q-》tail++］ = data; q-》size++; }

隊列容量有限，在進行入隊前一定對隊列進行判斷是否已滿。

出隊

int dequeue_arr（queue_arr_t *q）{ if（q == NULL）{ return NAN; } if（queue_arr_is_empty（q））{ return NAN; } if（q-》head 》= q-》cap）{ q-》head = 0; } q-》size--; return q-》arr［q-》head++］; }

出隊時一定要對隊列進行判斷是否已空。

判斷隊列是否已滿

bool queue_arr_is_full（queue_arr_t *q）{ if（q == NULL）{ return false; } return q-》size == q-》cap ？ true ： false; }

判斷隊列是否已空

bool queue_arr_is_empty（queue_arr_t *q）{ if（q == NULL）{ return true; } return q-》size == 0 ？ true ： false; }

獲取隊列長度

int queue_arr_length（queue_arr_t *q）{ if（q == NULL）{ return 0; } return q-》size; }

銷毀隊列

void queue_arr_destroy（queue_arr_t *q）{ if（q == NULL）{ return; } if（q-》arr）{ free（q-》arr）; } q-》arr = NULL; q-》tail = 0; q-》head = 0; q-》cap = 0; q-》size = 0; }

03

—

鏈式隊列的實現(xiàn)

為了避免隊列元素的移動我們實現(xiàn)了環(huán)形隊列，但是通過申請一塊內(nèi)存空間實現(xiàn)隊列在隊列大小未知的場景下無法滿足我們不斷加入元素進入隊列的需求，這個時候就需要一種無需知道隊列的最大容量，且能動態(tài)插入數(shù)據(jù)和取輸出的隊列實現(xiàn)。

我們知道鏈表能滿足這樣的需求，那么我們可以采用鏈表的實現(xiàn)方式實現(xiàn)隊列。下面我們分別定義一個結(jié)構體用于描述鏈式隊列和隊列結(jié)點并聲明隊列操作函數(shù)。

typedef struct node{ int data; struct node *next; }node_t; typedef struct queue{ node_t *head; node_t *tail; }queue_t; extern void queue_init（queue_t *q）; //隊列初始化 extern void enqueue（queue_t *q， int data）; //數(shù)據(jù)入隊 extern int dequeue（queue_t *q）; //數(shù)據(jù)出隊列 extern int queue_length（queue_t *q）; //獲取隊列長度 extern void queue_destroy（queue_t *q）; //銷毀隊列

隊列結(jié)點的next指針像單鏈表一樣指向下一個結(jié)點，我們重點關注queue_t的定義，head是隊列頭，tail是對尾，有了對頭和對尾就能快速的從對尾插入數(shù)據(jù)從對頭取出數(shù)據(jù)。

隊列初始化

void queue_init（queue_t *q）{ if（q == NULL）{ return; } q-》head = NULL; q-》tail = NULL; }

入隊

元素每次進入隊列都需要新建一個結(jié)點，為了方便我們定義一個新建結(jié)點函數(shù)new_node，函數(shù)實現(xiàn)如下：

static node_t *new_node（int data）{ node_t *node = （node_t *）malloc（sizeof（node_t））; if（node == NULL）{ return NULL; } node-》next = NULL; node-》data = data; return node; }

入隊函數(shù)實現(xiàn)如下：

void enqueue（queue_t *q， int data）{ if（q == NULL）{ return; } node_t *node = new_node（data）; //新建一個結(jié)點 if（node == NULL）{ return; } if（q-》head == NULL && q-》tail == NULL）{ //首次插入一個結(jié)點 q-》tail = node; q-》head = node; return; } q-》tail-》next = node; q-》tail = node; }

入隊前要進行判斷隊列里是否有結(jié)點，這里通過隊頭和對尾是否為空指針進行判斷，如果隊列里沒有結(jié)點則直接將對頭和隊尾指向插入的結(jié)點，否則結(jié)點則通過隊尾tail獲取到隊列最后的結(jié)點，并將最后結(jié)點的next指針指向新插入的結(jié)點，最后更新隊尾。

出隊

每次從隊列移除一個元素都需要釋放隊列結(jié)點內(nèi)存，為了方便我們定義一個是否結(jié)點內(nèi)存函數(shù)，函數(shù)實現(xiàn)如下：

static void free_node（node_t *node）{ if（node == NULL）{ return; } free（node）; node-》next = NULL; }

出隊函數(shù)實現(xiàn)如下：

int dequeue（queue_t *q）{ if（q == NULL）{ return NAN; } if（q-》head == NULL && q-》tail == NULL）{ return NAN; } node_t *node = q-》head; int data = node-》data; if（q-》head-》next == q-》tail）{ //只有一個結(jié)點 q-》head = NULL; q-》tail = NULL; }else{ //不止一個結(jié)點 q-》head = q-》head-》next; } node-》next = NULL; free_node（node）; return data; }

出隊同樣要判斷隊列里是否有結(jié)點，沒有結(jié)點則返回一個非法值，否則進行判斷是否只有一個結(jié)點，若只有一個結(jié)點則直接返回頭結(jié)點，并將對頭和隊尾指針置為空指針，否則獲取隊列頭結(jié)點并更新對頭指針。

獲取隊列長度

int queue_length（queue_t *q）{ if（q == NULL）{ return 0; } node_t *node = q-》head; if（node == NULL）{ return 0; } int length = 1; while（node ！= q-》tail）{ node = node-》next; length++; } return length; }

獲取隊列長度只要從隊列頭結(jié)點不斷的遍歷隊列，判斷當前結(jié)點是否已到隊列尾部，最后返回隊列長度。

銷毀隊列

void queue_destroy（queue_t *q）{ if（q == NULL）{ return; } node_t *node = q-》head; if（node == NULL）{ return; } node_t *temp = NULL; while（node-》next ！= q-》tail）{ temp = node; node = node-》next; free_node（temp）; temp = NULL; } free_node（node）; q-》tail = NULL; q-》head = NULL; }

04

—

結(jié)果驗證

下面我們寫一個小程序驗證隊列實現(xiàn)是否正確。

#include 《stdio.h》 #include “queue.h” int main（） { queue_t queue; int i = 0; queue_init（&queue）; //隊列初始化 printf（“入隊順序 ”）; for（i = 0; i 《 5; i++）{ printf（“%d ，”， i + 1）; enqueue（&queue， i + 1）; } printf（“ ”）; printf（“隊列長度： %d ”， queue_length（&queue））; printf（“取出隊列一個數(shù)據(jù)：%d ”， dequeue（&queue））; printf（“取出隊列一個數(shù)據(jù)：%d ”， dequeue（&queue））; printf（“隊列長度： %d ”， queue_length（&queue））; printf（“銷毀隊列 ”）; queue_destroy（&queue）; printf（“ ”）; printf（“大小固定的隊列測試 ”）; queue_arr_t queue2; queue_arr_init（&queue2， 6）; printf（“入隊順序 ”）; for（i = 10; i 《 16; i++）{ printf（“%d ，”， i）; enqueue_arr（&queue2， i）; } printf（“ ”）; if（queue_arr_is_full（&queue2））{ printf（“隊列已滿 ”）; }else{ printf（“隊列未滿 ”）; } printf（“取出隊列一個數(shù)據(jù)：%d ”， dequeue_arr（&queue2））; printf（“取出隊列一個數(shù)據(jù)：%d ”， dequeue_arr（&queue2））; if（queue_arr_is_full（&queue2））{ printf（“隊列已滿 ”）; }else{ printf（“隊列未滿 ”）; } printf（“隊列長度是：%d ”， queue_arr_length（&queue2））; printf（“銷毀隊列 ”）; queue_arr_destroy（&queue2）; if（queue_arr_is_empty（&queue2））{ printf（“隊列已空 ”）; }else{ printf（“隊列未空 ”）; } return 0; }

編譯輸出如下：

入隊順序 1 ，2 ，3 ，4 ，5 ， 隊列長度： 5 取出隊列一個數(shù)據(jù)：1 取出隊列一個數(shù)據(jù)：2 隊列長度： 3 銷毀隊列 大小固定的隊列測試 入隊順序 10 ，11 ，12 ，13 ，14 ，15 ， 隊列已滿 取出隊列一個數(shù)據(jù)：10 取出隊列一個數(shù)據(jù)：11 隊列未滿 隊列長度是：4 銷毀隊列 隊列已空

輸出完全正確。

編輯：jq