广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言超详细讲解队列的实现及代码
  • 665

0
分享到

C语言超详细讲解队列的实现及代码

2024-04-02 19:04:59 665人浏览 薄情痞子
摘要

目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化  队列销毁  入队列  出队列  队列判空  获取队列元

前言

队列的概念

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

队列和前文所学的栈还是有一定区别的，队列明确指出先进先出。假如说一个队列的入队顺序为A B C D，那么出队顺序一定为A B C D，因为无论你是在A进去再出来，然后B进去再出来接着CD进去再出来或者类似的，都不会影响它最终的出队顺序A B C D。这点和栈还是有区别的，毕竟栈是后进先出。

队列的结构

队列的应用场景

队列：

  • 公平排队
  • 广度优先遍历 ……

栈：

  • 解决括号匹配
  • 逆波兰表达式求解
  • 递归改非递归 ……

队列的实现

  • 在实现之前，首先得考虑用哪种结构好，是用数组结构还是链式结构呢？上文的栈我们使用的是数组结构，难道队列也要用吗？
  • 其实不然。应该使用链式结构。前文栈删除数据不需要挪动数据，使用数组结构即可满足需求，而队列在删除数据时需要把后面的数据挪到前面，使用链式结构非常容易实现，只需改变节点指向即可，而数组结构想要实现挪动数据则非常麻烦。综上，使用链式结构是最优的。此外，单链表即可满足需求，不需要使用其余较为复杂的链式结构。

创建队列结构

思路：

这里要定义两个结构体，除了要定义1个链式结构来记录各个节点外，还要定义一个结构来记录队头和队尾。以此方便后续的队尾入数据，队头出数据。

Queue.h 文件：

//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
 //创建队列节点
typedef struct Queuenode
{
	QDataType data; //存储数据
	struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
	QNode* head; //头指针
	QNode* tail; //尾指针
}Queue;

队列初始化  

思路：

队列可以为空，但是管理头指针和尾指针的结构体不能为空，所以一开始就要断言。其次，在插入数据前，队列肯定是空的，所以直接把头指针和尾指针置空即可。

Queue.h 文件：

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

Queue.c 文件：

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

队列销毁  

思路：

销毁队列就是把队列的每个数据都销毁掉，那么需要遍历链表进行挨个销毁free。首先定义一个cur指针为pq->head，用来保存第一个数据，遍历cur，如果不为空，就free。最后把tail和head置空即可。

Queue.h 文件：

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

Queue.c 文件：

//销毁队列
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;
}

入队列  

思路：

入队列其实很简单，只需要尾插即可，首先要新创建一个节点来保存新插入的数据。但是在尾插之前要考虑如果一开始队列没有数据，为空，那么只需要把head和tail节点指向新节点newnode节点即可。相反的，如果一开始就有数据，那么只需正常尾插把tail的next指向新节点newnode，再把newnode赋给tail即可。

Queue.h 文件：

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

 Queue.c 文件：

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建一个新节点保存数据
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力检测newnode，因为malloc的都要检测
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一开始没有数据，为空的情况
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出队列  

思路：

特殊情况：

这里在删除数据时，首先要考虑特殊情况，当删到只剩一个数据时，再删一次，此时数据是没了，不过head为空了，而tail变成野指针了，为了避免此现象的产生，单独讨论并置空head和tail即可。

一般情况：

此时只需要定义一个next指针保存head的下一个节点，将head移动到next即可，并把旧的head置空。

 Queue.h 文件：

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

