1. Toy模板网首页
  2. > Toy博客

【数据结构】C语言队列(详解)

8月前 作者：Dream_Chaser～ 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】C语言队列(详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言:

💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥

✨✨专栏:http://t.csdn.cn/oXkBa

⛳⛳本篇内容:c语言数据结构--C语言实现队列

目录

一.队列概念及结构

1.1队列的概念

1.2队列的结构

二.队列的实现

2.1头文件

2.2链式队列的结构定义

2.3队列接口的定义

2.4初始化队列

2.5判断队列是否为空

2.6销毁队列

2.7队尾入队列

2.8队头出队列

2.9获取队列头部元素

2.10获取队列队尾元素

2.11获取队列中有效元素个数

2.12打印队列元素

Test.c

Queue.h

Queue.c

一.队列概念及结构

1.1队列的概念

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

1.2队列的结构

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

二.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.1头文件

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

2.2链式队列的结构定义

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

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.

  QueueNode结构体表示队列中的节点，每个节点包含一个数据项 data 和一个指向下一个节点的指针 next。Queue结构体表示整个队列，包含指向队列头部和尾部节点的指针 phead 和 ptail，以及记录队列大小的变量 size

2.3队列接口的定义

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

void QueueDestroy(Queue* pq);// 销毁队列

void QueuePush(Queue* pq, QDataType x);// 队尾入队列

void QueuePop(Queue* pq);// 队头出队列

QDataType QueueFront(Queue* pq);// 获取队列头部元素

QDataType QueueBack(Queue* pq);// 获取队列队尾元素

int QueueSize(Queue* pq);// 获取队列中有效元素个数

bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

2.4初始化队列

void QueueInit(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	pq->phead=NULL; //将队列的头指针置为空
	pq->ptail = NULL;//将队列的尾指针置为空
	pq->size = 0;// 将队列的头指针置为空
}

2.5判断队列是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	//方法一,将队列的头指针以及尾指针置空
	//return pq->phead = NULL && pq->ptail==NULL;
	
	//方法二,将队列的有效元素置空
	return pq->size == 0;
}

2.6销毁队列

代码解析:

  1. assert(pq) 用于断言 pq 指针不为空，确保传入的指针有效。

  2. 创建一个指针 cur，并将其初始化为队列的头指针 pq->phead。

  3. 进入循环，遍历队列中的每个节点。

  4. 在循环中，首先保存当前节点的下一个节点指针为 next，以便在释放当前节点后能够访问下一个节点。

  5. 使用 free(cur) 释放当前节点的内存。

  6. 将指针 cur 移动到下一个节点，即 cur = next。

  7. 循环继续，直到遍历完队列中的所有节点。

  8. 在循环结束后，将队列的头指针和尾指针 pq->phead、pq->ptail 都置为空，表示队列已经为空。

  9. 将队列的大小 pq->size 置为 0，表示队列中没有元素。

void QueueDestroy(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
	while (cur)
	{
		QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
		free(cur);// 释放当前节点的内存
		cur = next;// 将指针 cur 移动到下一个节点
	}
	pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
	pq->size = 0;// 将队列的大小置为0
}

2.7队尾入队列

第一种情况:尾插第一个队列元素

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

第二种情况:已有元素前提下尾插节点

先尾插节点，后把新节点的地址给ptail(让ptail指向新节点)

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点

	if (newnode == NULL)
	{
		perror("malloc fail\n");// 检查内存分配是否成功
		return;
	}
	newnode->data = x;// 设置新节点的数据为传入的元素值
	newnode->next = NULL;// 将新节点的指针域置空

	//一个节点
	
	if (pq->ptail == NULL)// 判断队列是否为空
	{
		assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
		pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
	}
    //多个节点
	else
	{
		pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
		pq->ptail = newnode;// 更新队列的尾指针为新节点
	}
	pq->size++;// 增加队列的大小计数
}

代码执行: 

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.8队头出队列

第一种:队列只有一个元素时

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

第二种:队列有多个元素时

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

