006——队列

目录

队列：

 单端队列：

存储结构：

顺序队列

思路1：r指针指向尾元素的下一个位置

思路2：r指针指向真正的尾元素

如何解决假溢出的问题？

链式队列

双端队列

存储方式：

顺式存储

代码案例：

链式存储

代码示例

队列：

一种受限的线性表（线性逻辑结构），只允许在一段进行添加操作，在另一端只允许进行删除操作，中间位置不可操作，入队的一端被称为队尾，出队的一端被称为队头，在而我们会用两个指针分别用于标记队首和队尾，分别叫做队首指针和队尾指针

 单端队列：

存储结构：

顺序队列

顺序存储，基于数组来存储

两种思路

思路1：r指针指向尾元素的下一个位置

Ⅰ)初始空的队列：f=0,r=0

typedef struct {
	int* data;//数组
	int f, r;//front队首指针  rear队尾指针 
}Squeue;

Squeue InitQueue()
{
	Squeue q;
	q.data = (int*)malloc(sizeof(int) * maxsize);
	if (q.data == NULL)
	{
		printf("空间分配失败\n");
	}
	else {
		q.f = q.r = 0;
	}
	return q;
}

Ⅱ）入队：a[r]=k;r++;//a[r++]=k;

void Enqueue(Squeue* q, int k)
{
	q->data[q->r] = k;
	r++;
}

Ⅲ）出队：f++;

void Dequeue(Squeue* q)
{
	q->f++;
}

Ⅳ）判满：r==maxsize(假溢出)

Ⅴ）判空：f==r

思路2：r指针指向真正的尾元素

Ⅰ)初始空的队列：f=0,r=-1

Squeue InitQueue()
{
	Squeue q;
	q.data = (int*)malloc(sizeof(int) * maxsize);
	if (q.data == NULL)
	{
		printf("空间分配失败\n");
	}
	else {
		q.f = 0;
        q.r = 1;
	}
	return q;
}

Ⅱ）入队：r++;a[r]=k;//a[++r]=k;

void Enqueue(Squeue* q, int k)
{
	r++;
    q->data[q->r] = k;
	
}

Ⅲ）出队：f++;

void Dequeue(Squeue* q)
{
	q->f++;
}

Ⅳ）判满：r==maxsize-1(假溢出)

Ⅴ）判空：f==r+1

如何解决假溢出的问题？

形成循环队列-->取余（思路1相对来说更加方便取余）

Ⅰ)初始空的队列：f=0,r=0

Ⅱ）入队：a[r]=k;r=（r+1）%maxsize;

Ⅲ）出队：f=（f+1）%maxsize;

Ⅳ）判满：

        方法①：牺牲一个存储空间（r+1）%maxsize==f;

        方法②：队满之前的操作一定是入队flag==0操作

                       队空之前的操作一定是出队flag==1操作

        则用一个变量flag来记录此时是入队操作还是出队操作

                        f==r&&flag==0

Ⅴ）判空：f==r

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
//循环队列
typedef struct {
	int* data;//数组
	int f, r;//front队首指针  rear队尾指针 
}Squeue;
Squeue InitQueue()
{
	Squeue q;
	q.data = (int*)malloc(sizeof(int) * maxsize);
	if (q.data == NULL)
	{
		printf("空间分配失败\n");
	}
	else {
		q.f = q.r = 0;
	}
	return q;
}
void Enqueue(Squeue* q, int k)
{
	if ((q->r + 1) % maxsize == q->f)
	{
		printf("队满，不能入队\n");
		return;
	}
	q->data[q->r] = k;
	q->r = (q->r + 1) % maxsize;

}
void Dequeue(Squeue* q)
{
	if (q->f == q->r)
	{
		printf("队空，不能出队\n");
		return;
	}
	printf("队首%d出队\n", q->data[q->f]);
	q->f = (q->f + 1) % maxsize;
}
int main()
{
	
	return 0;
}