Queue.c 文件：

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能为空
	//特殊：当删到head=tail的位置时
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情况
	else
	{
		//保存head的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

队列判空  

思路：

如果head为空或者tail为空都是判空的条件，直接返回即可。

Queue.h 文件：

//判空
bool QueueEmpty(Queue* pq);

Queue.c 文件：

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

获取队列元素个数  

思路：

求元素个数其实不难，只需要定义一个cur指针为第一个数据pq->head，定义变量size来记录个数。依次遍历cur，不为空，size就++。这种遍历的思想不复杂，但时间复杂度达到O(N)，不是太好，想要O(1)的话可以直接在当初定义结构体时多定义一个size变量，专门用来记录有效元素个数，每次入队列size++，出队列size--。这样实现是比较好的，不过为了封装成一个独立模块，还是采用遍历的方式。如下：

Queue.h 文件：

//获取有效元素个数
size_t QueueSize(Queue* pq);

Queue.c 文件：

//获取有效元素个数
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

获取队列头部元素  

思路：

首先要断言头部不能为空，如果头部都为空了，那还怎么能获得头部元素，其次直接返回头部head的数据即可。

Queue.h 文件：

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

Queue.c 文件：

//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //头部不能为空
	return pq->head->data;
}

获取队列尾部元素  

思路：

有了获取队头元素的经验，队尾就更简单了，把head换位tail即可，结构与上文一样。

Queue.h 文件：

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

Queue.c 文件：

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能为空
	return pq->tail->data;
}

总代码

Queue.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
 //创建队列节点
typedef struct QueueNode
{
	QDataType data; //存储数据
	struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
	QNode* head; //头指针
	QNode* tail; //尾指针
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
 
//销毁队列
void QueueDestory(Queue* pq);
 
//入队列
void QueuePush(Queue* pq, QDataType x);
 
//出队列
void QueuePop(Queue* pq);
 
//判空
bool QueueEmpty(Queue* pq);
 
//获取有效元素个数
size_t QueueSize(Queue* pq);
 
//获取队头元素
QDataType QueueFront(Queue* pq);
 
//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#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));
	//暴力检测newnode，因为malloc的都要检测
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一开始没有数据，为空的情况
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
 
//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能为空
	//特殊：当删到head=tail的位置时
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情况
	else
	{
		//保存head的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
 
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
 
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
 
//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //头部不能为空
	return pq->head->data;
}
 
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能为空
	return pq->tail->data;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	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");
}
int main()
{
	TestQueue();
	return 0;
}

到此这篇关于C语言超详细讲解队列的实现及代码的文章就介绍到这了,更多相关C语言 队列的实现内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言超详细讲解队列的实现及代码

