【数据结构】队列（链表模拟队列）

🕗 发布于 2024-04-19 09:05 数据结构 链表队列单链表

学习本章节必须具备单链表的前置知识，

建议提前学习：点击链接学习：单链表各种功能函数细节详解

本章节是学习用单链表模拟队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

使用数组还是链表模拟队列结构？

因为需要模拟队列先进先出的特性：队头只能出，队尾只能进

若使用 数组模拟，每次 pop 队头操作，就需要全部元素向前面移动，时间复杂度为 O(n)

综上，因为需要考虑位置变化，选择链表实现队列较优

需要使用什么类型的链表模拟队列？

单向

带头 / 不带头都可以 ：因为哨兵位主要用于双向链表找尾，为了方便删除，这里差别不大

不循环

我们下面实现的是单向不带头不循环链表

实际上，单向或双向，循环或不循环，带头或不带头完全取决于你自己要实现一个功能的需求，不是说一定要固定使用哪一个套，需要灵活选择使用

单向链表实现队列的链表节点结构体创建：

typedef int QDataType;
typedef struct QueueNode
{
QDataType value;            // 节点数据
struct QueueNode* next;     // 指向下一个节点
}QNode;

考虑效率，创建头尾指针结构体

因为队列需要：队头 push，队尾 pop

涉及到对链表的尾部操作必须意识到：需要先进行 找尾操作，时间复杂度为 O(n)

方案：因为涉及头尾频繁操作：可以直接同时定义头指针 phead 和尾指针 ptail

技巧：同类型的变量可以封装成一个结构体

因为 phead 和 ptail 是可以不断变化的，每个相关函数都需要同时传递 phead 和 ptail 两个变量

则可以将多个同类型的变量 封装成一个结构体，方便操作

这样，传递变量时直接传递一个结构体的指针就行了

typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
}Queue;

// 区别：减少了传递变量的数量，利于协助开发
// void QueuePush(QNode* phead, QNode* ptail);
void QueuePush(Queue* pq);
// void QueuePop(QNode* phead, QNode* ptail);
void QueuePop(Queue* pq);

Push / Pop ：入队和出队操作

Push 在队尾入队，Pop 在队头出队

void QueuePop(Queue* pq)
{
assert(pq);
// pop 的删除操作 需要分类讨论：链表节点个数为 0、为 1、为 两个以上
    
// 为 0 ：直接判空，退出操作：phead == ptail == NULL
assert(pq->phead);    // 头节点为空 就一定代表为空了
    
// 为 1：phead == ptail  但是 phead != NULL 的情况：即一定指向一个节点
if (pq->phead == pq->ptail && pq->phead != NULL) {
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else // 为 两个以上：先记录第二个节点，free 掉头节点，更新头节点
{
QNode* tmp = pq->phead->next;
free(pq->phead);
pq->phead = tmp;
}
}

为什么 ” 头节点为空或尾节点为空就一定代表链表为空了 “？

观察上面代码：有需要判断链表节点数量的需求，为了简化代码与优化过程，可以直接定义一个 size ，放进结构体中，时刻记录链表节点数量

// 结构体更改：
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;

// 加入 size 后 的 Push 和 Pop 函数
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->phead);

    if (pq->size == 1) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else if (pq->size >= 2)
    {
        QNode* next = pq->phead->next;  // 保留下一个
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}


void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    // push 前先创建一个新节点
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL) {
        perror("malloc fail");
        return;
    }
    newNode->value = x;
    newNode->next = NULL;

    
    if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空
    {
        pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接
        pq->ptail = newNode; // 重新更新尾节点
    }
    else  // 若链表为空，则 phead 和 ptail 都要 处理
    {
        pq->phead = pq->ptail = newNode;
    }
    pq->size++;   // 数量++
}

综上所述，最终代码：

Queue.c

#include"Queue.h"

// Push 入队，Pop 出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead);

if (pq->size == 1) {
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else if (pq->size >= 2)
{
QNode* next = pq->phead->next;  // 保留下一个
free(pq->phead);
pq->phead = next;
}
pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}

void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
// push 前先创建一个新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL) {
perror("malloc fail");
return;
}
newNode->value = x;
newNode->next = NULL;

if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空
{
pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接
pq->ptail = newNode; // 重新更新尾节点
}
else  // 若链表为空，则 phead 和 ptail 都要 处理
{
pq->phead = pq->ptail = newNode;
}
pq->size++;   // 数量++
}

// 初始化
void  QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

