初阶数据结构之队列的实现

ops/2024/11/24 9:57:23/

1 队列的定义

什么是队列呢？队列只允许在一端进行插入数据操作，在另一端进行删除数据操作。队列具有先进先出FIFO(First In First Out)的特性。

队头：删除数据的一端称为队头。

队尾：插入数据的一端称为队尾。

2 队列底层结构的选择

在这里插入图片描述

底层采用数组来实现，在删除队头元素的时候，需要移动数组元素，时间复杂度为O(N)，还会存在空间浪费。

在这里插入图片描述

采用链表实现队列，删除队头元素时，只需要让head指向下一个节点同时将头结点的空间还给操作系统。在队尾增加元素时，申请一块空间存放数据，让新节点成为链表尾节点，为了避免在增加元素时需要找链表尾节点，所以创建一个tail指针，指向链表尾节点。

因此采用链表来实现队列再合适不过了。

3 队列的实现

3.1 队列的定义

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;

3.2 队列的接口

//初始化队列
void QueueInit(Queue* pq);//队尾插入数据
void QueuePush(Queue* pq, QDataType x);//队头出数据
QDataType QueueFront(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//删除队头数据
void QueuePop(Queue* pq);//队列的大小
int QueueSize(Queue* pq);//队尾出数据
QDataType QueueBack(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

3.2.1 初始化队列

//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}

刚开始队列为空，head和tail指向NULL。保证pq不能为NULL，否则
通过pq去访问head和tail会造成野指针。

3.2.2 队尾插入数据

//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){printf("QueuePush():malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}

在这里插入图片描述

如果head为NULL，说明队列为空，则让head和tail同时指向头结点。
否则，则让tail->next保存新节点的地址同时让tail指向新节点，使新节
点成为链表的尾节点。

3.2.3 队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}else{return false;}
}

head指向NULL，说明队列为空，否则，队列不为空。

3.2.4 队头出数据

//队头出数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

队列不为空才能出数据，返回队列头结点的数据（因为head指向头结点）。

3.2.5 删除队头数据

//删除队头数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//记录下一个节点的地址QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}

删除数据首先要保证队列不能为空，其次使head指向头结点的下一个
节点，再释放头结点。如果head指向了NULL，说明队列为空，此时
应该将tail置为NULL。避免野指针的出现。

3.2.6 队列的大小

//队列的大小
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;int size = 0;while (NULL != cur){size++;cur = cur->next;}return size;
}

对链表进行遍历，计算链表节点的个数。

3.2.7 队尾出数据

//队尾出数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

保证队列不为空的前提下，返回tail指向的节点的数据。

3.2.8 销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->head!=NULL){QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->tail = NULL;
}

对链表进行遍历，先记录要删除节点的下一个节点的地址，然后释放
删除节点的空间，让head指向下一个节点。最后，将tail置为NULL
（避免野指针）。

4 队列完整代码的实现

Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;//初始化队列
void QueueInit(Queue* pq);//队尾插入数据
void QueuePush(Queue* pq, QDataType x);//队头出数据
QDataType QueueFront(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//删除队头数据
void QueuePop(Queue* pq);//队列的大小
int QueueSize(Queue* pq);//队尾出数据
QDataType QueueBack(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){printf("QueuePush():malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}//队头出数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}else{return false;}
}//删除队头数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//记录下一个节点的地址QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}//队列的大小
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;int size = 0;while (NULL != cur){size++;cur = cur->next;}return size;
}//队尾出数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->head!=NULL){QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->tail = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS#include"Queue.h"
void TestQueue1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);QDataType ret = QueueFront(&q);printf("%d ", ret);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);
}void TestQueue2()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);int size = QueueSize(&q);printf("%d ", size);QDataType ret = QueueBack(&q);printf("%d ", ret);QueueDestroy(&q);
}
int main()
{//TestQueue1();TestQueue2();return 0;
}

http://www.ppmy.cn/ops/136280.html

相关文章

什么是 C++ 中的模板特化和偏特化？如何进行模板特化和偏特化？

什么是 C++ 中的模板特化和偏特化？如何进行模板特化和偏特化？

