C語(yǔ)言超詳細(xì)講解隊(duì)列的實(shí)現(xiàn)及代碼
前言
隊(duì)列的概念
- 隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out)
- 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾
- 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭
隊(duì)列和前文所學(xué)的棧還是有一定區(qū)別的，隊(duì)列明確指出先進(jìn)先出。假如說(shuō)一個(gè)隊(duì)列的入隊(duì)順序?yàn)锳 B C D，那么出隊(duì)順序一定為A B C D，因?yàn)闊o(wú)論你是在A進(jìn)去再出來(lái)，然后B進(jìn)去再出來(lái)接著CD進(jìn)去再出來(lái)或者類似的，都不會(huì)影響它最終的出隊(duì)順序A B C D。這點(diǎn)和棧還是有區(qū)別的，畢竟棧是后進(jìn)先出。
隊(duì)列的結(jié)構(gòu)
隊(duì)列的應(yīng)用場(chǎng)景
隊(duì)列：
- 公平排隊(duì)
- 廣度優(yōu)先遍歷 ……
棧：
- 解決括號(hào)匹配
- 逆波蘭表達(dá)式求解
- 遞歸改非遞歸 ……
隊(duì)列的實(shí)現(xiàn)
- 在實(shí)現(xiàn)之前，首先得考慮用哪種結(jié)構(gòu)好，是用數(shù)組結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)呢？上文的棧我們使用的是數(shù)組結(jié)構(gòu)，難道隊(duì)列也要用嗎？
- 其實(shí)不然。應(yīng)該使用鏈?zhǔn)浇Y(jié)構(gòu)。前文棧刪除數(shù)據(jù)不需要挪動(dòng)數(shù)據(jù)，使用數(shù)組結(jié)構(gòu)即可滿足需求，而隊(duì)列在刪除數(shù)據(jù)時(shí)需要把后面的數(shù)據(jù)挪到前面，使用鏈?zhǔn)浇Y(jié)構(gòu)非常容易實(shí)現(xiàn)，只需改變節(jié)點(diǎn)指向即可，而數(shù)組結(jié)構(gòu)想要實(shí)現(xiàn)挪動(dòng)數(shù)據(jù)則非常麻煩。綜上，使用鏈?zhǔn)浇Y(jié)構(gòu)是最優(yōu)的。此外，單鏈表即可滿足需求，不需要使用其余較為復(fù)雜的鏈?zhǔn)浇Y(jié)構(gòu)。
創(chuàng)建隊(duì)列結(jié)構(gòu)
思路：
這里要定義兩個(gè)結(jié)構(gòu)體，除了要定義1個(gè)鏈?zhǔn)浇Y(jié)構(gòu)來(lái)記錄各個(gè)節(jié)點(diǎn)外，還要定義一個(gè)結(jié)構(gòu)來(lái)記錄隊(duì)頭和隊(duì)尾。以此方便后續(xù)的隊(duì)尾入數(shù)據(jù)，隊(duì)頭出數(shù)據(jù)。
Queue.h 文件：
//創(chuàng)建隊(duì)列結(jié)構(gòu)
typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類型，本文以int為例
//創(chuàng)建隊(duì)列節(jié)點(diǎn)
typedef struct QueueNode
{
QDataType data; //存儲(chǔ)數(shù)據(jù)
struct QueueNode* next; //記錄下一個(gè)節(jié)點(diǎn)
}QNode;
//保存隊(duì)頭和隊(duì)尾
typedef struct Queue
{
QNode* head; //頭指針
QNode* tail; //尾指針
}Queue;隊(duì)列初始化
思路：
隊(duì)列可以為空，但是管理頭指針和尾指針的結(jié)構(gòu)體不能為空，所以一開(kāi)始就要斷言。其次，在插入數(shù)據(jù)前，隊(duì)列肯定是空的，所以直接把頭指針和尾指針置空即可。
Queue.h 文件：
//初始化隊(duì)列 void QueueInit(Queue* pq);
Queue.c 文件：
//初始化隊(duì)列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}隊(duì)列銷毀
思路：
銷毀隊(duì)列就是把隊(duì)列的每個(gè)數(shù)據(jù)都銷毀掉，那么需要遍歷鏈表進(jìn)行挨個(gè)銷毀free。首先定義一個(gè)cur指針為pq->head，用來(lái)保存第一個(gè)數(shù)據(jù)，遍歷cur，如果不為空，就free。最后把tail和head置空即可。
Queue.h 文件：
//銷毀隊(duì)列 void QueueDestory(Queue* pq);
Queue.c 文件：
//銷毀隊(duì)列
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}入隊(duì)列
思路：
入隊(duì)列其實(shí)很簡(jiǎn)單，只需要尾插即可，首先要新創(chuàng)建一個(gè)節(jié)點(diǎn)來(lái)保存新插入的數(shù)據(jù)。但是在尾插之前要考慮如果一開(kāi)始隊(duì)列沒(méi)有數(shù)據(jù)，為空，那么只需要把head和tail節(jié)點(diǎn)指向新節(jié)點(diǎn)newnode節(jié)點(diǎn)即可。相反的，如果一開(kāi)始就有數(shù)據(jù)，那么只需正常尾插把tail的next指向新節(jié)點(diǎn)newnode，再把newnode賦給tail即可。
Queue.h 文件：
//入隊(duì)列 void QueuePush(Queue* pq, QDataType x);
Queue.c 文件：
//入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//創(chuàng)建一個(gè)新節(jié)點(diǎn)保存數(shù)據(jù)
QNode* newnode = (QNode*)malloc(sizeof(QNode));
//暴力檢測(cè)newnode，因?yàn)閙alloc的都要檢測(cè)
assert(newnode);
newnode->next = NULL;
newnode->data = x;
//如果一開(kāi)始沒(méi)有數(shù)據(jù)，為空的情況
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}出隊(duì)列
思路：
特殊情況：
這里在刪除數(shù)據(jù)時(shí)，首先要考慮特殊情況，當(dāng)刪到只剩一個(gè)數(shù)據(jù)時(shí)，再刪一次，此時(shí)數(shù)據(jù)是沒(méi)了，不過(guò)head為空了，而tail變成野指針了，為了避免此現(xiàn)象的產(chǎn)生，單獨(dú)討論并置空head和tail即可。
一般情況：
此時(shí)只需要定義一個(gè)next指針保存head的下一個(gè)節(jié)點(diǎn)，將head移動(dòng)到next即可，并把舊的head置空。
Queue.h 文件：
//出隊(duì)列 void QueuePop(Queue* pq);
Queue.c 文件：
//出隊(duì)列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail); //tail和head均不能為空
//特殊：當(dāng)刪到head=tail的位置時(shí)
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//一般情況
else
{
//保存head的下一個(gè)節(jié)點(diǎn)
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}隊(duì)列判空
思路：
如果head為空或者tail為空都是判空的條件，直接返回即可。
Queue.h 文件：
//判空 bool QueueEmpty(Queue* pq);
Queue.c 文件：
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}獲取隊(duì)列元素個(gè)數(shù)
思路：
求元素個(gè)數(shù)其實(shí)不難，只需要定義一個(gè)cur指針為第一個(gè)數(shù)據(jù)pq->head，定義變量size來(lái)記錄個(gè)數(shù)。依次遍歷cur，不為空，size就++。這種遍歷的思想不復(fù)雜，但時(shí)間復(fù)雜度達(dá)到O(N)，不是太好，想要O(1)的話可以直接在當(dāng)初定義結(jié)構(gòu)體時(shí)多定義一個(gè)size變量，專門用來(lái)記錄有效元素個(gè)數(shù)，每次入隊(duì)列size++，出隊(duì)列size--。這樣實(shí)現(xiàn)是比較好的，不過(guò)為了封裝成一個(gè)獨(dú)立模塊，還是采用遍歷的方式。如下：
Queue.h 文件：
//獲取有效元素個(gè)數(shù) size_t QueueSize(Queue* pq);
Queue.c 文件：
//獲取有效元素個(gè)數(shù)
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}獲取隊(duì)列頭部元素
思路：
首先要斷言頭部不能為空，如果頭部都為空了，那還怎么能獲得頭部元素，其次直接返回頭部head的數(shù)據(jù)即可。
Queue.h 文件：
//獲取隊(duì)頭元素 QDataType QueueFront(Queue* pq);
Queue.c 文件：
//獲取隊(duì)頭元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head); //頭部不能為空
return pq->head->data;
}獲取隊(duì)列尾部元素
思路：
有了獲取隊(duì)頭元素的經(jīng)驗(yàn)，隊(duì)尾就更簡(jiǎn)單了，把head換位tail即可，結(jié)構(gòu)與上文一樣。
Queue.h 文件：
//獲取隊(duì)尾元素 QDataType QueueBack(Queue* pq);
Queue.c 文件：
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail); //尾部不能為空
return pq->tail->data;
}總代碼
Queue.h 文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//創(chuàng)建隊(duì)列結(jié)構(gòu)
typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類型，本文以int為例
//創(chuàng)建隊(duì)列節(jié)點(diǎn)
typedef struct QueueNode
{
QDataType data; //存儲(chǔ)數(shù)據(jù)
struct QueueNode* next; //記錄下一個(gè)節(jié)點(diǎn)
}QNode;
//保存隊(duì)頭和隊(duì)尾
typedef struct Queue
{
QNode* head; //頭指針
QNode* tail; //尾指針
}Queue;
//初始化隊(duì)列
void QueueInit(Queue* pq);
//銷毀隊(duì)列
void QueueDestory(Queue* pq);
//入隊(duì)列
void QueuePush(Queue* pq, QDataType x);
//出隊(duì)列
void QueuePop(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//獲取有效元素個(gè)數(shù)
size_t QueueSize(Queue* pq);
//獲取隊(duì)頭元素
QDataType QueueFront(Queue* pq);
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq);Queue.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化隊(duì)列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//銷毀隊(duì)列
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//創(chuàng)建一個(gè)新節(jié)點(diǎn)保存數(shù)據(jù)
QNode* newnode = (QNode*)malloc(sizeof(QNode));
//暴力檢測(cè)newnode，因?yàn)閙alloc的都要檢測(cè)
assert(newnode);
newnode->next = NULL;
newnode->data = x;
//如果一開(kāi)始沒(méi)有數(shù)據(jù)，為空的情況
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出隊(duì)列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail); //tail和head均不能為空
//特殊：當(dāng)刪到head=tail的位置時(shí)
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//一般情況
else
{
//保存head的下一個(gè)節(jié)點(diǎn)
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//獲取有效元素個(gè)數(shù)
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
//獲取隊(duì)頭元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head); //頭部不能為空
return pq->head->data;
}
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail); //尾部不能為空
return pq->tail->data;
}Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
Queue q;
QueueInit(&q);
//插入數(shù)據(jù)
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//打印
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
}
int main()
{
TestQueue();
return 0;
}到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解隊(duì)列的實(shí)現(xiàn)及代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言 隊(duì)列的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言數(shù)組和指針,內(nèi)存之間的關(guān)系
這篇文章主要介紹了C語(yǔ)言數(shù)組和指針,內(nèi)存之間的關(guān)系，首先論證一維數(shù)組和一級(jí)指針之前的關(guān)系，我們常常使用一級(jí)指針指針的方式訪問(wèn)一維數(shù)組，只有對(duì)內(nèi)存的理解到位才能理解它們直接的關(guān)系。需要的小伙伴可以參考一下2022-02-02
Qt無(wú)邊框窗口拖拽和陰影的實(shí)現(xiàn)方法
這篇文章主要給大家介紹了關(guān)于Qt無(wú)邊框窗口拖拽和陰影的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要為大家介紹了C/C++的內(nèi)存管理，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01
這篇文章主要為大家詳細(xì)介紹了C++發(fā)送郵件的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易學(xué)生成績(jī)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易學(xué)生成績(jī)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
Windows 環(huán)境下使用 Qt 連接 MySQL
這篇文章主要介紹了Windows 環(huán)境下使用 Qt 連接 MySQL的相關(guān)資料,需要的朋友可以參考下2017-07-07
第一種方法，思路：利用指針的強(qiáng)制類型轉(zhuǎn)換。第二種方法，思路：利用共用體所有數(shù)據(jù)都從同一地址開(kāi)始存儲(chǔ)。2013-03-03
在c++Template中很多地方都用到了typename與class這兩個(gè)關(guān)鍵字，而且好像可以替換，是不是這兩個(gè)關(guān)鍵字完全一樣呢?下面這篇文章主要給大家介紹了關(guān)于c++模板中class與typename的相關(guān)資料，需要的朋友可以參考下。2017-07-07
C++實(shí)現(xiàn)圖的遍歷算法(DFS,BFS)的示例代碼
本文給大家?guī)?lái)的是圖遍歷的算法，DFS(深度優(yōu)先遍歷)，BFS(廣度優(yōu)先遍歷)。這兩個(gè)算法是比較重要和常用的算法，但是在圖中的實(shí)現(xiàn)只是最基本的操作，快跟隨小編一起學(xué)習(xí)一下吧2022-07-07
C++實(shí)現(xiàn)數(shù)組中元素組合出最大值
這篇文章主要介紹了C++實(shí)現(xiàn)數(shù)組中元素組合出最大值，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-05-05