// 销毁链表：就是 单链表的 销毁操作
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur) {
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULL
pq->size = 0;
}

// Front 返回队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead); // 若链表为空 自然没有头节点;
return pq->phead->value;
}

// Back 返回队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail); // 若链表为空 自然没有尾节点;
return pq->ptail->value;
}

// Empty 判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}

// Size 返回节点数量
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int QDataType;
typedef struct QueueNode
{
QDataType value;
struct QueueNode* next;
}QNode;

typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;


// 初始化
void  QueueInit(Queue* pq);   

// Push 入队，Pop 出队
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);

// Front 队头元素，Back 队尾元素
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

// Empty 判断是否为空，Size 返回节点数量
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

// 销毁链表
void QueueDestory(Queue* pq);

Main.c

#include"Queue.h"

int main()
{
Queue q;   // 创建队列结构体
QueueInit(&q); // 初始化：用于初始化链表的头尾节点：phead  /  ptail

for (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5
QueuePush(&q, i); 
}

// 一个个读取队列元素
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}

QueueDestory(&q);
return 0;
}

【若文章有什么错误，欢迎评论区讨论或私信指出】

原文地址：https://blog.csdn.net/2301_79499548/article/details/137941463

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：亚远景科技-结合ASPICE和ISO26262标准谈谈汽车软件开发中的质量管理与控制
下一篇：开发语言漫谈-Object C

GetThreadSelectorEntry teb peb 段选择子 LDT_ENTRY _LDT_ENTRY
GetThreadSelectorEntry teb peb 段选择子 LDT_ENTRY _LDT_ENTRY
阅读更多2024-09-27
SD卡认识——SDIO协议入门与实践（一）
经常用sd卡会在卡的正面看到，**SD、SDHC、SDXC**的字样，一般用户也不太关心这些，但如果要搞sd卡相关开发，还是要了解一二的
阅读更多2024-09-27
HTAP 数据库的应用场景：是否被过度夸大？
HTAP 数据库的应用场景：是否被过度夸大？
阅读更多2024-09-27
美国林氏集团宣布全面进军Web3领域
吉隆坡，马来西亚——近日举行的第六界博览会上，美国林氏集团董事局主席林建中先生宣布，集团将通过旗下的大东亚银行创建一个全新的、合规的区块链交易所，并正式进军Web3、元宇宙及AI领域。同时，美国林氏集
阅读更多2024-09-27
Mysql之索引优化
指定索引适合开发者手动介入优化查询。覆盖索引能够在频繁查询特定列时，避免回表，提升查询效率，是性能优化的重要手段。前缀索引适用于长文本字段，能在保证索引效率的同时，减少存储开销。
阅读更多2024-09-27
Linux上的C/C++编程
vim，gcc，make/makefile，gdb
阅读更多2024-09-27
从耐用到防水：全面综合评估SD卡的性能指标
SD卡（Secure Digital Memory Card）是一种广泛使用的存储器件，因其快速的数据传输速度、可热插拔的特性以及较大的存储容量，广泛应用于各种场景，例如在便携式设备如智能手机、平板电
阅读更多2024-09-27
JSON 教程
【代码】JSON 教程。
阅读更多2024-09-27
ThreeJs绘制圆柱体
Threejs可以方便地创建各种不同尺寸和外观的圆柱体，可应用于构建机械模型、建筑结构、柱状物体等场景。是用于创建圆柱体几何形状的类。圆柱体在三维图形中是一种常见的基本形状。
阅读更多2024-09-27
MongoDB-索引的使用和索引类型
非常详细的MongoDB的索引介绍，针对MongoDB的索引大致可以分为，唯一索引、单列索引、多列索引（复合索引）、多键索引（数组字段索引）、文本搜索索引、地理空间索引，等。
阅读更多2024-09-27

【数据结构】队列（链表模拟队列）

学习本章节必须具备 单链表的前置知识，

建议提前学习：点击链接学习：单链表各种功能函数 细节 详解

本章节是学习用 单链表模拟队列

使用 数组 还是 链表 模拟 队列 结构？

需要使用 什么类型的 链表模拟队列？

单向链表 实现队列 的链表节点结构体创建：

考虑效率，创建 头尾指针结构体

Push / Pop ：入队 和 出队操作

为什么 ” 头节点为空 或 尾节点为空 就一定代表链表为空了 “？

观察上面代码：有需要 判断链表节点数量的 需求，为了简化代码与优化过程，可以 直接定义一个 size ，放进结构体中，时刻记录 链表节点数量