網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
隊(duì)列的實(shí)現(xiàn)
基本概念
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出
FIFO(First In First Out)
入隊(duì)列：進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾 出隊(duì)列：進(jìn)行刪除操作的一端稱(chēng)為隊(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ù)，效率會(huì)比較低需要挪動(dòng)數(shù)據(jù)O(N)。而鏈表結(jié)構(gòu)頭刪只需要O(1)。尾插定義一個(gè)尾指針，也只需要O(1)。
創(chuàng)建結(jié)構(gòu)體
這是一個(gè)嵌套結(jié)構(gòu)體。
實(shí)參q的地址傳給了形參pq。pq就是一個(gè)指向結(jié)構(gòu)體Queue的指針。Queue里面的head是指向隊(duì)列對(duì)頭的指針，tail是指向隊(duì)尾的指針。
int main()
{
//創(chuàng)建結(jié)構(gòu)體變量q
//需要傳q的地址過(guò)去。
Queue q;
return 0;
}
定義一個(gè)尾指針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)體
才開(kāi)始還沒(méi)有創(chuàng)建隊(duì)列的空間，所以只需要初始化第一個(gè)結(jié)構(gòu)體就ok了。隊(duì)列初始狀態(tài)需要對(duì)頭和隊(duì)尾指向同一位置，且都是空。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
銷(xiāo)毀隊(duì)列結(jié)構(gòu)體
這次我把銷(xiāo)毀結(jié)構(gòu)體放在初始化結(jié)構(gòu)體的后面，原因是內(nèi)存泄漏很?chē)?yán)重，但是經(jīng)常會(huì)忘記銷(xiāo)毀結(jié)構(gòu)體。創(chuàng)建意味著就要銷(xiāo)毀，二者對(duì)立，所以排在初始化的后面，理所應(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í)候，會(huì)創(chuàng)建新的節(jié)點(diǎn)。最好最好把新開(kāi)的newnode節(jié)點(diǎn)初始化。把他的next置為空，方便后期求隊(duì)列長(zhǎng)度函數(shù)，和出隊(duì)函數(shù)的循環(huán)條件的書(shū)寫(xiě)。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
//下面兩個(gè)初始化很有必要
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;
}
訪問(wèn)對(duì)頭的值
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
訪問(wèn)隊(duì)尾的值
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
返回隊(duì)列的長(zhǎng)度
長(zhǎng)度不可能為負(fù)數(shù)，所以返回類(lèi)型為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;
}
原文鏈接：https://blog.csdn.net/qq2466200050/article/details/123784401
相關(guān)推薦
- 2022-11-06 Git?Commitizen提交規(guī)范化自動(dòng)生成changelog文件_相關(guān)技巧
- 2022-05-02 C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單回聲服務(wù)器_C 語(yǔ)言
- 2022-12-07 C++11,?14,?17對(duì)tuple元素的訪問(wèn)詳情_(kāi)C 語(yǔ)言
- 2022-12-25 pytorch中model.named_parameters()與model.parameters(
- 2022-11-05 Flutter實(shí)現(xiàn)一個(gè)支持漸變背景的Button示例詳解_Android
- 2022-06-07 python數(shù)組的復(fù)制與列表中的pop_python
- 2022-09-26 符合選擇器和css三大特性組合
- 2022-08-10 對(duì)WPF中的TreeView實(shí)現(xiàn)右鍵選定_C#教程
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速