关于 C++ 队列算法，你该了解这些【第二集：链式存储队列】

最新推荐文章于 2024-04-23 13:28:24 发布
最新推荐文章于 2024-04-23 13:28:24 发布
阅读量744 收藏 1
点赞数 1
分类专栏： 算法 文章标签： 队列 指针 链表 数据结构 算法
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/cpp_learner/article/details/105273408
版权

上集回顾：顺序存储队列

第一集：顺序存储队列

观看本系列博文提醒：
你将学会队列的两种最基本的表现形式：顺序存储队列 和 链式存储队列；
一个扩展队列的使用方法：循环队列；
两个企业级队列的应用：线性池中的任务队列 和 优先链式存储队列。

队列的原理

队列是一种受限的线性表，(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out).
在这里插入图片描述
例如上图中，圆球1先进，也是圆球1先出。

队列是一种受限的线性结构

  1. 它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
  2. 生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队。。。。。。

在这里插入图片描述
由上图我们可以知道，队列中有两个“指针”，front指向队首，rear指向队尾；
至于length，他是整个队列的总长度（因为一个队列他是有固定长度的）。

链式存储队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。
为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。

在这里插入图片描述
由上图可知，front指针指向头节点，rear指针指向尾节点。

因为队列的长度是有限的，所以我们可以给队列的长度定义一个宏：
#define MaxSize 5 // 队列的最大容量

队列的定义

typedef int DateType;	// 队列中元素的类型

typedef struct _QNode {	// 节点结构
	DateType date;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePar;	// 节点的指针类型

typedef struct Queue {	// 定义链表队列
	int lenght;		// 队列的长度
	QueuePar front;	// 队头指针
	QueuePar rear;	// 队尾指针
}LinkQueue;

DateType 是队列的存储类型
QueuePar 是节点的指针类型

我们需要先定义出节点，然后才能根据节点定义出链表队列。

队列的初始化

// 队列的初始化
bool inItLinkQueue(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	LQ->lenght = 0;		// 队列长度值为零
	LQ->front = LQ->rear = NULL;	// 把队首和队尾指针指向NULL
	return true;
}

在这里插入图片描述
空队列就是头指针front和尾指针rear都是指向NULL。而且他的长度length等于0.

判断队列是否为空

// 判断队列是否为空
bool estimateLinkQueueEmpty(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (!LQ->front) {
		return true;
	}

	return false;
}

在这里插入图片描述
判断条件也很简单，只需要判断头指针是否指向NULL就可以了。如上图。
因为空队列头指针front和尾指针rear都是指向NULL。而且他的长度length等于0.

判断队列是否已满

// 判断队列是否已满
bool estimateLinkQueuefull(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (LQ->lenght == MaxSize) {
		return true;
	}

	return false;
}

在这里插入图片描述
队列中有一个变量时用于统计队列的元素个数的，只需要将他与队列的存储仅限长度作比较，就可以得出队列是否已满！

入队，将元素插入队列中

// 入队，将元素插入队列中
bool linkQueueInsertValue(LinkQueue*& LQ, DateType date) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueuefull(LQ)) {
		cout << "队列已满！" << endl;
		return false;
	}

	QNode* NQ = new QNode;	// 新建节点
	NQ->date = date;		// 节点的值被赋值
	NQ->next = NULL;		// 因为是最后一个节点，所以next指向NULL

	if (estimateLinkQueueEmpty(LQ)) {	// 如果链表为空
		LQ->front = LQ->rear = NQ;	// 队首指针与队尾指针都要指向新插入的节点
	} else {	// 链表不为空的情况
		LQ->rear->next = NQ;	// 在队尾插入节点(旧队尾节点和新队尾节点连起来)
		LQ->rear = NQ;			// 队尾指向新插入的节点
	}
	LQ->lenght += 1;	// 队列元素加一

	return true;
}

入队他有两种情况：

  1. 队列为空
    在这里插入图片描述
    因为我们传入的是待插入的元素，所以我们先创建一个新的节点。
    队列插入元素后，队首指针和队尾指针都要指向第一个元素（如上图）。
    然后length自增一。

  2. 队列不为空
    在这里插入图片描述
    因为我们传入的是待插入的元素，所以我们先创建一个新的节点.
    头指针不需要动。尾指针rear的next需要指向新插入的节点，然后尾节点在指向新插入的节点。
    然后length自增一。

请注意理解好：插入前尾节点rear的next是指向NULL的，所以得将next指向新插入的节点（将两个节点链起来），然后再将尾节点指向新插入的节点。
这两个步骤弄完后，rear有从新指向新插入的尾节点，那么他的next就为NULL。

出队，删除队首

