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

devtools/2024/11/27 15:35:51/

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/devtools/137430.html

相关文章

upload-labs 靶场(1~5)

upload-labs 靶场(1~5)

免责声明 本博客文章仅供教育和研究目的使用。本文中提到的所有信息和技术均基于公开来源和合法获取的知识。本文不鼓励或支持任何非法活动&#xff0c;包括但不限于未经授权访问计算机系统、网络或数据。 作者对于读者使用本文中的信息所导致的任何直接或间接后果不承担任何…
阅读更多...
【已解决】python面试、竞赛编程问题：最长递增子序列和旅行商问题（TSP）

【已解决】python面试、竞赛编程问题：最长递增子序列和旅行商问题（TSP）

在面试、竞赛以及实际应用中，有几个常见的问题，比如今天尝试解决的：最长递增子序列和旅行商问题（TSP）。本文针对这两个问题如何分析和求解并使用python编程实现给出了详细的步骤，供参考学习。 一、最长递增子序列问题 问题背景 一个经典的算法问题：“最长递增子序列（…
阅读更多...
vue实现滚动条滑动到底部分页调取后端接口加载数据

vue实现滚动条滑动到底部分页调取后端接口加载数据

一、案例效果 二、前提条件 接口返回数据 三、案例代码 子组件 const $emit defineEmits([cloneItem, updateList]);const props defineProps({rightList: {type: Array,},chartTableData: {type: Array as () > ChartListType[],},deleteChartInfo: {type: Object,}…
阅读更多...
LeetCode 3206.交替组 I：遍历

LeetCode 3206.交替组 I：遍历

【LetMeFly】3206.交替组 I&#xff1a;遍历 力扣题目链接&#xff1a;https://leetcode.cn/problems/alternating-groups-i/ 给你一个整数数组 colors &#xff0c;它表示一个由红色和蓝色瓷砖组成的环&#xff0c;第 i 块瓷砖的颜色为 colors[i] &#xff1a; colors[i] …
阅读更多...
线上＋线下≠新零售，6大互通诠释新零售的核心要点-亿发

线上＋线下≠新零售，6大互通诠释新零售的核心要点-亿发

新零售&#xff0c;这个词汇在近年来频繁出现在我们的视野中&#xff0c;它不仅仅是线上与线下的简单相加&#xff0c;而是一场深刻的商业变革。本文将通过6大互通的核心要点&#xff0c;为您揭示新零售的真正内涵。 1. 商品的互联互通 新零售模式下&#xff0c;商品的互联互…
阅读更多...
Redis中HGETALL和ZRANGE命令

Redis中HGETALL和ZRANGE命令

Redis中HGETALL和ZRANGE命令 简单来说 HGETALL 命令用于返回哈希表中&#xff0c;所有的字段和值。 ZRANGE 命令用于返回有序集中&#xff0c;指定区间内的成员。 HGETALL 在 Redis 中&#xff0c;HGETALL 是一个用于操作哈希&#xff08;Hash&#xff09;数据类型的命令&…
阅读更多...
Qt SQL模块概述

Qt SQL模块概述

Qt SQL支持的数据库 要在项目中使用 Qt SQL 模块&#xff0c;需要在项目配置文件中添加下面一条设置语句&#xff1a; Qt sql在头文件或源文件中使用 Qt SQL 模块中的类&#xff0c;可以使用包含语句&#xff1a; #include <QtSql>这样会将某个 Qt SQL 模块中的所有类…
阅读更多...
远程控制软件：探究云计算和人工智能的融合

远程控制软件：探究云计算和人工智能的融合

在数字化时代&#xff0c;远程控制工具已成为我们工作与生活的重要部分。用户能够通过网络远程操作和管理另一台计算机&#xff0c;极大地提升了工作效率和便捷性。随着人工智能&#xff08;AI&#xff09;和云计算技术的飞速发展&#xff0c;远程控制工具也迎来了新的发展机遇…
阅读更多...
最新文章

Copyright @ 2022~2023