隊(duì)列的概念與結(jié)構(gòu)
隊(duì)列是一種特殊的線性結(jié)構(gòu)，數(shù)據(jù)只能在一端插入，數(shù)據(jù)也只能在另一端進(jìn)行刪除。插入數(shù)據(jù)的那一端稱之為隊(duì)尾，插入數(shù)據(jù)的動(dòng)作稱之為入隊(duì)。刪除數(shù)據(jù)的那一端稱之為隊(duì)頭，刪除數(shù)據(jù)的動(dòng)作稱之為出列。隊(duì)列遵守的是FIFO原則（Frist In First Out），即先進(jìn)先出原則。
隊(duì)列具體實(shí)現(xiàn)結(jié)構(gòu)比較靈活，只要遵循FIFO原則即可。順序表的方式實(shí)現(xiàn)，雖然尾插數(shù)據(jù)方便，頭刪的代價(jià)較大，故不推薦。單鏈表的方式實(shí)現(xiàn)，頭刪數(shù)據(jù)方便，只需要添加一個(gè)記錄尾結(jié)點(diǎn)的指針，進(jìn)行尾插數(shù)據(jù)的效率也還可以。所以本篇文章將以單鏈表的方式來實(shí)現(xiàn)隊(duì)列。
隊(duì)列的特點(diǎn)
由于隊(duì)列是FIFO的原則，這就類似于去食堂排隊(duì)打飯，先排隊(duì)的就一定先吃上飯。而隊(duì)尾的就得等先排隊(duì)的打完飯了，才有機(jī)會(huì)吃飯。所以隊(duì)列無論是變?nèi)肓凶兂隽?，還是全部入列后再出列，結(jié)果是一樣的。這和棧的LIFO原則有些許不同。
隊(duì)列的實(shí)現(xiàn)
隊(duì)列的定義
首先，我們需要定義的是鏈?zhǔn)浇Y(jié)構(gòu)的隊(duì)列，即單鏈表為底層實(shí)現(xiàn)的。所以需要定義單鏈表結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)。然后，定義隊(duì)列，隊(duì)列里需要定義兩個(gè)指向單鏈表的指針，一個(gè)是指向單鏈表頭結(jié)點(diǎn)的指針，另一個(gè)則用來保存尾結(jié)點(diǎn)地址的指針。最后，還需定義一個(gè)記錄當(dāng)前隊(duì)列元素個(gè)數(shù)的變量，用于遍歷隊(duì)列和判空。
typedef int QueueDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QueueDataType data;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
int size;
}Queue;
初始化隊(duì)列
首先，斷言判斷一下指針合法性。然后，需要將隊(duì)列內(nèi)兩個(gè)指針變量初始化。最后，將記錄隊(duì)列有效元素個(gè)數(shù)的變量初始化一下。
// 初始化隊(duì)列
void QueueInit(Queue* q)
{
assert(q);
//初始化
q->head = q->tail = NULL;
q->size = 0;
}
隊(duì)列銷毀
首先，斷言一下指針有效性。然后，依次釋放每個(gè)結(jié)點(diǎn)。最后釋放最后一個(gè)結(jié)點(diǎn)時(shí)，把tail和head置空，size置零。
// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
assert(q);
//釋放結(jié)點(diǎn)
while (q->head)
{
QueueNode* next = q->head->next;
if (q->tail != q->head)
{
free(q->head);
q->head = next;
}
else
{
//避免野指針
free(q->head);
q->head=q->tail = NULL;
}
}
//手動(dòng)置零
q->size = 0;
}
隊(duì)列判空
由于在定義隊(duì)列時(shí)，增加了額外的記錄當(dāng)前有效數(shù)據(jù)個(gè)數(shù)的變量，所以這里直接返回該變量與0比較的值即可。
// 檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q)
{
return q->size == 0;
}
數(shù)據(jù)入隊(duì)
首先，依舊斷言判斷指針有效性。其次，就是動(dòng)態(tài)開辟結(jié)點(diǎn)，并對新節(jié)點(diǎn)初始化。然后，進(jìn)行頭插操作，記得第一次插入時(shí)，需要單獨(dú)判斷兩個(gè)指針同時(shí)指向新結(jié)點(diǎn)。最后，記得讓tail指針指向最后一個(gè)結(jié)點(diǎn)和size++。
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QueueDataType data)
{
//斷言判斷指針有效性
assert(q);
//開辟結(jié)點(diǎn)
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
perror("malloc fail\n");
return;
}
newnode->next = NULL;
newnode->data = data;
//插入數(shù)據(jù)
//空隊(duì)列插入數(shù)據(jù)
if (q->head == NULL)
{
q->head = q->tail = newnode;
}
//非空隊(duì)列插入數(shù)據(jù)
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
數(shù)據(jù)出列
首先，當(dāng)隊(duì)列為空時(shí)，不能進(jìn)行刪除操作，所以斷言判斷一下是否為空隊(duì)列。然后，就是頭刪鏈表的操作，需要注意的是當(dāng)只剩一個(gè)結(jié)點(diǎn)時(shí)，對tail進(jìn)行特殊處理避免野指針。最后，就是讓記錄有效元素的size–一下。
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{
assert(q);
//空隊(duì)列無法刪除數(shù)據(jù)
assert(!QueueEmpty(q));
//只有一個(gè)數(shù)據(jù)
if (q->head == q->tail)
{
free(q->head);
q->head = q->tail = NULL;
}
else
{
//先保存下一個(gè)結(jié)點(diǎn)
QueueNode* next = q->head->next;
free(q->head);
q->head = next;
}
//記錄當(dāng)前數(shù)據(jù)個(gè)數(shù)
q->size--;
}
獲取有效數(shù)據(jù)個(gè)數(shù)
由于在定義隊(duì)列時(shí)，定義了一個(gè)記錄當(dāng)前有效元素個(gè)數(shù)的變量，所以這里直接返回該變量當(dāng)前的值即可。
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
獲取隊(duì)頭數(shù)據(jù)
直接返回第一個(gè)結(jié)點(diǎn)的data即可。文章來源：http://www.zghlxwxcb.cn/news/detail-771593.html
// 獲取隊(duì)列頭部元素
QueueDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->head->data;
}
獲取隊(duì)尾數(shù)據(jù)
直接返回tail指針指向的鏈表存放的數(shù)據(jù)即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-771593.html
// 獲取隊(duì)列隊(duì)尾元素
QueueDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
完整代碼
//頭文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QueueDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QueueDataType data;
}QueueNode;
typedef struct Queue
{
struct QueueNode* head;
struct QueueNode* tail;
int size;
}Queue;
// 初始化隊(duì)列
void QueueInit(Queue* q);
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QueueDataType data);
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q);
// 獲取隊(duì)列頭部元素
QueueDataType QueueFront(Queue* q);
// 獲取隊(duì)列隊(duì)尾元素
QueueDataType QueueBack(Queue* q);
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q);
// 檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q);
// 銷毀隊(duì)列
void QueueDestroy(Queue* q);
//源文件
#include"Queue.h"
// 初始化隊(duì)列
void QueueInit(Queue* q)
{
//斷言判斷指針有效性
assert(q);
//初始化
q->head = q->tail = NULL;
q->size = 0;
}
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QueueDataType data)
{
//斷言判斷指針有效性
assert(q);
//開辟結(jié)點(diǎn)
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
perror("malloc fail\n");
return;
}
newnode->next = NULL;
newnode->data = data;
//插入數(shù)據(jù)
//空隊(duì)列插入數(shù)據(jù)
if (q->head == NULL)
{
q->head = q->tail = newnode;
}
//非空隊(duì)列插入數(shù)據(jù)
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{
assert(q);
//空隊(duì)列無法刪除數(shù)據(jù)
assert(!QueueEmpty(q));
//只有一個(gè)數(shù)據(jù)
if (q->head == q->tail)
{
free(q->head);
q->head = q->tail = NULL;
}
else
{
QueueNode* next = q->head->next;
free(q->head);
q->head = next;
}
//記錄當(dāng)前數(shù)據(jù)個(gè)數(shù)
q->size--;
}
// 獲取隊(duì)列頭部元素
QueueDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->head->data;
}
// 獲取隊(duì)列隊(duì)尾元素
QueueDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q)
{
return q->size == 0;
}
// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
assert(q);
//釋放結(jié)點(diǎn)
while (q->head)
{
QueueNode* next = q->head->next;
if (q->tail != q->head)
{
free(q->head);
q->head = next;
}
else
{
//避免野指針
free(q->head);
q->head=q->tail = NULL;
}
}
//手動(dòng)置零
q->size = 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——隊(duì)列（C語言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
