队列的实现（使用链表）

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。
P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

  

目录

  • 1、队列的概念
  • 2、队列的链表实现方法
    • 2.1 前言
    • 2.2 正文
      • 2.2.1 队列的初始化
      • 2.2.2 队列的销毁
      • 2.2.3 队列插入信息
      • 2.2.4 队列删除信息
      • 2.2.5 判断队列是否为空
      • 2.2.6 队列中数据个数
      • 2.2.7 队首的数据
      • 2.2.8 队尾的数据
  • 3、完整代码展示
  • 4、结语

1、队列的概念


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

在这里插入图片描述


  对于队列的实现我们可以选择数组和链表的形式，但如果是数组的话，静态和动态数组都有它的局限性，故本文主要拟使用链表的形式来实现队列。
  下面进入正文。




2、队列的链表实现方法

2.1 前言


  构建队列的需求有三个文件，包括Queue.c（用来书写逻辑的内容）、Queue.h（用来书写逻辑的声明）、test.c（用来测试我们所书写的代码）。

2.2 正文


  和我们书写代码的规则一致，使用链表实现队列时，往往会需要使用到结构体变量，在通常情况下我们都会将其进行重命名，以方便我们后续代码的使用。
  在此我们书写一个结构体变量QueueNode来表示链表中我们的节点，并对其重命名，结果如下： 
typedef struct QueueNode
{
	int val;//对类型重命名后此行代码改为QDataType val;
	struct QueueNode* next;
}QNode,* pQNode;

  因为在实际使用中我们队列中的元素往往是多样的，故在此对类型进行重命名，以便后续需要更改时更加快捷，结果如下： 
typedef int QDataType;

  当我们写完节点的结构体后，思考一下，如果需要实现队列的功能，“先进先出”，那么就需要用两个指针来分别标记头节点和尾节点。所以我们如果要实现插入数据的功能时，就要将函数写成以下形式。 
void QueuePush(pQNode* phead,pQNode* ptail,QDataType x);

  而后面每个函数都需要传入两个参数，并且还用到了二级指针，十分容易出现错误，故我们可以将头节点，尾节点分装成一个结构体，来表示整个队列的信息，并且可以额外加入一个变量 size 来记录队列中的数据个数。故此结构体如下，同样进行重命名以便后续使用：

typedef struct Queue
{
	pQNode phead;
	pQNode ptail;
	int size;
}Queue, * pQueue;

  下面我们就可以在头文件中一次性将需要实现的接口函数写出来，以便我们在源文件中实现。 
//初始化队列信息
void QueueInit(pQueue pq);

//销毁队列
void QueueDestroy(pQueue pq);

//队列插入信息
void QueuePush(pQueue pq, QDataType x);

//队列消除信息
void QueuePop(pQueue pq);

//队列判断是否为空
bool QueueEmpty(pQueue pq);

//队列数据个数查询
int QueueSize(pQueue pq);

//队列队首的数据
QDataType QueueFront(pQueue pq);

//队列队尾的数据
QDataType QueueBack(pQueue pq);

  下面进入相关接口的函数实现。

2.2.1 队列的初始化


  对于栈的初始化，代码如下： 