// 出队，删除队首
bool deleteLinkQueueFront(LinkQueue*& LQ, DateType* date) {	// 参数二：保存删除的数据返回
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！删除失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	*date = LQ->front->date;	// 保存出队的元素返回
	QNode* tem = LQ->front;	// 定义临时节点指向头指针

	LQ->front = tem->next;	// 指向自己的下一个节点
	if (!LQ->front) {	// 如果头指针为NULL，说明队列中已经没有节点了
		LQ->rear = NULL;// 尾指针也要指向NULL
	}
	LQ->lenght -= 1;	// 队列长度要减一

	delete tem;	// 释放掉原来的头指针

	return true;
}

在这里插入图片描述

  1. 首先呢，我们需要创建一个临时的节点，让其指向头节点。
  2. 然后队首指针指向自己的下一个节点。
  3. 我们得先判断现在的队首指针是否为NULL（如果队列只有一个节点的话，那么队首指针和队尾指针都是指向他的，而他们的next下一个节点都是NULL）。所以当条件成立时，队列是已经没有节点的了，所以队尾指针也得指向NULL。
  4. 将临时节点delete释放掉。
  5. 最后再将length自减一。

获取队列的首元素

// 获取队列的首元素
bool aginLinkQueueFrontValue(LinkQueue*& LQ, DateType* date) {	// 参数二：保存首数据返回
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！获取失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	*date = LQ->front->date;
	return true;
}

也就是和删除队首差不多的代码，只是获取元素不需要后面的删除操作而已。

修改队列中任意位置的值

// 修改队列中任意位置的值
bool alterLinkQueueValue(LinkQueue*& LQ, int i, DateType date) {	// 参数二：修改位置；参数三：修改后的值
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！获取失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	if (i < 0 || i > LQ->lenght) {
		cout << "i值不合法！" << endl;
		return false;
	}

	QNode* tem = LQ->front;	// 定义临时节点指向队首指针

	for (int j = 1; j < LQ->lenght + 1; j++) {
		if (i == j) {
			tem->date = date;
			return true;
		}

		tem = tem->next;
	}

	return false;
}

定义临时指针指向队首指针，用于循环遍历。当找到相对位置时，将该位置节点的值修改后就行了。

输出队列中的元素

// 输出队列中的元素
bool linkQueuePrint(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！输出失败！" << endl;
		return false;
	}

	QNode* tem = LQ->front;	// 定义临时节点指向队首指针

	while (tem) {
		cout << tem->date << "\t";
		tem = tem->next;
	}
	cout << endl;

	return true;
}

定义临时节点指向队首指针，使用while循环遍历，将全部元素都输出！

清空队列

// 清空队列
bool clearLinkQueue(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	QNode* tem = LQ->front;

	while (tem) {
		tem = tem->next;
		delete LQ->front;
		LQ->front = tem;
	}

	LQ->front = LQ->rear = NULL;
	LQ->lenght = 0;

	return true;
}

定义临时节点指向队首指针，while循环遍历队列；

  1. 临时节点首先指向自己的下一个节点；
  2. 释放第一个节点；
  3. 再将临时节点赋值给释放掉的空节点；
  4. while循环结束后，还得将队首指针和队尾指针都指向NULL；
  5. 最后再将length赋值0.

测试代码：

#include <iostream>
#include <Windows.h>

using namespace std;

#define MaxSize 5	// 队列的最大容量

typedef int DateType;	// 队列中元素的类型

typedef struct _QNode {	// 节点结构
	DateType date;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePar;

typedef struct Queue {
	int lenght;		// 队列的长度
	QueuePar front;	// 队头指针
	QueuePar rear;	// 队尾指针
}LinkQueue;

// 队列的初始化
bool inItLinkQueue(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	LQ->lenght = 0;		// 队列长度值为零
	LQ->front = LQ->rear = NULL;	// 把队首和队尾指针指向NULL
	return true;
}

// 判断队列是否为空
bool estimateLinkQueueEmpty(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (!LQ->front) {
		return true;
	}

	return false;
}

// 判断队列是否已满
bool estimateLinkQueuefull(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (LQ->lenght == MaxSize) {
		return true;
	}

	return false;
}

// 入队，将元素插入队列中
bool linkQueueInsertValue(LinkQueue*& LQ, DateType date) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueuefull(LQ)) {
		cout << "队列已满！" << endl;
		return false;
	}

	QNode* NQ = new QNode;	// 新建节点
	NQ->date = date;		// 节点的值被赋值
	NQ->next = NULL;		// 因为是最后一个节点，所以next指向NULL

	if (estimateLinkQueueEmpty(LQ)) {	// 如果链表为空
		LQ->front = LQ->rear = NQ;	// 队首指针与队尾指针都要指向新插入的节点
	} else {	// 链表不为空的情况
		LQ->rear->next = NQ;	// 在队尾插入节点(旧队尾节点和新队尾节点连起来)
		LQ->rear = NQ;			// 队尾指向新插入的节点
	}
	LQ->lenght += 1;	// 队列元素加一

	return true;
}

