数据结构：线性表之-队列

2023-09-21 22:45:23

目录

什么是队列？

详解：

功能介绍

代码实现

定义队列基本结构

1，初始化

2, 销毁

3,尾入数据

4,头出数据

5,取队头的数据

6,取队尾的数据

7,判断是否为空

8,计算队列中的元素

成品

Queue.h

Queue.c

test.c

队列的讲解将建立在有双向链表的基础之上进行讲解
当然队列只是链表的一种分支
单项链表详解：# 数据结构：线性表之-单向链表(无头)
双向链表详解：# 数据结构：线性表之-循环双向链表(万字详解)

什么是队列？


队列是一种常见的数据结构，用于存储和管理数据的集合。它遵循先进先出（FIFO）的原则，即最先进入队列的元素最先被删除。类比一下，你可以把队列视为排队等待服务的人群，新来的人排在队列末尾，而需要服务的人从队列头部被依次处理。

队列通常有两种基本操作：

  1. 入队（enqueue）：将元素添加到队列的末尾。
  2. 出队（dequeue）：从队列的头部删除一个元素，并返回被删除的元素。

除了入队和出队操作，队列还可以支持其他操作，如获取队列的大小（元素个数）、判断队列是否为空等。队列在计算机科学中有广泛的应用，例如任务调度、缓冲区管理、计算机网络等领域。
当队列已满时，新的元素无法入队，我们称之为队列满（Queue Full）。
当队列为空时，没有元素可以出队，我们称之为队列空（Queue Empty）。

队列的实现方式有多种，最常见的是使用数组或链表来存储元素。在数组实现中，我们使用一个固定大小的数组来存储元素，并使用两个指针（front和rear）分别指向队列的头部和尾部。入队操作时，将元素添加到rear指针所指位置，并将rear指针向后移动一位；出队操作时，将front指针所指位置的元素删除，并将front指针向后移动一位。

队列的应用非常广泛。举例来说，在计算机的操作系统中，进程调度算法通常使用队列来管理待执行的进程。在网络数据传输中，数据包也会按照先后顺序排队等待传输。此外，实现广度优先搜索算法、缓冲区处理等也需要使用队列。队列数据结构的特性使得它在这些场景下非常实用，能够提高程序的效率和性能。

详解：

功能介绍

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

//销毁
void QueueDestory(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);

代码实现

定义队列基本结构

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

typedef struct Queue
{
	//定义两个指针，tail方便尾插
	//方便对头出数据，尾入数据
	QNode* head;
	QNode* tail;
}Queue;

1，初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

2, 销毁

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;
}

这段代码实现了队列的销毁操作。
它接受一个指向队列的指针 pq，并通过遍历队列中的每个节点来逐个释放它们的内存。
首先，它在 assert 语句中检查指针 pq 是否为空，以确保操作的安全性。
然后，它将队列的头指针 pq->head 赋值给局部变量 cur，作为遍历的起始点。
接下来使用一个循环来遍历队列的每个节点。在每次循环中，它首先将当前节点 cur 的下一个节点保存在指针变量 next 中，以便能够继续遍历队列。
然后，它使用 free 函数释放当前节点 cur 的内存。
最后，它将 cur 更新为 next，以便在下一次循环中继续遍历。在循环结束后，它将队列的头指针 pq->head 和尾指针 pq->tail 都设为 NULL，表示队列已经为空了。
这段代码确保了在销毁队列后，所有节点的内存都得到了正确的释放，以避免内存泄漏。

3,尾入数据

void QueueDestory(Queue* pq)
{
	assert(pq);
	//QNode* cur = pq->head;`：创建一个指针 `cur`，
    //并将其初始化为指向队列的头节点。这将是遍历队列的起点
	QNode* cur = pq->head;
	while (cur)
	{
		//创建一个指针 `next`，将其指向当前节点 `cur` 的下一个节点。
		//这是为了保留对下一个节点的引用，以便在释放当前节点后继续访问。
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//在循环结束后，将队列的头指针 `pq->head` 
    //和尾指针 `pq->tail` 都设置为 NULL，表示队列为空。
	pq->head = pq->tail = NULL;
}

4,头出数据

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	/*1，只有一个头节点
	2，多个节点*/
	//判断队列是否只有一个节点。如果队列只有一个节点，即头节点，进入 `if` 语句。
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//创建一个指针 `next`，将其指向头节点的下一个节点。
		QNode* next = pq->head->next;
		free(pq->head);
		//将指针 `pq->head` 更新为 `next`，即将头指针指向下一个节点。
		pq->head = next;
	}
}

5,取队头的数据

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

6,取队尾的数据

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

7,判断是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

8,计算队列中的元素

