C語言?隊列的實現(xiàn)全解析
更新時間：2022年04月01日 09:47:58 作者：_奇奇
隊列（Queue）與棧一樣，是一種線性存儲結(jié)構(gòu)，它具有如下特點：隊列中的數(shù)據(jù)元素遵循“先進先出”（First?In?First?Out）的原則，簡稱FIFO結(jié)構(gòu)。在隊尾添加元素，在隊頭刪除元素
隊列的實現(xiàn)
基本概念
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出
FIFO(First In First Out)
入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低需要挪動數(shù)據(jù)O(N)。而鏈表結(jié)構(gòu)頭刪只需要O(1)。尾插定義一個尾指針，也只需要O(1)。
創(chuàng)建結(jié)構(gòu)體
這是一個嵌套結(jié)構(gòu)體。
實參q的地址傳給了形參pq。pq就是一個指向結(jié)構(gòu)體Queue的指針。Queue里面的head是指向隊列對頭的指針，tail是指向隊尾的指針。
int main()
{
//創(chuàng)建結(jié)構(gòu)體變量q
//需要傳q的地址過去。
Queue q;
return 0;
}
定義一個尾指針tail方便入隊的尾插。頭指針head方便出隊時的頭刪。
typedef int QDataType;
//節(jié)點結(jié)構(gòu)體
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
//頭指針和尾指針的結(jié)構(gòu)體
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
初始化結(jié)構(gòu)體
才開始還沒有創(chuàng)建隊列的空間，所以只需要初始化第一個結(jié)構(gòu)體就ok了。隊列初始狀態(tài)需要對頭和隊尾指向同一位置，且都是空。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
銷毀隊列結(jié)構(gòu)體
這次我把銷毀結(jié)構(gòu)體放在初始化結(jié)構(gòu)體的后面，原因是內(nèi)存泄漏很嚴重，但是經(jīng)常會忘記銷毀結(jié)構(gòu)體。創(chuàng)建意味著就要銷毀，二者對立，所以排在初始化的后面，理所應(yīng)當(dāng)。
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;
}
入隊
入隊的時候，會創(chuàng)建新的節(jié)點。最好最好把新開的newnode節(jié)點初始化。把他的next置為空，方便后期求隊列長度函數(shù)，和出隊函數(shù)的循環(huán)條件的書寫。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
//下面兩個初始化很有必要
newnode->data = 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;
}
}
出隊
因為Queue結(jié)構(gòu)體不可能為空,所以需要斷言
還需要斷言pq->head和tail都不為空。
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
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
判斷隊列是否為空
為空返回true，為假返回false
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
訪問對頭的值
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
訪問隊尾的值
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
返回隊列的長度
長度不可能為負數(shù)，所以返回類型為size_t
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
//size_t size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
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;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = 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
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
Test.c
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
printf("%d ", QueueFront(&q));
QueuePop(&q);
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語言 隊列的實現(xiàn)全解析的文章就介紹到這了,更多相關(guān)C語言 隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
VisualStudio2019構(gòu)建C/C++靜態(tài)庫和動態(tài)庫dll的問題 附源碼
這篇文章主要介紹了VisualStudio2019構(gòu)建C/C++靜態(tài)庫和動態(tài)庫(dll)(文末附源碼),本文通過實例圖文相結(jié)合給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
C++實現(xiàn)WebSocket服務(wù)器的案例分享
WebSocket是一種在單個TCP連接上進行全雙工通信的通信協(xié)議,與HTTP協(xié)議不同,它允許服務(wù)器主動向客戶端發(fā)送數(shù)據(jù),而不需要客戶端明確地請求,本文主要給大家介紹了C++實現(xiàn)WebSocket服務(wù)器的案例,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了C++中賦值運算符與逗號運算符的用法詳解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C/C++ 雙鏈表之逆序的實例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07
當(dāng)談?wù)揅++編程語言時,以下術(shù)語經(jīng)常被提及：int、DWORD和QWORD,它們是用于表示不同數(shù)據(jù)類型和長度的關(guān)鍵字,本文通過舉例給大家詳細介紹,感興趣的朋友一起看看吧2024-06-06
C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算
這篇文章主要介紹了C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算,文章中還介紹了矩陣相關(guān)的斯特拉森算法的實現(xiàn),需要的朋友可以參考下2015-12-12
shared_ptr是一個標(biāo)準(zhǔn)的共享所有權(quán)的智能指針，允許多個指針指向同一個對象，定義在memory文件中，命名空間為std，這篇文章主要介紹了C++ shared_ptr使用，需要的朋友可以參考下2022-11-11
五子棋游戲是一款很經(jīng)典的智力游戲，只有學(xué)過編程語言的人，把五子棋的編程原理弄懂了，就能用自己熟悉的語言實現(xiàn)出來，在這里給大家分享，c語言五子棋源碼，僅供大家參考借鑒。2016-03-03
這篇文章主要介紹了C++類中的static和const用法,是C++面向?qū)ο蟪绦蛟O(shè)計中非常重要的概念,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細介紹了OpenCV畫任意圓弧曲線，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01