探索数据结构：链式队与循环队列的模拟、实现与应用

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 队列的定义

队列（queue）是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。其严格遵循先进先出（First In First Out）的规则，简称FIFO。

img

img

  • 队头（Front）：允许删除的一端，又称队首。
  • 队尾（Rear）：允许插入的一端。

2. 队列的分类

队列与栈类似，实现方式有两种。一种是以数组的方式实现，另一种以单链表来实现。这两种实现方式各有优劣，并且都有细节需要处理。

  1. 基于单链表实现：我们可以将链表的头节点与尾节点分别作为队列的队首与队尾，这样我们就能用两个指针来对其进行操作。如下图：

img

  1. 基于数组实现：我们同样可以通过两个下标分别指向数组的起始与结束，但这时我们就可能发现两个问题：

  • 问题一：在不断出队与进队得到过程中，起始下标与末尾下标都在向后移动，当两个下标同时指向数组末尾时就无法再移动了，并且**浪费前面大量空间，**如图1

  • 问题二：为了解决上述问题，我们将数组首尾相接变为循环数组。但这时又会出现一个问题，那便是当队首与队尾下标指向同一个节点时，这个队列到底是空还是满呢？这时我们有三个解决方法

  • 第一种：牺牲一个单元来区分队空和队满，这时若队列不为空，让队尾下标指向队尾的下一个位置。约定以队头指针在队尾指针的下一位置作为队满的标志，即Q->rear+1==Q->front。如图二。

  • 第二种：增设表示元素个数的数据成员 size 。这样，队空的条件为 Q->size==0；队满的条件为 Q->size==MaxSize。

  • 第三种：增加表示队满的数据成员flag。将flag初始化为0，当队满时将其置为1。

img

3. 队列的功能

  1. 队列的初始化。
  2. 判断队列是否为空。。
  3. 返回队头与队尾的元素。
  4. 返回队列的大小。
  5. 入队与出队。
  6. 打印队列的元素。
  7. 销毁队列。

4. 队列的声明

4.1. 链式队

链式队的声明十分简单，参照上面图我们就可以直接实现了。

typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue 
{
	QNode* front;
	QNode* rear;
	size_t size;
}Queue;

4.2. 循环队

根据上述分析，我们采用一个数组来实现队列，其声明如下

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType data[MAXSIZE];
    int front;  //头指针
    int rear;   //尾指针
}Queue;

void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素

5. 队列的初始化

对队列声明的数据进行初始化，防止随机值。

5.1. 链式队

void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

5.2. 循环队

void QueueInit(Queue* q) 
{
    q->front = 0;
    q->rear = 0;
}

5.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

6. 判断队列是否为空

判断队列是否为空十分简单，这里就不在赘述。

6.1. 链式队

bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}

6.2. 循环队

bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}

6.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

7. 返回队头与队尾元素

因为定义了头指针与尾指针，所以访问数据也十分方便。

7.1. 链式队

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

7.2. 循环队

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->rear-1];
}

7.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

8. 队列的大小

8.1. 链式队

size_t QueueSize(Queue* q)
{
	return q->size;
}

8.2. 循环队

求循环队列的大小，我们很容易想到用Q->rear-Q->front得出队列元素个数。但是我们要考虑到一种特殊情况：当队列先删除元素再添加元素时，末尾下标**rear**可能循环重置，如下图。

img

那到底该如何解决这个问题呢？其实我们只需要在原来基础上加上一个MAXSIZE就行了，为了使图一情况也适用我们仍需模上一个MAXSIZE。

size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

8.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

9. 入队

9.1. 链式队

链式队列入队时需要判断队列是否为空的特殊情况，如果是则还需要将尾指针也指向这个节点。

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}

9.2. 循环队

为了使循环队列在插入数据时实现循环操作，我们可以每次进行取模操作。

void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}

9.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

10. 出队

10.1. 链式队

同样考虑特殊情况，防止队列为空。并且当队列只有一个节点时需要将头指针与尾指针都置为空。

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}

10.2. 循环队

同样为了实现循环，我们可以进行取模操作。

 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }

10.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

11. 打印队列

11.1. 链式队

void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}

11.2. 循环队

 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }

11.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

12. 销毁队列

12.1. 链式队

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}

12.2. 循环队

循环队列是以数组作为存储空间，并不是动态内存开辟的空间，所以并不需要手动释放空间。

12.3. 复杂度分析

  • 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：链式队花费空间都是一个固定大小，所以空间复杂度为O(1)。

13. 链式队与循环队列的对比与应用

13.1. 对比

对比项链式队循环队列
时间效率因为存在头指针与尾指针，所以链式队的出队与入队的时间都相对较小。循环队列是基于数组实现的，支持下标的随机访问，所以时间消耗也并不大
空间效率链式队每次入队都需固定创造一个新的节点，空间利用率较高，较稳定。循环队列的空间是固定的，可能会造成空间的浪费。

