深度解析數(shù)據(jù)結(jié)構(gòu)與算法篇之隊列及環(huán)形隊列的實現(xiàn)

01

—

隊列簡介

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

02

—

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

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

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

head是對列頭，tail是對尾，cap記錄隊列的最大容量，size記錄當(dāng)前隊列大小，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++; }

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

出隊

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++］; }

出隊時一定要對隊列進(jìn)行判斷是否已空。

判斷隊列是否已滿

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

—

鏈?zhǔn)疥犃械膶崿F(xiàn)

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

我們知道鏈表能滿足這樣的需求，那么我們可以采用鏈表的實現(xiàn)方式實現(xiàn)隊列。下面我們分別定義一個結(jié)構(gòu)體用于描述鏈?zhǔn)疥犃泻完犃薪Y(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é)點，我們重點關(guān)注queue_t的定義，head是隊列頭，tail是對尾，有了對頭和對尾就能快速的從對尾插入數(shù)據(jù)從對頭取出數(shù)據(jù)。

隊列初始化

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

入隊

元素每次進(jìn)入隊列都需要新建一個結(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; }

入隊前要進(jìn)行判斷隊列里是否有結(jié)點，這里通過隊頭和對尾是否為空指針進(jìn)行判斷，如果隊列里沒有結(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é)點則返回一個非法值，否則進(jìn)行判斷是否只有一個結(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é)點不斷的遍歷隊列，判斷當(dāng)前結(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