C語言實(shí)現(xiàn)隊(duì)列的示例詳解
前言
前一段時(shí)間，我們?cè)囍肅語言實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的順序表，單鏈表，雙向循環(huán)鏈表，棧。今天我們?cè)儆肅語言來實(shí)現(xiàn)另一種特殊的線性結(jié)構(gòu)：隊(duì)列
一. 什么是隊(duì)列
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（head）進(jìn)行刪除操作，而在表的后端（tail）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
這個(gè)隊(duì)列就可以理解成我們平時(shí)的排隊(duì)，先進(jìn)入的先出去，與我們之前實(shí)現(xiàn)的先進(jìn)后出的棧相反。
二. 使用什么來實(shí)現(xiàn)棧
再把上次的圖拿出來，我們看看是用線性表來實(shí)現(xiàn)隊(duì)列，還是鏈表比較好
| 不同點(diǎn) | 順序表 | 鏈表 |
|---|---|---|
| 存儲(chǔ)空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機(jī)訪問 | 可以直接訪問任何元素 | 必須從頭節(jié)點(diǎn)開始往后尋找 |
| 任意位置插入或刪除元素 | 要搬移其他的元素，效率低。 | 只需要修改節(jié)點(diǎn)的指針指向，效率高 |
| 插入 | 動(dòng)態(tài)順序表，當(dāng)空間不夠時(shí)需要擴(kuò)容 | 無容量概念，需要就申請(qǐng)，不用就釋放 |
| 應(yīng)用場景 | 元素高效存儲(chǔ)，并且需要頻繁訪問 | 需要在任意位置插入或者刪除頻繁 |
綜合上表來看，我覺得鏈表較為方便，原因如下：
1.隊(duì)列有多少元素不確定，鏈表可以做到需要就申請(qǐng)，不用就釋放，較為方便
2.隊(duì)列是先進(jìn)先出，順序固定，不需要隨機(jī)訪問。
三. 隊(duì)列的實(shí)現(xiàn)
3.1頭文件
1.包含的標(biāo)準(zhǔn)庫
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h>
2.定義結(jié)構(gòu)體
typedef int QDateType;//隊(duì)列存儲(chǔ)數(shù)據(jù)類型
typedef struct QueueNode //隊(duì)列元素節(jié)點(diǎn)
{
QDateType val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue //隊(duì)列
{
QueueNode* head;
QueueNode* tail;
}Queue;
3.函數(shù)聲明
void QueueInti(Queue* pq); // 隊(duì)列初始化 void QueueDestory(Queue* pq); // 隊(duì)列的銷毀 void QueuePush(Queue* pq, QDateType x); // 入隊(duì) void QueuePop(Queue* pq); // 出隊(duì) QDateType QueueFront(Queue* pq); // 取出隊(duì)首元素 int QueueSize(Queue* pq); // 求隊(duì)列的長度 bool QueueEmpty(Queue* pq); // 判斷隊(duì)是否為空
3.2 函數(shù)的實(shí)現(xiàn)
1.隊(duì)列的初始化
將頭尾置為空指針即可。
void QueueInti(Queue* pq)
{
assert(pq); //防止pq為空指針
pq->head = pq->tail = NULL;
}
2.隊(duì)列的銷毀
遍歷隊(duì)列元素，然后將每一個(gè)元素釋放。
void QueueDestory(Queue* pq)
{
assert(pq); //防止pq為空指針
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->tail = pq->head = NULL;
}
3.入隊(duì)
對(duì)于入隊(duì)，我們首先需要去開辟一個(gè)新的節(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)，然后將這個(gè)節(jié)點(diǎn)加入到tail后即可。此時(shí)我們就要分別考慮。
1.如果為空隊(duì)列，那么我們不僅要改變tail，還要改變head的值
2.如果不為空隊(duì)列，只用改變tail即可。
void QueuePush(Queue* pq, QDateType x)
{
assert(pq); //防止pq為空指針
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newNode)
{
printf("malloc error\n");
exit(-1);
}
newNode->val = x;
newNode->next = NULL;//開辟一個(gè)新節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)
if (pq->tail == NULL)//判斷是否為空隊(duì)列
{
assert(pq->head == NULL);
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
4.出隊(duì)
對(duì)于出隊(duì)，我們同樣需要考慮兩種情況
- 隊(duì)列為空，改變head的同時(shí)改變tail
- 隊(duì)列不為空，改變head即可。
void QueuePop(Queue* pq)
{
assert(pq);//防止pq為空指針
assert(pq->head && pq->tail); //防止隊(duì)列為空隊(duì)列
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
5. 取出隊(duì)首元素
沒啥說的，直接訪問頭節(jié)點(diǎn)取出即可
QDateType QueueFront(Queue* pq)
{
assert(pq);//防止pq為空指針
assert(pq->head && pq->tail); //防止隊(duì)列為空隊(duì)列
return pq->head->val;
}
6.判斷是否為空隊(duì)列
我們只需要判斷頭指針是否為NULL，如果是則為空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
7. 求隊(duì)伍長度
創(chuàng)建一個(gè)變量，遍歷隊(duì)伍求長度。
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
int count = 0;
while (cur)
{
cur = cur->next;
count++;
}
return count;
}
四.完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDateType;
typedef struct QueueNode
{
QDateType val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
void QueueInti(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->tail = pq->head = NULL;
}
void QueuePush(Queue* pq, QDateType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newNode)
{
printf("malloc error\n");
exit(-1);
}
newNode->val = x;
newNode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
QDateType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->val;
}
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
int count = 0;
while (cur)
{
cur = cur->next;
count++;
}
return count;
}
以上就是C語言實(shí)現(xiàn)隊(duì)列的示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語言 隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了visual studio 2015下boost庫的配置教程，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-04-04
這篇文章介紹了C語言中的常量，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
C語言實(shí)現(xiàn)日期和時(shí)間處理的常用函數(shù)總結(jié)
在C語言中，時(shí)間和日期處理是一項(xiàng)非?；A(chǔ)的技能，也是開發(fā)實(shí)際應(yīng)用程序時(shí)經(jīng)常會(huì)用到的功能，本文為大家總結(jié)了C語言中一些常用的時(shí)間庫函數(shù)，希望對(duì)大家有所幫助2023-06-06
C語言中關(guān)于庫函數(shù) qsort 快排的用法
快速排序Qsort是所有學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)最基礎(chǔ)的一個(gè)部分，也是考試題和面試的一個(gè)小重點(diǎn)。本片文章帶你了解Qsort的詳細(xì)用法規(guī)則2021-09-09
C++算法實(shí)現(xiàn)leetcode 1252奇數(shù)值單元格數(shù)目
這篇文章為大家主要介紹了C++實(shí)現(xiàn)leetcode 1252奇數(shù)值單元格的數(shù)目題解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
c++內(nèi)聯(lián)函數(shù)(inline)使用詳解
這篇文章主要介紹了c++內(nèi)聯(lián)函數(shù)(inline)使用詳解,需要的朋友可以參考下2014-04-04
C++利用easyx圖形庫實(shí)現(xiàn)創(chuàng)意天天酷跑小游戲
這篇文章主要為大家詳細(xì)介紹了C++如何利用easyx圖形庫實(shí)現(xiàn)創(chuàng)意小游戲——天天酷跑，文中的示例代碼講解詳細(xì)，快跟隨小編一起了解一下吧2023-03-03
C++重載運(yùn)算符實(shí)現(xiàn)分?jǐn)?shù)加減乘除
這篇文章主要為大家詳細(xì)介紹了C++重載運(yùn)算符實(shí)現(xiàn)分?jǐn)?shù)加減乘除，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
C\C++實(shí)現(xiàn)讀寫二進(jìn)制文件的方法詳解
這篇文章主要為大家詳細(xì)介紹了C\C++實(shí)現(xiàn)讀寫二進(jìn)制文件的方法，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要介紹了C++實(shí)現(xiàn)迷宮算法實(shí)例解析,是一個(gè)比較經(jīng)典的C++算法,有一定的學(xué)習(xí)與借鑒價(jià)值,需要的朋友可以參考下2014-07-07