C語言?隊(duì)列的實(shí)現(xiàn)全解析
隊(duì)列的實(shí)現(xiàn)
基本概念
隊(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ì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會比較低需要挪動數(shù)據(jù)O(N)。而鏈表結(jié)構(gòu)頭刪只需要O(1)。尾插定義一個尾指針，也只需要O(1)。
創(chuàng)建結(jié)構(gòu)體
這是一個嵌套結(jié)構(gòu)體。
實(shí)參q的地址傳給了形參pq。pq就是一個指向結(jié)構(gòu)體Queue的指針。Queue里面的head是指向隊(duì)列對頭的指針，tail是指向隊(duì)尾的指針。
int main()
{
//創(chuàng)建結(jié)構(gòu)體變量q
//需要傳q的地址過去。
Queue q;
return 0;
}
定義一個尾指針tail方便入隊(duì)的尾插。頭指針head方便出隊(duì)時(shí)的頭刪。
typedef int QDataType;
//節(jié)點(diǎn)結(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)建隊(duì)列的空間，所以只需要初始化第一個結(jié)構(gòu)體就ok了。隊(duì)列初始狀態(tài)需要對頭和隊(duì)尾指向同一位置，且都是空。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
銷毀隊(duì)列結(jié)構(gòu)體
這次我把銷毀結(jié)構(gòu)體放在初始化結(jié)構(gòu)體的后面，原因是內(nèi)存泄漏很嚴(yán)重，但是經(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;
}
入隊(duì)
入隊(duì)的時(shí)候，會創(chuàng)建新的節(jié)點(diǎn)。最好最好把新開的newnode節(jié)點(diǎn)初始化。把他的next置為空，方便后期求隊(duì)列長度函數(shù)，和出隊(duì)函數(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;
}
}
出隊(duì)
因?yàn)镼ueue結(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;
}
}
判斷隊(duì)列是否為空
為空返回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;
}
訪問隊(duì)尾的值
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
返回隊(duì)列的長度
長度不可能為負(fù)數(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語言 隊(duì)列的實(shí)現(xiàn)全解析的文章就介紹到這了,更多相關(guān)C語言 隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++虛函數(shù)的工作原理的的相關(guān)資料，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
這篇文章主要介紹了Windows消息傳遞機(jī)制,有助于讀者更好的理解windows編程的消息機(jī)制,需要的朋友可以參考下2014-07-07
本文主要介紹C語言中的if else,這里詳細(xì)介紹了if else 語句并提供了簡單的示例代碼,希望能幫助編程入門的小伙伴學(xué)習(xí)2016-07-07
本文是C++設(shè)計(jì)模式系列文章的第一篇，主要給大家講述下工廠模式，非常的簡單實(shí)用，有需要的小伙伴可以參考下2016-05-05
這篇文章主要給大家介紹了關(guān)于c語言和c++語言中const修飾的變量區(qū)別的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2022-02-02
chrono庫是C++11中的一個標(biāo)準(zhǔn)庫,它提供了一系列與時(shí)間相關(guān)的類和函數(shù),用于表示和處理時(shí)間間隔,時(shí)鐘和時(shí)間點(diǎn),C++20新增Calendar,這篇文章主要介紹了C++日期與時(shí)間 chrono庫介紹及使用,需要的朋友可以參考下2023-12-12
C++實(shí)現(xiàn)優(yōu)酷土豆去視頻廣告的方法
這篇文章主要介紹了C++實(shí)現(xiàn)優(yōu)酷土豆去視頻廣告的方法,實(shí)例分析了C++實(shí)現(xiàn)屏蔽功能的相關(guān)技巧,需要的朋友可以參考下2015-04-04
C++ STL 標(biāo)準(zhǔn)庫中的sort()函數(shù)專門用來對容器或普通數(shù)組中指定范圍內(nèi)的元素進(jìn)行排序，本文就詳細(xì)的介紹一下怎么實(shí)現(xiàn)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
Qt?QtCreator添加自定義注釋的實(shí)現(xiàn)方法
在寫代碼的時(shí)候我們?yōu)榱艘?guī)范化,一般會加文件注釋、類注釋和函數(shù)注釋,本文主要介紹了Qt?QtCreator添加自定義注釋的實(shí)現(xiàn)方法,具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11
C++服務(wù)器和客戶端交互的項(xiàng)目實(shí)踐
本文主要介紹了C++服務(wù)器和客戶端交互的項(xiàng)目實(shí)踐，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07