C語言中隊列的結(jié)構(gòu)和函數(shù)接口的使用示例
更新時間：2023年02月14日 14:32:11 作者：[Pokemon]大貓貓
隊列只允許一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進(jìn)先出FIFO的性質(zhì)；隊列可用數(shù)組和鏈表 的方法實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因為如果使用數(shù)組節(jié)，出隊列時刪去首元素需要將整個數(shù)組前移，效率比較低
一、隊列的結(jié)構(gòu)
隊列：一種操作受限的線性表，只允許在線性表的一端進(jìn)行插入，另一端進(jìn)行刪除，插入的一端稱為隊尾，刪除的一端稱為隊頭
通過 動態(tài)順序表 的實(shí)現(xiàn)，可以發(fā)現(xiàn)在數(shù)組的頭部進(jìn)行插入刪除操作時，需要移動數(shù)據(jù)，效率較低，因此不采用數(shù)組來實(shí)現(xiàn)隊列
但通過 單鏈表 的實(shí)現(xiàn)，可以發(fā)現(xiàn)在對單鏈表進(jìn)行頭插時效率很高，而進(jìn)行尾插時，需要找尾數(shù)據(jù)，較為麻煩，但是可以通過增加一個尾指針的方式來提升效率，因此用單鏈表的頭尾指針來實(shí)現(xiàn)隊列，結(jié)構(gòu)如下：
//隊列的元素類型
typedef int QueueDataType;
//隊列的結(jié)點(diǎn)結(jié)構(gòu)
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QNode;
//隊列結(jié)構(gòu)，需要包含指向鏈表的頭指針和尾指針
//為了求隊列數(shù)據(jù)個數(shù)時，時間復(fù)雜度為 O(1)，這里增加一個 size 變量
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
二、隊列的函數(shù)接口
1. 初始化和銷毀
初始化函數(shù)如下：
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
鏈表的結(jié)點(diǎn)都是動態(tài)開辟的，不用隊列時，應(yīng)當(dāng)銷毀
銷毀函數(shù)如下：
void QueueDestroy(Queue* pq)
{
assert(pq);
//從頭結(jié)點(diǎn)開始銷毀
QNode* cur = pq->head;
while (cur)
{
//保存下一個結(jié)點(diǎn)
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
2. 入隊和出隊
入隊：在隊尾插入元素
入隊函數(shù)如下：
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
//創(chuàng)建新結(jié)點(diǎn)
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
//沒有結(jié)點(diǎn)時，插入元素，需要改變隊列的頭尾指針
//有結(jié)點(diǎn)時，直接鏈接在尾結(jié)點(diǎn)之后，tail 變成新的尾
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
//插入元素后，數(shù)據(jù)個數(shù)需要自增
pq->size++;
}
出隊：刪除隊頭元素
出隊函數(shù)如下：
void QueuePop(Queue* pq)
{
assert(pq);
//沒有元素時，不能刪除，這里直接調(diào)用判空函數(shù)
assert(!QueueEmpty(pq));
//如果只有一個結(jié)點(diǎn)時，需要改變隊列的頭尾指針
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
//刪除元素后，數(shù)據(jù)個數(shù)需要自減
pq->size--;
}
3. 訪問隊頭和隊尾元素
訪問隊頭元素函數(shù)如下：
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
//沒有元素時，不能取隊頭元素，這里直接調(diào)用判空函數(shù)
assert(!QueueEmpty(pq));
return pq->head->data;
}
訪問隊尾元素函數(shù)如下：
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
//沒有元素時，不能取隊尾元素，這里直接調(diào)用判空函數(shù)
assert(!QueueEmpty(pq));
return pq->tail->data;
}
4. 判空和元素個數(shù)
判空函數(shù)如下：
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
元素個數(shù)函數(shù)如下：
size_t QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
到此這篇關(guān)于C語言中隊列的結(jié)構(gòu)和函數(shù)接口的使用示例的文章就介紹到這了,更多相關(guān)C語言隊列結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
常量是固定值，在程序執(zhí)行期間不會改變。這些固定的值，又叫做字面量。常量可以是任何的基本數(shù)據(jù)類型，比如整數(shù)常量、浮點(diǎn)常量、字符常量，或字符串字面值，也有枚舉常量。常量就像是常規(guī)的變量，只不過常量的值在定義后不能進(jìn)行修改2022-04-04
這篇文章主要為大家介紹了C語言指針，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
本篇文章介紹了，在C++中概念重載、覆蓋、隱藏的使用分析說明。需要的朋友參考下2013-05-05
這篇文章主要介紹了C++編輯距離（動態(tài)規(guī)劃），編輯距離是指兩個字符串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)，限免詳細(xì)內(nèi)容，需要的小伙伴可以參考一下2022-01-01
隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（head）進(jìn)行刪除操作，而在表的后端（tail）進(jìn)行插入操作。本文將用C語言實(shí)現(xiàn)隊列，感興趣的可以了解一下2022-06-06
C++中malloc與free、new與delete的詳解與應(yīng)用
今天小編就為大家分享一篇關(guān)于C++中malloc與free、new與delete的詳解與應(yīng)用，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
今天遇到單向鏈表的反轉(zhuǎn)的問題,于是靜下心來好好想了一番。下面這篇文章主要給大家介紹了關(guān)于單鏈表反轉(zhuǎn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02
這篇文章主要為大家詳細(xì)介紹了C語言中字符串的兩種定義方式，小編覺得這篇文章寫的還不錯，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
C++ 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)兩個棧實(shí)現(xiàn)一個隊列
這篇文章主要介紹了詳解C++ 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)兩個棧實(shí)現(xiàn)一個隊列的相關(guān)資料,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了C語言中的文件操作詳解，使用文件可以將數(shù)據(jù)直接存放到電腦的硬盤上，做到了數(shù)據(jù)的持久化2022-07-07