void QueuePop(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->phead);// 检查队列的头指针是否存在
	//1.一个节点
	if (pq->phead->next == NULL) // 队列只有一个节点的情况
	{
		free(pq->phead); // 释放队列头节点的内存
		pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
	}
    //2.多个节点
	else
	{
		QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
		free(pq->phead);// 释放队列头节点的内存
		pq->phead = next;// 更新队列的头指针为下一个节点
	}
	pq->size--;//减少队列的大小计数
}

代码执行: 

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.9获取队列头部元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->phead);// 检查队列的头指针是否存在
 
	return pq->phead->data;// 返回队列头节点的数据
}

代码执行:

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.10获取队列队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);// 检查队列是否非空
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->ptail);// 检查队列的尾指针是否存在
	
	return pq->ptail->data;//返回队列尾节点的数据
}

代码执行:

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.11获取队列中有效元素个数

int QueueSize(Queue* pq)
{
	assert(pq);//检查指针是否为空

	return pq->size;//返回队列的大小（元素个数）
}

代码执行:

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

2.12打印队列元素

void QPrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	QNode* next = cur;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

代码执行: 

【数据结构】C语言队列(详解),C--数据结构,数据结构,c语言,算法,链表,开发语言,笔记

Test.c

#include"Queue.h"
void TestQueue1()//元素入队列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,1);
	QueuePush(&q,2);	
	//printf("%d ", QueueFront(&q));
	//QueuePop(&q);
	QueuePush(&q,3);
	QueuePush(&q,4);
	//printf("Size:%d\n", QueueSize(&q));
	//QPrint(&q);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}
void TestQueue2()//元素出队列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	
	printf("\n");
}
void TestQueue3()//获取队列头部和尾部元素,和队列元素个数
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("队列头部元素:%d\n",QueueFront(&q));
	printf("队列尾部元素:%d\n", QueueBack(&q));
	printf("Size:%d\n", QueueSize(&q));

	/*while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}*/
	printf("\n");
}
void TestQueue4()//打印队列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QPrint(&q);
	printf("\n");
}
int main()
{
	//TestQueue1();//元素入队列
	//TestQueue2();//元素出队列
	//TestQueue3();//获取队列头部和尾部元素,和队列元素个数
	TestQueue4();
}

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{	
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.

void QueueInit(Queue* pq);// 初始化队列
void QueueDestroy(Queue* pq);// 销毁队列
void QueuePush(Queue* pq, QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
int QueueSize(Queue* pq);// 获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	pq->phead=NULL; // 将队列的头指针置为空
	pq->ptail = NULL;// 将队列的头指针置为空
	pq->size = 0;// 将队列的头指针置为空
}

void QPrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	QNode* next = cur;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

void QueueDestroy(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
	while (cur)
	{
		QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
		free(cur);// 释放当前节点的内存
		cur = next;// 将指针 cur 移动到下一个节点
	}
	pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
	pq->size = 0;// 将队列的大小置为0
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点

	if (newnode == NULL)
	{
		perror("malloc fail\n");// 检查内存分配是否成功
		return;
	}
	newnode->data = x;// 设置新节点的数据为传入的元素值
	newnode->next = NULL;// 将新节点的指针域置空

	//一个节点
	//多个节点
	if (pq->ptail == NULL)// 判断队列是否为空
	{
		assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
		pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
	}
	else
	{
		pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
		pq->ptail = newnode;// 更新队列的尾指针为新节点
	}
	pq->size++;// 增加队列的大小计数
}

void QueuePop(Queue* pq)
{
	assert(pq);// 检查指针是否为空
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->phead);// 检查队列的头指针是否存在
	//1.一个节点
	if (pq->phead->next == NULL) // 队列只有一个节点的情况
	{
		free(pq->phead); // 释放队列头节点的内存
		pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
	}
	else
	{
		//头删
		QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
		free(pq->phead);// 释放队列头节点的内存
		pq->phead = next;// 更新队列的头指针为下一个节点
	}
	pq->size--;//减少队列的大小计数
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->phead);// 检查队列的头指针是否存在
 
	return pq->phead->data;// 返回队列头节点的数据
}
  