void QueueInit(pQueue pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.2.2 队列的销毁


  对于栈的销毁，代码如下： 
void QueueDestroy(pQueue pq)
{
	assert(pq);
	pQNode cur = pq->phead;
	while(cur)
	{
		pQNode next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.2.3 队列插入信息


  队列插入信息代码如下： 
void QueuePush(pQueue pq, QDataType x)
{
	assert(pq);
	pQNode newnode = (pQNode)malloc(sizeof(QNode));
	if(newnode == NULL)
	{
		perror("QueuePush:malloc");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	if(pq->ptail == NULL)//只有一个节点
	{
		pq->ptail = pq->phead = newnode;
	}
	else//多个节点
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

2.2.4 队列删除信息


  队列删除信息代码如下： 
void QueuePop(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	if(pq->phead == pq->ptail)//只有一个节点
	{	
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}	
	else//多个节点
	{
		pQNode tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	pq->size--;
}

2.2.5 判断队列是否为空


  判断队列是否为空代码如下： 
bool QueueEmpty(pQueue pq)
{
	assert(pq);
	return pq->size == 0;
}

2.2.6 队列中数据个数


  队列中数据个数的代码如下： 
int QueueSize(pQueue pq)
{
	assert(pq);
	return pq->size;
}

2.2.7 队首的数据


  取队首数据代码如下 
QDataType QueueFront(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->phead->val;
}

2.2.8 队尾的数据


  取队尾数据代码如下 
QDataType QueueBack(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->ptail->val;
}




3、完整代码展示


  Queue.h: 
#pragma once

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

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode, * pQNode;

typedef struct Queue
{
	pQNode phead;
	pQNode ptail;
	int size;
}Queue, * pQueue;

//队列初始化
void QueueInit(pQueue pq);

//队列销毁
void QueueDestroy(pQueue pq);

//队列插入数据
void QueuePush(pQueue pq, QDataType x);

//队列删除数据
void QueuePop(pQueue pq);

//队列数据个数
int QueueSize(pQueue pq);

//队列判空
bool QueueEmpty(pQueue pq);

//取队列头数据
QDataType	QueueFront(pQueue pq);

//取队列尾数据
QDataType QueueBack(pQueue pq);

  Queue.c:

#include "Queue.h"

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

//队列销毁
void QueueDestroy(pQueue pq)
{
	assert(pq);
	pQNode cur = pq->phead;
	while (cur)
	{
		pQNode next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队列插入数据
void QueuePush(pQueue pq, QDataType x)
{
	assert(pq);
	pQNode tmp = (pQNode)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("QueuePush:malloc");
		return;
	}
	tmp->next = NULL;
	tmp->val = x;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = tmp;
	}
	else
	{
		pq->ptail->next = tmp;
		pq->ptail = tmp;
	}
	pq->size++;
}

//队列删除数据
void QueuePop(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		pQNode tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	pq->size--;
}

//队列数据个数
int QueueSize(pQueue pq)
{
	assert(pq);
	return pq->size;
}

//队列判空
bool QueueEmpty(pQueue pq)
{
	assert(pq);
	return pq->size == 0;
}

//取队列头数据
QDataType	QueueFront(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->phead->val;
}

//取队列尾数据
QDataType QueueBack(pQueue pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->ptail->val;
}

  test.c:

#include "Queue.h"

int main()
{
	Queue s;
	QueueInit(&s);
	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);
	printf("%d\n", QueueFront(&s));
	printf("%d\n", QueueBack(&s));
	QueuePop(&s);
	printf("%d\n", QueueFront(&s));
	printf("%d\n", QueueSize(&s));
	QueuePop(&s);
	QueuePop(&s);
	printf("%d\n", QueueSize(&s));
	if (QueueEmpty(&s))
		printf("空了\n");
	else
		printf("有东西\n");
	QueuePop(&s);
	if (QueueEmpty(&s))
		printf("空了\n");
	else
		printf("有东西\n");
	QueueDestroy(&s);

	return 0;
}




4、结语


  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享，学习路漫漫，如有错误，感谢指正。
  如需引用，注明地址。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/610588.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

苹果公司因iPad广告争议而道歉，承认“未达标”｜TodayAI

苹果公司因iPad广告争议而道歉，承认“未达标”｜TodayAI

周二&#xff0c;苹果公司发布了一则新的iPad Pro广告&#xff0c;引起了广泛争议&#xff0c;该公司随后发表道歉声明&#xff0c;承认这则广告“未达标”。这则名为“压碎&#xff01;”的广告意图展示全新的M4芯片iPad Pro的创意潜力&#xff0c;但却因其表现方式而备受批评…
阅读更多...
服务器直连电脑（盒子直连电脑）电脑需要设置为固定ip才能访问盒子

服务器直连电脑（盒子直连电脑）电脑需要设置为固定ip才能访问盒子

文章目录 现象盒子设置为固定ip&#xff0c;pc设置成固定ip&#xff08;以太网网卡&#xff0c;realtak那个&#xff0c;不是tap-windows那个&#xff0c;tap-windows不用管&#xff09;&#xff0c;在pc上用ip搜索工具搜索&#xff0c;可以搜到盒子ip。盒子设置为固定ip&#…
阅读更多...
phpstudy靶场访问显示404 Not Found

phpstudy靶场访问显示404 Not Found

涉及靶场 upload-labd sqli-labs pikachu dvwa 以及所有部署在phpstudy中的靶场 一、检查phpstduy设置 localhost——管理——修改 1、根目录&#xff08;默认设置&#xff0c;不要改&#xff09; localhost这个域名必须保留&#xff0c;并且把根目录设置为phpstudy的WWW文…
阅读更多...
性能测试工具——wrk的安装与使用

性能测试工具——wrk的安装与使用

前言 想和大家来聊聊性能测试&#xff0c;聊到了性能测试必须要说的是性能测试中的工具&#xff0c;在这些工具中我今天主要给大家介绍wrk。 ​介绍 wrk是一款开源的性能测试工具 &#xff0c;简单易用&#xff0c;没有Load Runner那么复杂&#xff0c;他和 apache benchmar…
阅读更多...
flutter开发实战-webview_flutter 4.x版本使用

flutter开发实战-webview_flutter 4.x版本使用

flutter开发实战-webview_flutter 4.x版本使用 在之前使用的webview_flutter版本是3.x的&#xff0c;升级到4.x后&#xff0c;使用方式有所变化。 一、webview_flutter 在工程的pubspec.yaml中引入插件 webview_flutter: ^4.4.2二、使用webview_flutter 在4.x版本中&#…
阅读更多...
umi6.x + react + antd的项目增加403（无权限页面拦截），404，错误处理页面

umi6.x + react + antd的项目增加403（无权限页面拦截），404，错误处理页面

首先在src/pages下创建403&#xff0c;404&#xff0c;ErrorBoundary 403 import { Button, Result } from antd; import { history } from umijs/max;const UnAccessible () > (<Resultstatus"403"title"403"subTitle"抱歉&#xff0c;您无权…
阅读更多...
如何使用Python为Excel文件添加预设文档属性和自定义文档属性

如何使用Python为Excel文件添加预设文档属性和自定义文档属性

向Excel文件添加文档属性是专业地组织和管理电子表格数据的关键步骤。这些属性&#xff0c;如标题、作者、主题和关键词&#xff0c;增强了文件的元数据&#xff0c;使得在大型数据库或文件系统中跟踪、排序和搜索文档变得更加容易。通过包含这些信息&#xff0c;您不仅提高了文…
阅读更多...
C++map和set(个人笔记)

C++map和set(个人笔记)

Cmap和set 1.set1.1set的使用1.1.1 set的模板参数列表1.1.2set的构造1.1.3set的迭代器1.1.4 set的容量1.1.5 set修改操作1.1.6 set的具体使用例子 2.map2.1map的使用2.1.1map的模板参数列表2.1.2map的构造2.1.3map的迭代器2.1.4 map的容量与元素访问2.1.5 map中元素的修改2.1.6…
阅读更多...
资源管理游戏模版进入The Sandbox

资源管理游戏模版进入The Sandbox

我们非常高兴地向您介绍 Game Maker 的最新模板&#xff1a;资源管理游戏&#xff01; 这一全新的模板让您能够深入身临其境的游戏体验中&#xff0c;同时掌握令人兴奋的新机制。通过揭开模板的神秘面纱&#xff0c;您可以锤炼您的游戏设计技能。 什么是资源管理游戏&#xff1…
阅读更多...
【C语言和Java的对比学习】2（布尔类型、运算符、程序逻辑控制）

【C语言和Java的对比学习】2（布尔类型、运算符、程序逻辑控制）

【C语言和Java的对比学习】2&#xff08;布尔类型、运算符、程序逻辑控制&#xff09; 1. 布尔类型变量2. 逻辑运算符的短路问题2.1 &&和||使用举例2.2 &和|的使用举例 3.位移运算4. switch语句 1. 布尔类型变量 下面我们直接先看下面一组代码的对比图。 注意&am…
阅读更多...
马化腾用了一年多的时间，告诉所有人，视频号小店是新风口！

马化腾用了一年多的时间，告诉所有人，视频号小店是新风口！

大家好&#xff0c;我是电商笨笨熊 当腾讯说出自己要做电商的时候&#xff0c;所有人都在说&#xff0c;根本不可能&#xff1b; 甚至在视频号小店正式推出之后&#xff0c;依旧有人说&#xff0c;腾讯做电商就是笑话&#xff1b; 一个“抄”过来的项目&#xff0c;毫无特色…
阅读更多...
whisper之初步使用记录

whisper之初步使用记录

文章目录 前言 一、whisper是什么&#xff1f; 二、使用步骤 1.安装 2.python调用 3.识别效果评估 4.一点封装 5.参考链接 总结 前言 随着AI大模型的不断发展&#xff0c;语音识别等周边内容也再次引发关注&#xff0c;通过语音转文字再与大模型交互&#xff0c;从而…
阅读更多...
数据库入门（sql文档+命令行）

数据库入门（sql文档+命令行）

一.基础知识 1.SQL&#xff08;Structured Query Language&#xff09;结构化查询语言分类&#xff1a; DDL数据定义语言用来定义数据库对象&#xff1a;数据库、表、字段DML数据操作语言对数据库进行增删改查DQL数据查询语言查询数据库中表的信息DCL数据控制语言用来创建数据…
阅读更多...
用数字化武装文物——博物馆文物管理平台

用数字化武装文物——博物馆文物管理平台

一、引言 在数字化与信息化高速发展的今天&#xff0c;博物馆文物管理面临着前所未有的挑战与机遇。随着科技的不断进步&#xff0c;传统的管理方式已难以满足现代博物馆对文物管理和保护的需求。在此情况下&#xff0c;博物馆文物管理平台以其强大的功能&#xff0c;正成为文物…
阅读更多...
快速理解SPI通信协议（超简单）

快速理解SPI通信协议（超简单）

SPI通信协议 一、SPI协议介绍二、发送数据三、读数据注意 一、SPI协议介绍 SPI是一种全双工的串行通信协议 他有四条线 SCLK&#xff08;Serial Clock&#xff09;&#xff1a;时钟线 MOSI&#xff08;Master Output, Slave Input&#xff09;&#xff1a;关键字母"O&q…
阅读更多...
Highcharts 实现3D饼图 tooltip轮播

Highcharts 实现3D饼图 tooltip轮播

实现3D饼图&#xff0c;并且轮播显示tooltip 自定义toottip样式 import Highcharts from highcharts; import highcharts from highcharts; import highcharts3d from highcharts/highcharts-3d;highcharts3d(Highcharts); highcharts3d(highcharts); import { useEffect, use…
阅读更多...
Docker安装达梦数据库

Docker安装达梦数据库

1.确保已安装Docker 可参考&#xff1a;Linux安装Docker-CSDN博客 2.上传dm镜像并导入安装包 可以从&#xff1a;产品下载 | 达梦数据库下载dm镜像&#xff0c;如下图&#xff1a; docker load -i dm8_20230808.tar 3.导入后查看镜像 docker images 4.启动容器 docker run …
阅读更多...
工业数据采集软件 高效的数字化信息管理系统

工业数据采集软件 高效的数字化信息管理系统

近年来&#xff0c;随着产线自动化程度的提升&#xff0c;越来越多的工业设备被运用到自动化生产中&#xff0c;产线中各位置所产生的数据也越来越多&#xff0c;每个设备又都是独立的&#xff0c;如何将其整合&#xff0c;进行系统化查看处理&#xff0c;就是工业数据采集软件…
阅读更多...
数据结构05：树与二叉树 习题01[C++]

数据结构05：树与二叉树 习题01[C++]

考研笔记整理&#xff0c;本篇作为树与二叉树的基本概念习题&#xff0c;供小伙伴们参考~&#x1f95d;&#x1f95d; 之前的博文链接在此&#xff1a;数据结构05&#xff1a;树与二叉树[C]-CSDN博客~&#x1f95d;&#x1f95d; 第1版&#xff1a;王道书的课后习题~&#x1…
阅读更多...
有什么方便实用的黏土特效教程？6个软件教你快速进行特效制作

有什么方便实用的黏土特效教程？6个软件教你快速进行特效制作

有什么方便实用的黏土特效教程&#xff1f;6个软件教你快速进行特效制作 作为时尚小达人&#xff0c;你自己是否想要制作出属于自己的黏土特效照片呢&#xff1f;比如下面几种。 看到这些黏土特效软件有没有心动&#xff0c;下面我也为大家详细的介绍一下可以制作出对应特效的…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站