链式队列

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
//链式队列
typedef struct Qnode {
	int data;
	struct Qnode* next;
}QNode;
typedef struct Queue {
	QNode* f;
	QNode* r;
}LinkQ;

LinkQ InitLinkQ()
{
	LinkQ q;
	q.f = (QNode*)malloc(sizeof(QNode));
	if (q.f == NULL)
	{
		printf("空间分配失败\n");
	}
	else {
		q.f->next = NULL;
		q.r = q.f;
	}
	return q;
}
LinkQ Enqueue(LinkQ q, int k)
{
	QNode* s = (QNode*)malloc(sizeof(QNode));
	if (s == NULL)
	{
		printf("空间分配失败,不能入队\n");
	}
	else {
		s->data = k;
		s->next = NULL;
		q.r->next = s;
		q.r = s;
	}
	return q;

}
LinkQ Dequeue(LinkQ q)
{
	if (q.r == q.f)
	{
		printf("空间分配失败,不能出队\n");
		return q;
	}
	QNode* p = q.f->next;
	q.f->next = p->next;
	if (q.r == p)
	{
		q.r = q.f;
	}
	printf("队首%d出队\n", p->data);
	free(p);
	p = NULL;
}
int main()
{
	return 0;
}

双端队列

双端队列，可以简单理解成将两个队列合在一起，而双端队列的两端分为前端和后端，而在着两端均可以进行出入队操作

存储方式：

顺式存储

前面可以了解到，顺序存储我们是用数组来实现，那这里就会存在一个问题：前端的位置和后端的位置是不固定的，-因为我们不知道前端的位置具体插入多少元素，后端的位置插入多少元素，所以我们采用循环数组来实现存储

这里还有一个需要考虑的问题：到底是先动指针还是先放数据？

①前后端先动指针后放数据

这个时候我们会发现中间会存放一个空数据，所以是不行的

①前后端先放数据后动指针

这个时候我们会发现有的元素数据会被覆盖掉

所以我们需要一端是先移动指针，一段是先放入数据

不过这样的话，其中一个指针指向的是该元素，另一个指针指向的是该元素的下一个位置

代码案例：

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
int* q=NULL;//指针模拟开数组
int l, r;//左端 右端
int size;//记录双端队列中实际的元素个数


void InitQueue() {
	q = (int*)malloc(sizeof(int) * maxsize);
	if (q == NULL) {
		printf("空间访问失败\n");
		return;
	}
	size = 0;
	l = r = 0;
}

//左端入队
void insert_left(int k) {
	if (size == maxsize) {
		printf("队满，不能入队\n");
		return;
	}
	q[l] = k;
	l = (l - 1 + maxsize) % maxsize;
	size++;
}

//左端出队
void delete_left() {
	if (size == 0) {
		printf("队空，不能出队\n");
		return;
	}
	printf("出队元素为%d", q[(l + 1) % maxsize]);
	l = (l + 1) % maxsize;
	size--;
}

//右端入队
void insert_right(int k) {
	if (size == maxsize) {
		printf("队满，不能入队\n");
		return;
	}
	
	r = (r + 1 ) % maxsize;
	q[r] = k;
	size++;
}

//右端出队
void delete_right() {
	if (size == 0) {
		printf("队空，不能出队\n");
		return;
	}
	printf("出队元素为%d", q[(r - 1 + maxsize) % maxsize]);
	r = (r - 1 + maxsize) % maxsize;
	size--;
}

//打印
void show() {
	int i = (l + 1)%maxsize;
	while (i != r) {
		printf("%d\t", q[i]);
		i = (i + 1) % maxsize;
	}
	printf("%d\n", q[r]);

}

int main() {
	InitQueue();
	insert_left(10);
	insert_left(5);
	insert_right(13);
	insert_right(56);
	show();
}

链式存储

因为双端队列需要往两端去延长，所以如果用链表来实现的话，我们需要用双向链表来去实现。