QDataType QueueBack(Queue* pq)
{
	assert(pq);// 检查队列是否非空
	assert(!QueueEmpty(pq));// 检查队列是否非空
	assert(pq->phead);// 检查队列的头指针是否存在
	
	return pq->ptail->data;//返回队列尾节点的数据
}

int QueueSize(Queue* pq)
{
	assert(pq);//检查指针是否为空

	return pq->size;//返回队列的大小（元素个数）
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	//方法一,将队列的头指针以及尾指针置空
	//return pq->phead = NULL && pq->ptail==NULL;
	
	//方法二,将队列的有效元素置空
	return pq->size == 0;
}

        本篇结束，如有错误，欢迎大家指正，感谢来访！文章来源地址https://www.toymoban.com/news/detail-689153.html

到了这里，关于【数据结构】C语言队列(详解)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构与算法》之队列与链表复习

    《数据结构与算法》之队列与链表复习

    我们在上一次学习了堆栈的数据结构以后，可以了解到它是受限制的操作，比如我们操作只能在栈顶，现在我们要学习的东西叫做队列，它也是受限制的一种数据结构，它的特点是队头只出数据，而队尾只入数据， 它的结构就和它的名字，像我们平时排队一样先来的人肯定要

    2024年02月08日
    浏览(39)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(44)
  • 【数据结构】C语言队列(详解)

    【数据结构】C语言队列(详解)

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文件 2.2链式队列的结构定义 2.3队列接口的定义 2.4初始化队列 2.5判断队列

    2024年02月10日
    浏览(39)
  • 【数据结构】队列---C语言版（详解！！！）

    【数据结构】队列---C语言版（详解！！！）

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

    2024年02月10日
    浏览(45)
  • 数据结构-循环队列详解（c语言版）

    数据结构-循环队列详解（c语言版）

    目录 一、什么是循环队列？ 二、特点 三、基本运算 四、代码实现  1、初始化 2、入队 3、出队 4、队满？ 5、队空？  6、输出队列 7、队列大小 8、获取队首元素 五、队列应用场景 六、完整代码 1、完整代码 2、运行结果 七、总结 前言 相比于链队列， 循环队列 有着内存固

    2024年01月20日
    浏览(51)
  • 【算法与数据结构】队列的实现详解

    【算法与数据结构】队列的实现详解

    队列的概念： 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 队列特征如

    2024年04月13日
    浏览(38)
  • （详解)数据结构-----------栈与队列 c语言实现

    （详解)数据结构-----------栈与队列 c语言实现

    本章将会详细讲解以下知识点： 目录 一：栈         1：栈的定义，栈的特点         2：用什么结构来实现栈与原因的分析?         3:  (超详解)栈的常用接口并且附上测试用例 二:队列         1:队列的定义，队列的特点         2：用什么结构来实现队列与原因的分析

    2024年02月11日
    浏览(40)
  • 数据结构之队列详解（C语言手撕）

    数据结构之队列详解（C语言手撕）

    🎉个人名片： 🐼作者简介：一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉：GOTXX 🐼个人WeChat：ILXOXVJE 🐼本文由GOTXX原创，首发CSDN🎉🎉🎉 🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句：如果没有特别幸运，那就请特

    2024年03月10日
    浏览(59)
  • 头歌（C语言）-数据结构与算法-队列-第1关：实现一个顺序存储的队列

    头歌（C语言）-数据结构与算法-队列-第1关：实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务：实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数，以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(111)

  • 【C/C++数据结构与算法】C语言栈与队列

    目录 一、栈 二、队列 三、循环队列 特性： 顺序存储，后进先出 优点是可随机访问，尾部增删效率高 缺点是可能会浪费空间，不知道头部增删 特性： 链式存储，先进先出 优点是无空间浪费，头部增删效率高 缺点是不能随机访问，尾部增删效率低 特性： 顺序存储，先进先

    2024年02月09日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包