int QueueSize(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

此处是单独创建一个函数进行计算队列中的元素个数
另一种方法是在定义队列基本结构的结构体中定义一个int size
每次尾增时++size
每次头删时–size

成品

Queue.h

#pragma once

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

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

typedef struct Queue
{
	//定义两个指针，tail方便尾插
	//方便对头出数据，尾入数据
	QNode* head;
	QNode* tail;
}Queue;

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

//销毁
void QueueDestory(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);

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));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;

	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

//头出数据
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	//1，只有一个头节点
	//2，多个节点
	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;
	}
}

//取队头的数据
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->head == NULL;
}

//计算队列中的元素
int QueueSize(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

test.c

test.c只是用于测试代码，菜单的写法本文将不进行讲解。
但test.c中含有对查找and销毁and存储链元素个数的使用方法进行了示例可以当参考。

#include "Queue.h"

void test()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);
}

int main()
{
	test();

	return 0;
}
更多推荐

MySQL主从复制与读写分离

目录MySQL主从复制1、mysql支持的复制类型2、主从复制的工作过程3、主从复制操作1）下载时间同步工具，并配置时间源，实现slave库与master库时间同步2）、配置主master库3）配置slave库4）登录主MySQL，给从服务器授权5）登录从数据库，配置同步，并启动同步6）测试MySQL读写分离MySQL

HTTPS的传输过程

加密分为两种方式一种是对称加密，一种是非对称加密。在对称加密算法中，加密和解密使用的密钥是相同的。也就是说，加密和解密使用的是同一个密钥。因此，对称加密算法要保证安全性的话，密钥要做好保密。只能让使用的人知道，不能对外公开。在非对称加密算法中，加密使用的密钥和解密使用的密钥是不相同的。一把是作为公开的公钥，另一把是作为

机器学习西瓜书+南瓜书吃瓜教程学习笔记第四章决策树

1、算法原理从逻辑角度，一堆ifelse语句的组合从集合角度，根据某种准则划分特征空间最终目的：将样本越分越“纯”决策树是基于树结构来进行决策的例如，我们对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”：我们先看“它是什么颜色？”，如果是“青绿色”，则我们再看“它的根蒂是什么形态？”，如果是“

Linux C 网络基础

为什么需要网络通信？进程间通信解决的是本机内通信网络通信解决的是任意不同机器的通信实现网络通信需要哪些支持1.通信设备：网卡（PC机自带）；路由器和交换机；光纤、电缆和基站2.通信协议：2.1.操作系统自带协议栈（Linux的特点：丰富的网络协议）2.2.裸机开发需要独立的协议栈3.简单网络通信只需要学会系统APITC

Java基础（三）

前言：前面主要涉及到java的基本语法，接下来本篇博客主要记录Java中Collections类、泛型、以及File类、IO流的学习。目录数据结构泛型集合分类Collection的分类collection常用方法collection遍历方式迭代器for循环Lambda表达式List集合特点增删改查List集合的遍历方式

爬虫 — Scrapy 框架（一）

目录一、介绍1、同步与异步2、阻塞与非阻塞二、工作流程三、项目结构1、安装2、项目文件夹2.1、方式一2.2、方式二3、创建项目4、项目文件组成4.1、piders/__init__.py4.2、spiders/demo.py4.3、__init__.py4.4、items.py4.5、middlewares.py4.

npm安装心得（依赖库Python及node-sass依赖环境）

在使用vue的开发环境过程中，总会遇到这样哪样的安装或者打包错误，vue运行或打包常见错误如下：1.npminstall时node-sassnpmERRcommandfailed（可能是node.js的版本和node-sass的版本不符，就是卸掉原来的node.js，下载一个符合node-sass版本的node.js）

Go - 【字符串，数组，哈希表】常用操作

一.字符串字符串长度：s:="hello"l:=len(s)fmt.Println(l)//输出5遍历字符串：s:="hello"fori,c:=ranges{fmt.Printf("%d:%c",i,c)}//输出：0:h1:e2:l3:l4:ofori:=0;i<len(s);i++{fmt.Printf("%s"

Go基础-文件、字符