代码示例

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10 
typedef struct linkQ{
	int data;
	struct linkQ* pre;
	struct linkQ* next;
}Node; 
Node* l=NULL;
Node* r=NULL; 
void initqueue()
{
	l=(Node*)malloc(sizeof(Node));
	if(l==NULL)
	{
		printf("空间分配失败\n");
		return;
	}
	l->next=NULL;
	l->pre=NULL;
	r=l;
}
//左边
void insert_left(int k)
{
	Node* s=(Node*)malloc(sizeof(Node));
	if(s==NULL)
	{
		printf("空间分配失败,不能入队\n");
		return;
	}
	l->data=k;
	s->pre=l->pre;
	l->pre=s;
	s->next=l;
	l=s; 
 } 
void delet_left()
{
	if(l==r)
	{
	printf("队空，不能出队\n");
		return; 	
	}
	int x=l->next->data;
	printf("%d出队\n",x); 
	Node* p=l;
	l=p->next;
	l->pre=p->pre;
	free(p);
	p=NULL;
}
//右边
void insert_right(int k)
{
	Node* s=(Node*)malloc(sizeof(Node));
	if(s==NULL)
	{
		printf("空间分配失败,不能入队\n");
		return;
	}
	s->data=k;
	s->next=r->next;
	s->pre=r;
	r->next=s;
	r=s;
 } 
 void delet_right()
 {
 	if(l==r)
	{
	printf("队空，不能出队\n");
		return; 	
	}
	int x=r->data;
	printf("%d出队\n",x); 
	Node* p=r;
	r=p->pre;
	r->next=p->next;
	free(p);
	p=NULL;
}
void show()
{
	Node* p=l->next;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
int main()
{
	initqueue();
	insert_left(1);
	insert_left(2);
	insert_left(3);
    insert_right(4);
    insert_right(8);
    printff();
    delet_left();
	delet_right(); 
	delet_right();
	delet_right();
	 show();
	return 0;
}

后面我们将会去学习树的知识点，但在学习树的知识之前，先让我们了解一下递归的思想和代码实现

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

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

相关文章

Redis基础数据结构之 Sorted Set 有序集合 源码解读

Redis基础数据结构之 Sorted Set 有序集合 源码解读

目录标题 Sorted Set 是什么?Sorted Set 数据结构跳表&#xff08;skiplist&#xff09;跳表节点的结构定义跳表的定义跳表节点查询层数设置 Sorted Set 基本操作 Sorted Set 是什么? 有序集合&#xff08;Sorted Set&#xff09;是 Redis 中一种重要的数据类型&#xff0c;…
阅读更多...
国央企如何完善黑名单排查体系？

国央企如何完善黑名单排查体系？

国央企完善黑名单排查体系的关键在于建立健全的供应商管理机制、风险评估体系和信息共享平台。以下是一些具体措施&#xff1a; 1.建立黑名单库&#xff1a;国央企可以依据外部黑名单数据&#xff08;如政府监管部门、行业协会、第三方征信机构公布的黑名单&#xff09;和内部…
阅读更多...
瑞芯微RK3588开发板Linux系统添加自启动命令的方法，深圳触觉智能Arm嵌入式鸿蒙硬件方案商

瑞芯微RK3588开发板Linux系统添加自启动命令的方法，深圳触觉智能Arm嵌入式鸿蒙硬件方案商

本文适用于触觉智能所有Linux系统的开发板、主板添加自启动命令的方法&#xff0c;本次使用了触觉智能的EVB3588开发板演示&#xff0c;搭载了瑞芯微RK3588旗舰芯片。 该开发板为核心板加底板设计&#xff0c;为工业场景设计研发的模块化产品&#xff0c;10年以上稳定供货,帮助…
阅读更多...
免费分享：全月地质图

免费分享：全月地质图

数据详情 世界第一幅1∶250万月球全月地质图 数据属性 数据名称&#xff1a;月球1:250万全月地质图 数据时间&#xff1a;- 空间位置&#xff1a;月球 数据格式&#xff1a;jpg 空间分辨率&#xff1a;1:250万 坐标系&#xff1a;- 下载方法 打开数字地球开放平台网站&…
阅读更多...
跨境商家如何在1688找优质供应商货源，新手卖家必看

跨境商家如何在1688找优质供应商货源，新手卖家必看

选产品和找供应&#xff0c;是每个跨境人不可避免的&#xff0c;但是盲目的选品&#xff0c;无疑是大海捞针。如果你选择的商品没有固定的供应商&#xff0c;要上1688找又得花不少时间&#xff0c;店雷达选品工具就能够帮助我们解决这个问题。据我所知&#xff0c;很多跨境同行…
阅读更多...
STM32上实现FFT算法精准测量正弦波信号的幅值、频率和相位差（标准库）

STM32上实现FFT算法精准测量正弦波信号的幅值、频率和相位差（标准库）

在研究声音、电力或任何形式的波形时&#xff0c;我们常常需要穿过表面看本质。FFT&#xff08;快速傅里叶变换&#xff09;就是这样一种强大的工具&#xff0c;它能够揭示隐藏在复杂信号背后的频率成分。本文将带你走进FFT的世界&#xff0c;了解它是如何将时域信号转化为频域…
阅读更多...
最新绿豆影视系统 /反编译版源码/PC+WAP+APP端 /附搭建教程+软件

最新绿豆影视系统 /反编译版源码/PC+WAP+APP端 /附搭建教程+软件

源码简介&#xff1a; 最新的绿豆影视系统5.1.8&#xff0c;这可是个反编译版的源码哦&#xff01;它不仅支持PC端、WAP端&#xff0c;还有APP端&#xff0c;一应俱全。而且附上了搭建教程和软件&#xff0c;安卓和苹果双端都能用&#xff0c;实用方便&#xff01; 优化内容&…
阅读更多...
设计模式 组合模式（Composite Pattern）

设计模式 组合模式（Composite Pattern）

组合模式简绍 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端可以用一致的方式处理单个对象和组合对象。这样&#xff0c;可以在不知道对象具体类型的条…
阅读更多...
K8S容器实例Pod安装curl-vim-telnet工具

K8S容器实例Pod安装curl-vim-telnet工具

在没有域名的情况下&#xff0c;有时候需要调试接口等需要此工具 安装curl、telnet、vim等 直接使用 apk add curlapk add vimapk add tennet
阅读更多...
裸土检测算法实际应用、裸土覆盖检测算法、裸土检测算法

裸土检测算法实际应用、裸土覆盖检测算法、裸土检测算法

裸土检测算法主要用于环境保护、农业管理、城市规划和土地管理等领域&#xff0c;通过图像识别技术来检测和识别地表上的裸露土壤。这种技术可以帮助管理者实时监控裸土面积&#xff0c;及时采取措施&#xff0c;防止水土流失、环境污染和生态退化。 一、技术实现 裸土检测算…
阅读更多...
内核驱动开发之系统移植

内核驱动开发之系统移植

系统移植 系统移植&#xff1a;定制linux操作系统 系统移植是驱动开发的前导&#xff0c;驱动开发是系统运行起来之后&#xff0c;在内核中新增一些子功能而已 系统移植就四个部分&#xff1a; 交叉编译环境搭建好bootloader的选择和移植&#xff1a;BootLoader有一些很成熟…
阅读更多...
Linux-DHCP服务器搭建

Linux-DHCP服务器搭建

环境 服务端&#xff1a;192.168.85.136 客户端&#xff1a;192.168.85.138 1. DHCP工作原理 DHCP动态分配IP地址。 2. DHCP服务器安装 2.1前提准备 # systemctl disable --now firewalld // 关闭firewalld自启动 # setenforce 0 # vim /etc/selinux/config SELINU…
阅读更多...
如何在精益六西格玛项目实践中激励小组成员保持积极性？

如何在精益六西格玛项目实践中激励小组成员保持积极性？

在精益六西格玛项目实践中&#xff0c;激励小组成员保持积极性是推动项目成功与持续改进的关键因素。精益六西格玛作为一种集精益生产与六西格玛管理精髓于一体的管理模式&#xff0c;旨在通过流程优化、质量提升及成本降低&#xff0c;实现企业的卓越绩效。然而&#xff0c;这…
阅读更多...
Linux自主学习篇

Linux自主学习篇

用户及权限管理 sudo 是 "superuser do" 的缩写&#xff0c;是一个在类 Unix 操作系统&#xff08;如 Linux 和 macOS&#xff09;中使用的命令。它允许普通用户以超级用户&#xff08;root 用户&#xff09;的身份执行命令&#xff0c;从而获得更高的权限。 useradd…
阅读更多...
网络资源模板--Android Studio 垃圾分类App

网络资源模板--Android Studio 垃圾分类App

目录 一、项目演示 二、项目测试环境 三、项目详情 四、完整的项目源码 一、项目演示 网络资源模板--垃圾分类App 二、项目测试环境 三、项目详情 登陆注册 设置点击监听器&#xff1a;当用户点击注册按钮时触发事件。获取用户输入&#xff1a;从输入框获取用户名和密码&a…
阅读更多...
HarmonyOS鸿蒙开发实战（5.0）自定义全局弹窗实践

HarmonyOS鸿蒙开发实战（5.0）自定义全局弹窗实践

鸿蒙HarmonyOS开发实战往期文章必看&#xff1a; HarmonyOS NEXT应用开发性能实践总结 最新版&#xff01;“非常详细的” 鸿蒙HarmonyOS Next应用开发学习路线&#xff01;&#xff08;从零基础入门到精通&#xff09; 非常详细的” 鸿蒙HarmonyOS Next应用开发学习路线&am…
阅读更多...
Docker：解决开发运维问题的开源容器化平台

Docker：解决开发运维问题的开源容器化平台

云计算de小白 Docker是一个开源的容器化平台&#xff0c;可以将应用程序及其依赖的环境打包成轻量级、可移植的容器。 Docker为什么这么受欢迎呢?原因很简单&#xff1a;Docker可以解决不同环境一致运行的问题&#xff0c;而且占用资源少&#xff0c;速度快。 所以好的东西…
阅读更多...
C++速通LeetCode中等第2题-最长连续序列

C++速通LeetCode中等第2题-最长连续序列

方法一&#xff0c;排序后遍历&#xff0c;后减前1&#xff0c;计数&#xff0c; 相等跳过&#xff0c;后减前&#xff01;1就保存。 class Solution { public:int longestConsecutive(vector<int>& nums) {vector<int> ans;int count 1;sort(nums.begin(),n…
阅读更多...
ER论文阅读-Decoupled Multimodal Distilling for Emotion Recognition

ER论文阅读-Decoupled Multimodal Distilling for Emotion Recognition

基本介绍&#xff1a;CVPR, 2023, CCF-A 原文链接&#xff1a;https://openaccess.thecvf.com/content/CVPR2023/papers/Li_Decoupled_Multimodal_Distilling_for_Emotion_Recognition_CVPR_2023_paper.pdf Abstract 多模态情感识别&#xff08;MER&#xff09;旨在通过语言、…
阅读更多...
媒体动态：播客增长的重大转变、社交媒体创新和搜索动态

媒体动态：播客增长的重大转变、社交媒体创新和搜索动态

关键亮点&#xff1a; 关键亮点&#xff1a; 电视和音频&#xff1a;播客继续迅速增长&#xff0c;但主要由少数几档节目驱动。付费社交&#xff1a;Meta在最新的一次成功财报电话会议后继续加倍推进AI进展&#xff0c;X起诉GARM和广告商反垄断&#xff0c;Snap的订阅计划继续…
阅读更多...
最新文章

Copyright @ 2022~2023