C語言數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列的實(shí)現(xiàn)詳解
隊(duì)列的概念及結(jié)構(gòu)
隊(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ì)列的結(jié)構(gòu)在生活中非常地常見，比如排隊(duì)時(shí)的抽號機(jī)就是一個(gè)典型的隊(duì)列結(jié)構(gòu)。那隊(duì)列如何實(shí)現(xiàn)呢？我們一起來看一下。
隊(duì)列的實(shí)現(xiàn)
隊(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ù)，時(shí)間復(fù)雜度為O(N)，效率會比較低。
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head; // 頭指針
QNode* tail; // 尾指針
int size; // 節(jié)點(diǎn)的個(gè)數(shù)
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
隊(duì)列要實(shí)現(xiàn)的函數(shù)接口有：初始化隊(duì)列、銷毀隊(duì)列、數(shù)據(jù)入隊(duì)、數(shù)據(jù)出隊(duì)、返回隊(duì)頭的數(shù)據(jù)、返回隊(duì)尾的數(shù)據(jù)、判斷隊(duì)列是否為空以及隊(duì)列中數(shù)據(jù)的個(gè)數(shù)。這些接口實(shí)現(xiàn)起來也不是很難，我們一起來看一下。
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
// 隊(duì)列中沒有節(jié)點(diǎn)
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
//del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
初始化隊(duì)列
頭指針和尾指針都指向空，隊(duì)列元素個(gè)數(shù)初始化為0
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
銷毀隊(duì)列
利用while循環(huán)將申請的節(jié)點(diǎn)一一釋放掉，然后頭指針pq->head和尾指針pq->tail指向空，棧的數(shù)據(jù)個(gè)數(shù)置為 0pq->size = 0
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
數(shù)據(jù)入隊(duì)
1.申請新的節(jié)點(diǎn)newnode newnode->data = x,newnode->next = NULL
2.數(shù)據(jù)入隊(duì)：當(dāng)pq->tail == NULL時(shí)，隊(duì)列中沒有節(jié)點(diǎn)，那么頭指針和尾指針都賦值為newnode pq->head = pq->tail = newnode；當(dāng)pq->tail != NULL時(shí)，隊(duì)列中有節(jié)點(diǎn)，那么尾部鏈接上新節(jié)點(diǎn)newnode，然后newnode成為新的尾結(jié)點(diǎn)。
3.隊(duì)列數(shù)據(jù)個(gè)數(shù)加一pq->size++
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
// 隊(duì)列中沒有節(jié)點(diǎn)
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
數(shù)據(jù)出隊(duì)
1.判斷隊(duì)列是否為空
2.數(shù)據(jù)出隊(duì)：當(dāng)pq->head->next == NULL時(shí)，隊(duì)列中只有一個(gè)節(jié)點(diǎn)，釋放該節(jié)點(diǎn)，頭指針和尾指針都指向空；當(dāng)pq->head->next != NULL時(shí)，釋放讓頭指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，釋放原來的頭節(jié)點(diǎn)
3.隊(duì)列數(shù)據(jù)個(gè)數(shù)減一pq->size--
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
//del = NULL;
}
pq->size--;
}
返回隊(duì)頭數(shù)據(jù)
先判斷隊(duì)列是否為空，不為空時(shí)，返回隊(duì)頭數(shù)據(jù)。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
返回隊(duì)尾數(shù)據(jù)
先判斷隊(duì)列是否為空，不為空時(shí)，返回隊(duì)尾數(shù)據(jù)。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
判斷隊(duì)列是否為空
判斷隊(duì)列是否為空有兩種方式：1.判斷pq->size等不等于 0；2.判斷頭指針pq->head和尾指針pq->tail是否等于空指針NULL
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head == NULL && pq->tail == NULL;
}
隊(duì)列中數(shù)據(jù)的個(gè)數(shù)
直接返回隊(duì)列數(shù)據(jù)的個(gè)數(shù)pq->size
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
Test.c
以下為測試函數(shù)接口的代碼，大家可以參考一下。需要注意的是，打印隊(duì)列中的數(shù)據(jù)是通過打印隊(duì)頭數(shù)據(jù)、Pop掉隊(duì)頭數(shù)據(jù)的方式來實(shí)現(xiàn)的。
#include "Queue.h"
void QueueTest()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("%d ", QueueFront(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePop(&q);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
QueueTest();
return 0;
}
以上就是C語言數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列的實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu) 隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++虛繼承的內(nèi)存模型是一個(gè)老生常談的話題，實(shí)現(xiàn)方法主要依賴于編譯器，本文從多個(gè)角度通過代碼詳解C++中虛繼承的內(nèi)存模型知識，感興趣的朋友跟隨小編一起看看吧2021-07-07
基類成員的private成員不但對于對象是不可見的，對于派生類也是不可見的，只能被基類成員或者友元訪問2013-09-09
C++動態(tài)調(diào)用動態(tài)鏈接庫(DLL或SO)的方法實(shí)現(xiàn)
動態(tài)鏈接庫是一種Windows操作系統(tǒng)下常見的可執(zhí)行文件格式,它包含了一些可被其他應(yīng)用程序調(diào)用的函數(shù)和數(shù)據(jù),本文主要介紹了C++動態(tài)調(diào)用動態(tài)鏈接庫(DLL或SO),感興趣的可以了解一下2024-01-01
在C語言中g(shù)etchar的使用方法和讀取規(guī)則講解
getchar中文意思是獲取字符，getchar函數(shù)從標(biāo)準(zhǔn)輸入輸出里讀取下一個(gè)字符，返回類型為int整形，返回用戶輸入的ASCII碼值，如果到達(dá)文件末尾或者出錯返回EOF，這篇文章主要介紹了在C語言中g(shù)etchar的使用方法和讀取規(guī)則，需要的朋友可以參考下2022-12-12
C語言之如何用isspace()和ungetc()實(shí)現(xiàn)前導(dǎo)空白字符過濾
這篇文章主要介紹了C語言如何用isspace()和ungetc()實(shí)現(xiàn)前導(dǎo)空白字符過濾問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
這篇文章主要介紹了C++中運(yùn)算符重載詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++編程中的文件流與字符串流,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
大數(shù)據(jù)情況下桶排序算法的運(yùn)用與C++代碼實(shí)現(xiàn)示例
在排序元素很多的情況下,其實(shí)桶排序的性能并不是太高,這里我們配合單鏈表的直接插入排序,來看下一大數(shù)據(jù)情況下桶排序算法的運(yùn)用與C++代碼實(shí)現(xiàn)示例:2016-07-07
這篇文章主要介紹了opencv攝像頭捕獲識別顏色，用opencv通過攝像頭捕獲識別顏色，紅色藍(lán)色等，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07
C語言沒有運(yùn)行時(shí)庫，無法自動壓縮使用中的內(nèi)存，縮小堆棧所需內(nèi)存空間。若只申請內(nèi)存，沒有釋放，勢必造成系統(tǒng)內(nèi)存不斷減少、丟失。長時(shí)間的運(yùn)行，最終導(dǎo)致系統(tǒng)死機(jī)。文章闡述了C語言垃圾產(chǎn)生的原因，并從引用計(jì)數(shù)、標(biāo)記一清除算法兩方面提出如何實(shí)現(xiàn)C語言的垃圾回收。2019-02-02