// 出队，删除队首
bool deleteLinkQueueFront(LinkQueue*& LQ, DateType* date) {	// 参数二：保存删除的数据返回
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！删除失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	*date = LQ->front->date;
	QNode* tem = LQ->front;	// 定义临时节点指向头指针

	LQ->front = tem->next;	// 指向自己的下一个节点
	if (!LQ->front) {	// 如果头指针为NULL，说明队列中已经没有节点了
		LQ->rear = NULL;// 尾指针也要指向NULL
	}
	LQ->lenght -= 1;	// 队列长度要减一

	delete tem;	// 释放掉原来的头指针

	return true;
}

// 获取队列的首元素
bool aginLinkQueueFrontValue(LinkQueue*& LQ, DateType* date) {	// 参数二：保存首数据返回
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！获取失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	*date = LQ->front->date;
	return true;
}

// 修改队列中任意位置的值
bool alterLinkQueueValue(LinkQueue*& LQ, int i, DateType date) {	// 参数二：修改位置；参数三：修改后的值
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！获取失败！" << endl;
		return false;
	}

	if (!date) {
		cout << "指针date为空！" << endl;
		return false;
	}

	if (i < 0 || i > LQ->lenght) {
		cout << "i值不合法！" << endl;
		return false;
	}

	QNode* tem = LQ->front;	// 定义临时节点指向队首指针

	for (int j = 1; j < LQ->lenght + 1; j++) {
		if (i == j) {
			tem->date = date;
			return true;
		}

		tem = tem->next;
	}

	return false;
}

// 输出队列中的元素
bool linkQueuePrint(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateLinkQueueEmpty(LQ)) {
		cout << "链表为空！输出失败！" << endl;
		return false;
	}

	QNode* tem = LQ->front;	// 定义临时节点指向队首指针

	while (tem) {
		cout << tem->date << "\t";
		tem = tem->next;
	}
	cout << endl;

	return true;
}

// 清空队列
bool clearLinkQueue(LinkQueue*& LQ) {
	if (!LQ) {
		cout << "队列不存在！" << endl;
		return false;
	}

	QNode* tem = LQ->front;

	while (tem) {
		tem = tem->next;
		delete LQ->front;
		LQ->front = tem;
	}

	LQ->front = LQ->rear = NULL;
	LQ->lenght = 0;

	return true;
}

int main(void) {
	LinkQueue* LQ = new LinkQueue;
	DateType date = 0;

	// 初始化队列
	inItLinkQueue(LQ);

	// 插入元素
	for (int i = 0; i < 7; i++) {
		linkQueueInsertValue(LQ, i*6);
	}
	linkQueuePrint(LQ);

	cout << endl;

	// 出队，删除队首
	if (deleteLinkQueueFront(LQ, &date)) {
		cout << "出队成功！出队元素是：" << date << endl;
	}
	linkQueuePrint(LQ);

	cout << endl;

	// 获取队列的首元素
	if (aginLinkQueueFrontValue(LQ, &date)) {
		cout << "获取成功！队首数据为：" << date << endl;
	}
	linkQueuePrint(LQ);

	cout << endl;

	// 修改队列中任意位置的值
	if (alterLinkQueueValue(LQ, 3, 666)) {
		cout << "修改成功！" << endl;
	}
	linkQueuePrint(LQ);
	cout << endl;

	/*if (alterLinkQueueValue(LQ, 5, 666)) {
		cout << "修改成功！" << endl;
	}
	linkQueuePrint(LQ);
	cout << endl;*/

	// 清空链表
	if (clearLinkQueue(LQ)) {
		cout << "清空成功！" << endl;
	}
	linkQueuePrint(LQ);

	system("pause");
	return 0;
}

总结：
操作并不是很复杂，和单向链表一模一样。
只要不被指针给搞混就好！

注意：由于一篇博客内容太多，所以我将会把他分成几篇进行讲解！

祝各位学习愉快！

下集预告：
你将学会队列的一个企业级应用：线性池中的任务队列；
请持续关注！

