006——队列

server/2024/9/23 17:43:20/

目录

队列：

 单端队列：

存储结构：

顺序队列

思路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;
}

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


http://www.ppmy.cn/server/120896.html

相关文章

LeetCode41. 缺失的第一个正数（2024秋季每日一题 20）

LeetCode41. 缺失的第一个正数（2024秋季每日一题 20）

给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3 解释&#xff1a;范围 [1,2] 中的数字都在数组…
阅读更多...
spring springboot 日志框架

spring springboot 日志框架

一、常见的日志框架 JUL、JCL、Jboss-logging、logback、log4j、log4j2、slf4j.... 注意&#xff1a;SLF4j 类似于接口 Log4j &#xff0c;Logback 都是出自同一作者之手 JUL 为apache 公司产品 Spring&#xff08;commons-logging&#xff09;、Hibernate&#xff08;jboss…
阅读更多...
C++单例模式代码实现与分析

C++单例模式代码实现与分析

目录 1 代码 2 代码剖析 2.1 构造函数私有化 2.2 只能执行一次的代码 2.3 静态成员变量 2.4 智能指针 1 代码 下面的代码是https://github.com/Cambricon/CNStream 中的&#xff0c; /************************************************************************** Cop…
阅读更多...
使用Redis实现用户关注博客的推模式

使用Redis实现用户关注博客的推模式

目录 一、思路 二、实现代码&#xff1a; 一、思路 发布者&#xff1a; 这里采用redis的zset结构&#xff0c;将键设置为被推送用户id&#xff0c;值设置为博客id&#xff0c;score设置为时间戳 推送之前先查到当前发布博客用户的粉丝有哪些&#xff0c;然后去循环挨个推送…
阅读更多...
如何将 java.nio.ByteBuffer 转为 String

如何将 java.nio.ByteBuffer 转为 String

如何将 java.nio.ByteBuffer 转为 String 方法1: newString()方法结合ByteBuffer的array()方法, 忽略是否flip()过 用String的 public String(byte[] bytes, int offset, int length, Charset charset)方法 和 ByteBuffer的array()方法 长度在取 bbf.position()0?bbf.limit(…
阅读更多...
银河麒麟桌面操作系统V10（SP1）离线升级SSH(OpenSSH)服务

银河麒麟桌面操作系统V10（SP1）离线升级SSH(OpenSSH)服务

目录 前言 准备工作 准备与目标服务器相同版本的操作系统 准备编译依赖包 下载OpenSSL源码包 下载OpenSSH源码包 升级OpenSSH服务 查看当前版本信息 安装编译依赖包 安装OpenSSL 安装OpenSSH 前言 OpenSSH是一个广泛使用的开源SSH（安全壳）协议的实现，它提供了安…
阅读更多...
Android对象池的深入理解和使用

Android对象池的深入理解和使用

参考文献&#xff1a;https://www.jianshu.com/p/eb04e4e1869d 判断对象是否可以被回收 垃圾收集算法 内存分配与回收策略
阅读更多...
安卓13长按电源按键直接关机 andriod13不显示关机对话框直接关机

安卓13长按电源按键直接关机 andriod13不显示关机对话框直接关机

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析4.代码修改5.编译6.彩蛋1.前言 有些设备需要在长按电源键的时候，直接关机。不需要弹出对话框进行询问。 2.问题分析 过滤电源按键，需要在系统里面处理的话，那么我们需要熟悉android的事件分发，然后再…
阅读更多...
最新文章

Copyright @ 2022~2023