13.2. 应用

队列的应用与栈一样，十分广泛

  1. 当我们去食堂扫码订餐时，你的订单就会加入一个队列中。
  2. 在操作系统中，队列可以用来管理任务进度与进程切换。

14. 完整代码

14.1. 链式队

14.1.1. Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue 
{
	QNode* front;
	QNode* rear;
	size_t size;
}Queue;
void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素
void QueueDestroy(Queue* q);//销毁队列
14.1.2. Queue.c
#include"Queue.h"
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
size_t QueueSize(Queue* q)
{
	return q->size;
}
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}

14.2. 循环队列

14.2.1. Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType data[MAXSIZE];
    int front;  //头指针
    int rear;   //尾指针
}Queue;

void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素
14.2.2. Queue.c
void QueueInit(Queue* q) 
{
    q->front = 0;
    q->rear = 0;
}
bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->rear-1];
}
size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}
 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }
 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }

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

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

相关文章

原来这就是线程安全(一)

原来这就是线程安全(一)

TOC 一:什么是线程不安全?? 先看一段代码: public class Demo1 {public static int count 0;public static void main(String[] args) throws InterruptedException {Thread t1new Thread(()->{for (int i 0; i < 50000; i) {count;}});Thread t2new Thread(()-&g…
阅读更多...
Linux-进程控制

Linux-进程控制

&#x1f30e;进程控制【上】 文章目录&#xff1a; 进程控制 为什么要有地址空间和页表 程序的内存       程序申请内存使用问题 写时拷贝与缺页中断 父子进程代码共享       为什么需要写时拷贝       页表的权限位       缺页中断 退出码和错误码…
阅读更多...
P3369 【模板】普通平衡树（splay 算法）

P3369 【模板】普通平衡树（splay 算法）

题目描述 您需要写一种数据结构&#xff08;可参考题目标题&#xff09;&#xff0c;来维护一些数&#xff0c;其中需要提供以下操作&#xff1a; 插入一个数 x。删除一个数 x&#xff08;若有多个相同的数&#xff0c;应只删除一个&#xff09;。定义排名为比当前数小的数的…
阅读更多...
Pytorch从零开始实战22

Pytorch从零开始实战22

Pytorch从零开始实战——CycleGAN实战 本系列来源于365天深度学习训练营 原作者K同学 内容介绍 CycleGAN是一种无监督图像到图像转换模型&#xff0c;它的一个重要应用领域是域迁移&#xff0c;比如可以把一张普通的风景照变化成梵高化作&#xff0c;或者将游戏画面变化成真…
阅读更多...
2024软件设计师备考讲义——UML（统一建模语言）

2024软件设计师备考讲义——UML（统一建模语言）

UML的概念 用例图的概念 包含 <<include>>扩展<<exted>>泛化 用例图&#xff08;也可称用例建模&#xff09;描述的是外部执行者&#xff08;Actor&#xff09;所理解的系统功能。用例图用于需求分析阶段&#xff0c;它的建立是系统开发者和用户反复…
阅读更多...
4G/5G防爆布控球

4G/5G防爆布控球

#防爆布控球 #远程实时监控 #移动应急指挥 #高清图像采集 #防爆安全认证 4G/5G防爆布控球 M130-EX防爆布控球是针对石化装置、石油平台、燃气、化工、制药、煤炭、冶炼、船舶制造、纺织等易燃易爆环境及危险场所而开发设计的防爆智能一体化电气设备。 产品型号&#xff1a;M13…
阅读更多...
Antd Vue3 使用 Anchor 锚点组件记录

Antd Vue3 使用 Anchor 锚点组件记录

项目场景 客户要求做一个表单页面&#xff0c;表单数据分为三步&#xff0c;每一步骤是一个单独的 Vue 组件&#xff0c;表单上方需要使用锚点组件实现锚点定位到每一步的功能。 代码总览 <template><div class"guided-form-content-wrapper"><!-- …
阅读更多...
CKS之Kubernetes审计日志

CKS之Kubernetes审计日志

目录 概述 审计事件阶段 审计日志级别 None Metadata Request RequestResponse 审计日志的使用 步骤1&#xff1a;配置审计策略文件 步骤2&#xff1a;配置API Server 步骤3&#xff1a;配置日志存储 注意事项 审计策略与规则 审计日志样例 使用场景 概述 Kube…
阅读更多...
一、JAVA集成海康SDK

一、JAVA集成海康SDK

JAVA集成海康SDK 文章目录 JAVA集成海康SDK前言一、项目依赖 jar1. examples.jar2. 项目依赖 jna.jar，可以通过 maven依赖到。二、集成SDK1.HcNetSdkUtil 海康 SDK封装类2.HCNetSDK3.Linux系统集成SDK三、总结前言 提示：首先去海康官网下载 https://open.hikvision.com/dow…
阅读更多...
stable diffusion如何下载模型？

stable diffusion如何下载模型？

文件夹里面有14个模型&#xff0c;把这些模型复制到SD文件夹里 具体位置:SD文件>models>ControlNet
阅读更多...
【C/C++】从零开始认识C++历程-启航篇

【C/C++】从零开始认识C++历程-启航篇

文章目录 &#x1f4dd;前言&#x1f320; 什么是C&#xff1f;&#x1f309;C的发展史 &#x1f320;C的重要性&#x1f309;语言的使用广泛度 &#x1f320;在工作领域&#x1f309; 岗位需求 &#x1f320;相关笔试题&#x1f309; 公司怎样面试C &#x1f6a9;总结 &#x…
阅读更多...
蓝桥杯 - 小明的背包1（01背包）

蓝桥杯 - 小明的背包1（01背包）

解题思路&#xff1a; 本题属于01背包问题&#xff0c;使用动态规划 dp[ j ]表示容量为 j 的背包的最大价值 注意&#xff1a; 需要时刻提醒自己dp[ j ]代表的含义&#xff0c;不然容易晕头转向 注意越界问题&#xff0c;且 j 需要倒序遍历 如果正序遍历 dp[1] dp[1 - vo…
阅读更多...
java的多态和final关键字

java的多态和final关键字

多态&#xff1a; 多态分为对象多态&#xff0c;行为多态 多态的前提&#xff1a; 有继承/实现关系&#xff1b;存在父类引用子类对象&#xff1b;存在方法重写&#xff1b; 注意&#xff1a;多态是对象&#xff0c;行为的多态&#xff0c;java的成员变量不谈多态 这是我写…
阅读更多...
将Knife4j所展示请求参数和响应参数转化为TS类型声明

将Knife4j所展示请求参数和响应参数转化为TS类型声明

目标&#xff1a;在浏览器控制台输入js代码&#xff0c;将读取页面所展示的请求参数和响应参数&#xff0c;将他们转化为TS的类型声明&#xff0c;并在控制台中输出出来。 将Knife4j所展示请求参数和响应参数转化为TS类型声明 1 找到所需要的元素节点2 转化元素节点3 封装成函…
阅读更多...
本地部署的stable diffusion 如何更新controlnet？

本地部署的stable diffusion 如何更新controlnet？

stable diffusion 未启动状态 点击“版本管理” 点击“扩展” 找到controlnet&#xff0c;点击右边的“更新”按钮 完成&#xff01;
阅读更多...
【软考---系统架构设计师】特殊的操作系统介绍

【软考---系统架构设计师】特殊的操作系统介绍

目录 一、嵌入式系统&#xff08;EOS&#xff09; &#xff08;1&#xff09;嵌入式系统的特点 &#xff08;2&#xff09;硬件抽象层 &#xff08;3&#xff09;嵌入式系统的开发设计 二、实时操作系统&#xff08;RTOS&#xff09; &#xff08;1&#xff09;实时性能…
阅读更多...
总结TCP各类知识点

总结TCP各类知识点

前言 本篇博客博主将详细地介绍TCP有关知识点&#xff0c;坐好板凳发车啦~ 一.TCP特点 1.有连接 TCP传输的过程中类似于打电话的各个过程 2.可靠传输 通过TCP自身的多种机制来保证可靠传输 3.面向字节流 内容是以字节的方式来进行发送与接收 4.缓冲区 TCP有接收缓冲区…
阅读更多...
网络安全接入认证-802.1X接入说明

网络安全接入认证-802.1X接入说明

介绍 802.1X是一个网络访问控制协议&#xff0c;它可以通过认证和授权来控制网络访问。它的基本原理是在网络交换机和认证服务器之间建立一个安全的通道&#xff0c;并要求客户端提供身份验证凭据。如果客户端提供的凭据是有效的&#xff0c;交换机将开启端口并允许访问。否则&…
阅读更多...
服务器被挖矿了怎么办，实战清退

服务器被挖矿了怎么办，实战清退

当我们发现服务器资源大量被占用的时候&#xff0c;疑似中招了怎么办 第一时间重启服务是不行的&#xff0c;这些挖矿木马一定是会伴随着你的重启而自动重启&#xff0c;一定时间内重新霸占你的服务器资源 第一步检查高占用进程 top -c ps -ef 要注意这里%CPU&#xff0c;如果…
阅读更多...
1.8.1 摄像机

1.8.1 摄像机

一、摄像机 OpenGL本身没有摄像机的概念&#xff0c;但是我们可以通过把场景中的所有物体往相反方向移动的方式来模拟出摄像机&#xff0c;产生一种我们在移动的感觉&#xff0c;而不是场景在移动。 本节将会讨论如何在OpenGL中配置一个摄像机&#xff0c;让你能够在3D场景中…
阅读更多...
最新文章

Copyright @ 2022~2023