1) 什么是 C 中的模板特化和偏特化&#xff1f; 在 C 中&#xff0c;模板提供了一种编写通用代码的方法&#xff0c;可以处理多种数据类型。然而&#xff0c;有时我们需要为特定的类型或特定的模板参数提供特定的实现&#xff0c;这就是模板特化和偏特化的用途。 模板特化&…
阅读更多...
.net的winfrom程序 窗体透明打开窗体时出现在屏幕右上角

.net的winfrom程序 窗体透明打开窗体时出现在屏幕右上角

窗体透明&#xff0c; 将Form的属性Opacity&#xff0c;由默认的100% 调整到 80%(尽量别低于50%)&#xff0c;这个数字越小越透明&#xff01; 打开窗体时出现在屏幕右上角 //构造函数 public frmCalendarList() {InitializeComponent();//打开窗体&#xff0c;窗体出现在屏幕…
阅读更多...
微服务设计模式 - 物化视图模式（Materialized View Pattern）

微服务设计模式 - 物化视图模式（Materialized View Pattern）

微服务设计模式 - 物化视图模式&#xff08;Materialized View Pattern&#xff09; 嗨&#xff0c;大家好&#xff01;今天我们来聊聊一个在云计算设计中非常实用的模式——物化视图模式&#xff08;Materialized View Pattern&#xff09;。 背景和问题 在现代分布式系统…
阅读更多...
第二十九章 TCP 客户端 服务器通信 - 记录的拼接

第二十九章 TCP 客户端 服务器通信 - 记录的拼接

文章目录 第二十九章 TCP 客户端 服务器通信 - 记录的拼接记录的拼接多路复用 TCP设备正在关闭连接使用CLOSE命令断开连接 第二十九章 TCP 客户端 服务器通信 - 记录的拼接 记录的拼接 在某些情况下&#xff0c;TCP会将不同的记录连接在一起形成单个记录。如果客户端或服务器…
阅读更多...
2024 APMCM亚太数学建模C题 - 宠物行业及相关产业的发展分析和策略 完整参考论文（2）

2024 APMCM亚太数学建模C题 - 宠物行业及相关产业的发展分析和策略 完整参考论文（2）

5.2 问题一模型的建立与求解 5.2.1 分析发展情况 为了更好地理解数据的变化趋势，利用matlab通过六个子图对宠物行业中的关键变量进行了可视化展示。 图 1. 宠物数量变化展示了 猫数量、狗数量 和 总宠物数量 在 2019-2023 年间的变化趋势。结果显示：猫的数量呈逐年上升的趋…
阅读更多...
45.坑王驾到第九期：Mac安装typescript后tsc命令无效的问题

45.坑王驾到第九期：Mac安装typescript后tsc命令无效的问题

点赞收藏加关注&#xff0c;你也能主打别墅&#xff01; 一、问题描述 Mac上终端运行如下命令&#xff1a; sudo npm install typescript -g //全局安装ts提示成功安装后&#xff0c;我测试tsc -v这个命令时出现如下错误&#xff1a; 也就是说找不到 tsc 命令。 二、解决方…
阅读更多...
40分钟学 Go 语言高并发：Context包与并发控制

40分钟学 Go 语言高并发：Context包与并发控制

Context包与并发控制 学习目标 知识点掌握程度应用场景context原理深入理解实现机制并发控制和请求链路追踪超时控制掌握超时设置和处理API请求超时、任务限时控制取消信号传播理解取消机制和传播链优雅退出、资源释放context最佳实践掌握使用规范和技巧工程实践中的常见场景…
阅读更多...
安科瑞电气股份有限公司环保用电监管综合云平台GetEnterpriseInfoById存在SQL注入漏洞

安科瑞电气股份有限公司环保用电监管综合云平台GetEnterpriseInfoById存在SQL注入漏洞

免责声明: 本文旨在提供有关特定漏洞的深入信息，帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步，未经授权访问系统、网络或应用程序，可能会导致法律责任或严重后果。因此，作者不对读者基于本文内容所采取的任何行为承担责任。读者在…
阅读更多...
最新文章

Copyright @ 2022~2023