01

—

隊(duì)列簡(jiǎn)介

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

02

—

環(huán)形隊(duì)列的實(shí)現(xiàn)

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

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

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

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

隊(duì)列初始化

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

入隊(duì)

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

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

出隊(duì)

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

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

判斷隊(duì)列是否已滿

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

判斷隊(duì)列是否已空

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

獲取隊(duì)列長(zhǎng)度

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

銷毀隊(duì)列

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)疥?duì)列的實(shí)現(xiàn)

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

我們知道鏈表能滿足這樣的需求，那么我們可以采用鏈表的實(shí)現(xiàn)方式實(shí)現(xiàn)隊(duì)列。下面我們分別定義一個(gè)結(jié)構(gòu)體用于描述鏈?zhǔn)疥?duì)列和隊(duì)列結(jié)點(diǎn)并聲明隊(duì)列操作函數(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）; //隊(duì)列初始化 extern void enqueue（queue_t *q， int data）; //數(shù)據(jù)入隊(duì) extern int dequeue（queue_t *q）; //數(shù)據(jù)出隊(duì)列 extern int queue_length（queue_t *q）; //獲取隊(duì)列長(zhǎng)度 extern void queue_destroy（queue_t *q）; //銷毀隊(duì)列

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

隊(duì)列初始化

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

入隊(duì)

元素每次進(jìn)入隊(duì)列都需要新建一個(gè)結(jié)點(diǎn)，為了方便我們定義一個(gè)新建結(jié)點(diǎn)函數(shù)new_node，函數(shù)實(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; }

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

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

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

出隊(duì)

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

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

出隊(duì)函數(shù)實(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）{ //只有一個(gè)結(jié)點(diǎn) q-》head = NULL; q-》tail = NULL; }else{ //不止一個(gè)結(jié)點(diǎn) q-》head = q-》head-》next; } node-》next = NULL; free_node（node）; return data; }

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

獲取隊(duì)列長(zhǎng)度

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

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

銷毀隊(duì)列

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é)果驗(yàn)證

下面我們寫一個(gè)小程序驗(yàn)證隊(duì)列實(shí)現(xiàn)是否正確。

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

編譯輸出如下：

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

輸出完全正確。

編輯：jq