C++实现链式队列和线性队列
cloudYun的博客
03-29 385
云开的博客原文：https://chenyunxin.cn/posts/3058917998.html 欢迎访问我的博客交流哟????：https://chenyunxin.cn/ 前言    队列(queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行...
c++循环队列（链式存储）
qq_35901266的博客
09-26 416
#pragma once #include<iostream> #include<string> using namespace std; template<class T> class QuNode { public: T data; QuNode<T>* next; }; template<class T> class LinkQueue { private: QuNode<T>* front,*rear; public:.
第2关：链队列
m0_64562382的博客
01-09 956
第2关：链队列
链式队列
zjy425500828的博客
07-27 203
队列解决问题： 银行3台ATM机，一张卡同时在3台ATM机上取钱。必须通过队列，一台操作完才能在下一台操作。 考虑银行用户众多，用链表。 简单实现方式： queue.h queue.c main.c queue.h #include <stdio.h> #include <stdlib.h> #define datatype int typedef struct queue{ datatype data; struct queue *pNext; }Queue,*PQue
数据结构之线性表(十四)——队列(2 链队列)
daocaoren_的博客
07-27 441
链队列的类型定义 在用户无法估计所用队列的长度时，宜采用链队列，其形式如下图， 与普通线性表不同的是，它定义了头尾两个指针。 普通的链表结点定义如下： typedef struct Qnode { QElemType data; struct Qnode* next; }Qnode, *QueuePtr; 加入头尾指针的链队列定义如下： typedef struct { QueuePtr...
队列顺序存储&链式存储.rar
04-12
本资源“队列顺序存储&链式存储.rar”提供了浙江大学在中国大学MOOC上《数据结构》课程中关于队列实现的源代码，主要包含两种存储方式：顺序存储和链式存储。 队列是一种先进先出（First In First Out, FIFO）的...
C++数据结构之链式队列实现
09-20
在C++中，链式队列可以通过定义一个节点类来存储队列中的元素，并通过头节点和尾节点来追踪队列的状态。以下是对链式队列实现的详细解释： ### 1. 链式队列的基本概念 队列是一种线性数据结构，其操作特性是只允许...
djb.rar_C++_c 循环 队列_数据队列_链式队列_队列 数据结构
09-23
本压缩包“djb.rar”包含C++和C语言实现的几种队列类型，包括顺序队列、顺序循环队列和链式队列。这些源代码为理解队列的数据结构提供了很好的实例。 1. **顺序队列**：顺序队列是最简单的队列实现，它使用数组作为...
数据结构与算法解析：链式存储队列与时间空间复杂度
本文主要介绍了队列的链式存储实现，并给出了C++代码示例，同时探讨了数据结构与算法中的时间复杂度和空间复杂度概念。 在计算机科学中，队列是一种重要的数据结构，它遵循先进先出（FIFO）的原则。在链式存储的...
头歌数据结构循环队列及链队列的基本操作
05-18
头歌数据结构循环队列及链队列的基本操作 第1关循环队列的基本操作 第2关链队列的基本操作 稳过 栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出”的数据结构。队列就是从日常生活中的排队现象抽象出来的线性表。
数据结构：链队列（基本操作）
Atlas！的博客
04-02 874
上次插了个链栈，发现链队列还没有插上来，现在一并附上。 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 #define OVERFLOW -2 const int MAXSIZE = 80; // 预设的存储空间最大容量 typedef int Status;...
单向链(带头)式队列实现
wang_da_ye的博客
04-09 145
#include <stdio.h> #include "queue.h" #include <stdlib.h> /** * 单向链(带头)式队列： 尾入头出 */ typedef struct LinkNode { LinkNode *next; int data; } LinkNode; typedef struct Queue { ...
数据结构之链队列
每天进步一点点。。。的博客
07-19 780
4.13 队列的链式存储结构及实现 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们简称为链队列。我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。        头结点    队头                   队尾 front           a1                      an NULL  rear 空队列时，front和
循环队列基本知识与代码
universe_1207的博客
09-21 1051
循环队列基本知识，相关计算，代码
数据结构（4.队列）
m0_58839943的博客
08-11 426
一、前言 本文将详细介绍队列以及用C++实现队列的封装，代码复制可使用，重点介绍顺序循环队列，链队列只稍加讨论。 二、队列的定义和特点 队列是一种先进先出（First In First Out，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这与日常生活中排队一样，最早进入队列的元素最先离开。在队列中允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。假设队列为Q = (a1，a2，...，an)，那么a1就是队头元素，an则...
《数据结构》（Wrong Question）
最新发布
qiqi_liuliu的博客
04-23 1847
It is used to record some mistakes encoutered in daily life.
【数据结构】队列（循环队列和链队列）详细讲解各种操作
小吉妙妙屋
04-15 5873
详细讲解循环队列和链队列的定义，初始化，入队，出队，遍历等操作
队列操作实现
weixin_43978453的博客
10-08 529
队列的定义： 队列说白了，就是一种**“先进先出”**的储存结构，这跟我们日常生活中的排队现象相类似，如果忘记了，就想想你是怎么排队的，（但是前提是，你不插队） 分类： 链式队列 ----用链式存储实现 静态队列 ----用顺序存储实现 静态队列一般都用循环队列 在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要有front（头指针）和rear（尾指针）...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

cpp_learners

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值