本文链接: https://www.lsjlt.com/news/145558.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言超详细讲解队列的实现及代码
    目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化  队列销毁  入队列  出队列  队列判空  获取队列元...
    99+
    2022-11-13
  • C语言超详细讲解栈的实现及代码
    目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码Stack.h 文件Stack.c 文件Test.c 文件前言 栈...
    99+
    2022-11-13
  • C语言超详细讲解栈与队列实现实例
    目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3...
    99+
    2022-11-13
  • C语言示例代码讲解栈与队列
    目录栈栈的定义顺序栈顺序栈的定义顺序栈的初始化顺序栈的入栈顺序栈的出栈取顺序栈的栈顶元素链栈队列队列的定义队列的顺序表达与实现队列顺序存储结构假溢出循环队列循环队列的初始化循环队列的...
    99+
    2022-11-13
  • C++ 栈和队列的实现超详细解析
    目录1、栈的介绍：2、栈的常用接口实现 3、队列的介绍4、队列的常用接口实现 可算是把链表给结束了，很多小伙伴已经迫不及待想看到栈和队列了，那么它来了！相信有了顺...
    99+
    2022-11-13
  • C语言超详细讲解猜数字游戏的实现
    目录rand函数srand函数时间戳完整代码与程序运行图rand函数 先看一下下面这张图： 通过这张图我们可以了解到rand函数的返回值是int类型，形参为空，它的头文件<s...
    99+
    2022-11-13
  • C语言简明讲解队列的实现方法
    目录前言队列的表示和实现队列的概念及结构代码实现束语前言 大家好啊，我又双叒叕来水博客了，道路是曲折的，前途是光明的，事物是呈螺旋式上升的，事物最终的发展结果还是我们多多少少能够决定...
    99+
    2022-11-13
  • C语言超详细讲解指针的使用
    目录指针概述自身类型指向类型代码例子数值型指针字符型指针单字符字符数组字符串型指针字符数组总结指针概述 C语言中指针也可以认为是一种类型，不同于数值型和字符型的类型。推演过去指针变量...
    99+
    2022-11-13
  • C语言超详细讲解文件的操作
    目录一、为什么使用文件二、什么是文件1.程序文件2.数据文件3.文件名三、文件指针四、文件的打开和关闭五、文件的顺序读写六、文件的随机读写fseekftellrewind七、文件结束...
    99+
    2022-11-13
  • C语言实现队列的示例详解
    目录前言一. 什么是队列二. 使用什么来实现栈三. 队列的实现3.1头文件3.2 函数的实现四.完整代码前言 前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链表，双向循环链...
    99+
    2022-11-13
  • C++代码实现链队列详解
    目录主要功能：完整代码展示：总结主要功能： 初始化、入队、出队、取队头元素、销毁队列、输出队列 完整代码展示： #include <iostream> using n...
    99+
    2022-11-12
  • C语言详解链式队列与循环队列的实现
    目录队列的实现链式队列链式队列的定义链式队列的实现循环队列循环队列的定义循环队列的实现队列的实现 队列是一种先进先出（First in First Out）的线性表，简称FIFO。与...
    99+
    2022-11-13
  • C语言超详细讲解getchar函数的使用
    目录一、getchar 函数二、缓冲区1、什么是缓冲区2、为什么要存在缓冲区3、缓冲区的类型4、缓冲区的刷新三、getchar 函数的正确使用1、getchar 的换行问题2、get...
    99+
    2022-11-13
  • C语言折半查找法的超详细讲解
    折半查找法仅适用于对已有顺序的数组、数据进行操作！！！（从小到大）自我总结：折半查找法就是相当于（通过改变low或high的大小）把中间位置指到了key那个数那里，所以mid应该处于...
    99+
    2022-11-13
  • C语言数据的存储超详细讲解上篇
    目录前言1、数据类型介绍类型的基本归类2、整形在内存中的存储2.1 原码、反码、补码2.2 大小端介绍2.2.1 什么是大小端2.2.2 大端和小端意义2.2.3 写程序判断字节序总...
    99+
    2022-11-13
  • C语言超详细讲解宏与指针的使用
    目录1、关于define2、初识指针（1）内存（2）示例（3）指针的使用示例（4）指针变量的大小1、关于define define是一个预处理指令，有两种用法，一种是用define定...
    99+
    2022-11-13
  • C语言超详细讲解函数指针的运用
    目录前言计算器的例子回调函数转移表前言 前面我们学习了各种各样的指针类型，有些指针可以说是稀奇百怪，特别是函数指针，有些朋友可能觉得，函数指针有些多余，调用函数为什么要用指针调用，直...
    99+
    2022-11-13
  • C语言超详细讲解指向函数的指针
    目录一、函数的指针二、指向函数的指针变量三、调用函数的两种方式四、指向函数的指针的作用五、用指向函数的指针作函数参数(重点)六、为什么要将指向函数的指针变量作为函数的形参(重点)一、...
    99+
    2022-11-13
  • C语言栈与队列相互实现详解
    目录一、本章重点二、队列实现栈三、栈实现队列四、解题思路总结一、本章重点 用两个队列实现栈用两个栈实现队列解题思路总结 二、队列实现栈  我们有两个队列：  ...
    99+
    2022-11-13
  • C语言 队列的实现全解析
    目录队列的实现基本概念创建结构体初始化结构体销毁队列结构体入队出队判断队列是否为空访问对头的值访问队尾的值返回队列的长度Queue.hQueue.cTest.c队列的实现 基本概念 ...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作