文件创建导入“os”包，创建文件，读写文件的函数都在改包。指定创建的文件存放路径以及文件名。执行Create()函数，进行文件创建。关闭文件。packagemainimport("fmt""os")funcmain(){//创建文件，需要指定文件的存放路径以及文件名称//file为文件指针file,err:=os.Cr

C#控制台程序中使用log4.net来输出日志

Apachelog4net库是一个帮助程序员将日志语句输出到各种输出目标的工具。log4net是优秀的Apachelog4j™框架到Microsoft®.NE​​T运行时的端口。我喜欢他可以自定义输出，区分等级等特点。导入库我们在工程里添加NuGet的包。输入名称log4net，导入包。创建配置文件然后我们在项目根创建

北邮22级信通院数电：Verilog-FPGA（3）实验“跑通第一个例程”modelsim仿真及遇到的问题汇总（持续更新中）

北邮22信通一枚~跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章持续关注作者迎接数电实验学习~获取更多文章，请访问专栏：北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客注意：本篇文章所有绝对路径的展示都来自上一篇博客北邮22级信通院数电：Verilog-FPGA（2）modelsim北邮信通专属下

热文推荐
  1. Spring底层原理之 BeanFactory 与 ApplicationContext

    🐌个人主页：🐌叶落闲庭💨我的专栏：💨c语言数据结构javaEE操作系统Redis石可破也，而不可夺坚；丹可磨也，而不可夺赤。Spring底层原理一、BeanFactory与ApplicationContext二、BeanFactory功能三、ApplicationContext功能3.1getMessage3.

  2. 【计算机网络】IP协议第一讲（协议格式介绍）

    IP协议1.协议头格式1.1概念介绍1.2补充说明1.2.18位生存时间---TTL1.2.216位首部检验和首先明确一个概念：TCP/IP协议是配合使用的，TCP负责可靠传输策略，IP则是负责传输，TCP协议是位于传输层提供的是策略解决可靠性问题，IP协议在网络层，提供的是网络传输服务，实现A主机到B主机的跨网络通信

  3. Python爬虫异常处理实用技巧分享

    当我们编写爬虫程序时，经常会遇到各种各样的异常情况，比如网络连接失败、页面解析错误、请求被拒绝等等。这些异常情况可能导致程序中断或者无法正常运行，给我们的数据采集工作带来一定的困扰。所以，掌握一些实用的异常处理技巧对于提高爬虫的稳定性和效率非常重要。在Python中，我们可以使用try-except语句来处理异常。下面

  4. DSOX3012A是德科技keysight DSOX3012A示波器

    181/2461/8938是德科技DSOX3012A(安捷伦)示波器是德科技DSOX3012A(安捷伦)是InfiniiVision3000X系列中的双通道型号。这款可升级示波器采用突破性技术设计，提供卓越的性能和功能。其独特的5仪器合一设计为相同的预算提供了更大的范围。是德科技DSOX3012A示波器的特性和规格包括

  5. 网络安全深入学习第五课——热门框架漏洞（RCE— Apache Shiro 1.2.4反序列化漏洞）

    文章目录一、序列化和反序列化二、反序列化漏洞原理三、ApacheShiro1.2.4反序列化漏洞1、漏洞描述：2、漏洞影响的版本3、Shiro反序列化漏洞原理4、工作原理：5、shiro反序列化的特征：四、ApacheShiro1.2.4反序列化漏洞手工复现1、使用DNSlog严重漏洞是否存在2、VPS监听端口3、构造

  6. 【Vue】如何搭建SPA项目--详细教程

    🎬艳艳耶✌️：个人主页🔥个人专栏：《Spring与Mybatis集成整合》《springMvc使用》⛺️生活的理想，为了不断更新自己!目录1.什么是vue-cli2.安装2.1.创建SPA项目2.3.一问一答模式答案3.运行SPA项目3.1.导入项目3.2.运行项目4.基于SPA项目完成路由4.1.案例实操5.基于

  7. Python灰帽子编程————网页信息爬取

    爬取图片，问题分解：获取网页内容；从网页内容中提取图片地址；通过图片地址，将图片下载到本地。1.相关模块1.1requests模块获取网页内容。requests模块：主要是用来模拟浏览器行为，发送HTTP请求，并处理HTTP响应的功能。importrequests#被认为，最贴近与人的操作的模块importurllib

  8. 【C++】C++ 引用详解 ⑥ ( 普通变量 / 一级指针 / 二级指针 做函数参数的作用 )

    文章目录一、普通变量/一级指针/二级指针做函数参数的作用1、普通变量做函数参数的作用2、一级指针做函数参数的作用3、二级指针做函数参数的作用4、代码示例-二级指针做函数参数的作用一、普通变量/一级指针/二级指针做函数参数的作用1、普通变量做函数参数的作用普通变量的作用:将普通变量传入函数作为参数,则可以在函数中,访问到

  9. 【Java 基础篇】Java 运算符宝典：Java编程的关键

    在Java编程中，运算符是用于执行各种操作的特殊符号。它们可以用于操作各种数据类型，执行算术、逻辑和比较等操作。本篇博客将详细介绍Java中常见的运算符，以及它们的使用和示例。算术运算符算术运算符用于执行基本的数学运算，如加法、减法、乘法和除法。加法运算符（+）加法运算符用于将两个值相加，并返回它们的和。示例：inta