如何设计循环队列（两种方法）

文章目录

  • 前言
  • 一、方法一:数组法
  • 二、方法二.链表法
  • 总结

前言

前面有提到过队列的知识，这次来说一下怎么设计一个循环队列

一.循环队列（力扣）

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/description/

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

思路:循环队列无论使用数组实现还是链表实现，都要多开一个空间，也就意味着要是存K个数据的循环队列，就要开K+1个空间，不然无法实现判空和判满

方法一:数组法

注意数组法的判空和判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

1.0初始化

初始化一个数组，有头front，尾tail，数组明a

typedef struct {
	int* a;
	int front;
	int tail;
	int k;

} MyCircularQueue;

1.1创建

MyCircularQueue* myCircularQueueCreate(int k) 
{
	//开辟一个循环队列的空间
	MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//开辟一个数组的空间用来实现循环队列，要多开辟一个
	q->a = (int*)malloc(sizeof(int) * (k + 1));
	//初始化
	q->front = q->tail = 0;
	q->k = k;
	return q;
}

1.2判空，判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->k + 1) == obj->front;
}

1.3插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	//如果循环队列是满的就不能插入
	if (myCircularQueueIsFull(obj))
		return false;
	//把末尾的值插入值
	obj->a[obj->tail] = value;
	//然后tail的往后走
	++obj->tail;
	//防止数组越界，%(k+1)把下标都控制在k之内
    //把越界的重置
	obj->tail %= (obj->k + 1);
	return true;
}

1.4删除

数组的删除不用向链表这些Pop，直接覆盖就可以了

//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	//如果是空的就不能删
	if (myCircularQueueIsEmpty(obj))
		return false;
	//头往前走
	++obj->front;
	//止数组越界，%(k+1)把下标都控制在k之内
	obj->front %= (obj->k + 1);
	return true;
}

1.5拿出最后一个数

int myCircularQueueRear(MyCircularQueue* obj) {
	//如果是空的就拿不了
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数
	if (obj->tail == 0)
		return obj->a[obj->k];
	else
		return obj->a[obj->tail - 1];
}

1.6拿出头数据和销毁

//直接拿出
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}

	return obj->a[obj->front];

}

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

1.7总代码

注意把判空判满提前引用！！！

typedef struct {
	int* a;
	int front;
	int tail;
	int k;

} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) 
{
	//开辟一个循环队列的空间
	MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//开辟一个数组的空间用来实现循环队列，要多开辟一个
	q->a = (int*)malloc(sizeof(int) * (k + 1));
	//初始化
	q->front = q->tail = 0;
	q->k = k;
	return q;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	//如果循环队列是满的就不能插入
	if (myCircularQueueIsFull(obj))
		return false;
	//把末尾的值插入值
	obj->a[obj->tail] = value;
	//然后tail的往后走
	++obj->tail;
	//防止数组越界，%(k+1)把下标都控制在k之内
	obj->tail %= (obj->k + 1);
	return true;
}

//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	//如果是空的就不能删
	if (myCircularQueueIsEmpty(obj))
		return false;
	//头往前走
	++obj->front;
	//止数组越界，%(k+1)把下标都控制在k之内
	obj->front %= (obj->k + 1);
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}

	return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {
	//如果是空的就拿不了
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数
	if (obj->tail == 0)
		return obj->a[obj->k];
	else
		return obj->a[obj->tail - 1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->k + 1) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

方法二.链表法

2.0初始化

先初始化一个链表，在定义结构

typedef struct listNode {
    int data;
    struct Node* next;
}Node;

typedef struct {
    Node* front;
    Node* tail;
    int k;
}MyCircularQueue;

2.1创建

这个是最难的部分，就是在创建的时候要创造一个循环链表，注意:这里其实已经开辟了k+1个空间了,不懂的自己画图

MyCircularQueue* myCircularQueueCreate(int k) {

    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->tail = (Node*)malloc(sizeof(Node));
    cq->k = k;
    //创造一个循环链表
    //这里其实已经开辟了k+1个空间了注意
    while (k)
    {
        Node* cur= (Node*)malloc(sizeof(Node));
        cur->data = 0;
        cur->next = NULL;
        cq->tail->next =cur;
        cq->tail= cq->tail->next;
        k--;
    }
    //开辟好了之后还要把尾和头发一起
    cq->tail->next =cq->front;
    cq->tail= cq->front;

    return cq;
}

2.2判空，判满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->front;
}

2.3插入

//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判满
    if (myCircularQueueIsFull(obj))
        return false;
    //直接在尾上插入
    obj->tail->data = value;
    obj->tail= obj->tail->next;
    return true;
}

2.4删除

//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判空
    if (myCircularQueueIsEmpty(obj))
        return false;
    //头删
    obj->front = obj->front->next;
    return true;
}

2.5去头元素

int myCircularQueueFront(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}

2.6去尾元素

注意尾是前一个元素，所以不可以直接拿出，实在不理解看一下直接的动图

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //去找尾
    Node* cur= obj->front;
    while (cur->next != obj->tail)
        cur= cur->next;

    return cur->data;

}

2.7销毁

这个是我自己犯的错误

cur=cur->next,为什么不可以，因为cur等于头节点，cur等于cur->next，再释放cur，相当于把头节点next释放掉了，那我头节点后面的后面怎么去找呢？所以我们是从头节点开始释放的，把头节点用cur记录下来，释放之前让头节点走了，但是cur是头节点的傀儡节点，所以释放cur相当于是释放头节点了。

void myCircularQueueFree(MyCircularQueue* obj) {
   //和单链表的销毁一样
    Node* tmp = obj->front;
    while (obj->k + 1)
    {
        //cur=cur->next；为什么不可以
        obj->front = obj->front->next;
        free(tmp);
        tmp = obj->front;
        obj->k--;
    }
    free(obj);
}

2.8总代码

注意把判空判满提前引用！！！

typedef struct listNode {
    int data;
    struct Node* next;
}Node;

typedef struct {
    Node* front;
    Node* tail;
    int k;
}MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {

    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->tail = (Node*)malloc(sizeof(Node));
    cq->k = k;
    //创造一个循环链表
    //这里其实已经开辟了k+1个空间了注意
    while (k)
    {
        Node* cur= (Node*)malloc(sizeof(Node));
        cur->data = 0;
        cur->next = NULL;
        cq->tail->next =cur;
        cq->tail= cq->tail->next;
        k--;
    }
    //开辟好了之后还要把尾和头发一起
    cq->tail->next =cq->front;
    cq->tail= cq->front;

    return cq;
}
//插入
//他这个题目其实是提前开辟好了，让你直接插入就可以了
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判满
    if (myCircularQueueIsFull(obj))
        return false;
    //直接在尾上插入
    obj->tail->data = value;
    obj->tail= obj->tail->next;
    return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判空
    if (myCircularQueueIsEmpty(obj))
        return false;
    //头删
    obj->front = obj->front->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //去找尾
    Node* cur= obj->front;
    while (cur->next != obj->tail)
        cur= cur->next;

    return cur->data;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
   //和单链表的销毁一样
    Node* tmp = obj->front;
    while (obj->k + 1)
    {
        obj->front = obj->front->next;

        free(tmp);
        tmp = obj->front;

        obj->k--;
    }
    free(obj);
}

总结

用两种解法理解了循环队列，想必对链表和队列的知识做到了巩固

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

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

相关文章

seleniumUI自动化实例（CSDN发布文章）

seleniumUI自动化实例（CSDN发布文章）

1.CSDN登陆成功后，点击发布 源码： #点击首页中的发布按钮 CSDNconf.driver.find_element(By.LINK_TEXT,"发布").click() time.sleep(15) 2.输入标题 #输入文章标题，标题格式“selenium UI自动化测试实例今天的日期” CSDNconf.d…
阅读更多...
JavaScript中的Lexical Environment

JavaScript中的Lexical Environment

概要 本文主要介绍JavaScript中的一个重要概念Lexical Environment，它可以帮助我们解释我们为什么可以通过嵌套方法，共享数据，以及为什么可以在函数中定义一个和全局变量同名的变量，并且不会影响到全局变量。 基本分析 基本概念…
阅读更多...
leetcode 2671

leetcode 2671

leetcode 2671 题目 例子 思路1 使用哈希&#xff0c; unordered_map 是基于hash 实现的key,val 存储。 代码1 class FrequencyTracker {unordered_map<int, int>m;public:FrequencyTracker() { }void add(int number) {if(m.find(number) m.end()){m.insert({num…
阅读更多...
机器学习 | 期望最大化（EM）算法介绍和实现

机器学习 | 期望最大化（EM）算法介绍和实现

在现实世界的机器学习应用中&#xff0c;通常有许多相关的特征&#xff0c;但只有其中的一个子集是可观察的。当处理有时可观察而有时不可观察的变量时&#xff0c;确实可以利用该变量可见或可观察的实例&#xff0c;以便学习和预测不可观察的实例。这种方法通常被称为处理缺失…
阅读更多...
pytorch 实现多层神经网络MLP（Pytorch 05）

pytorch 实现多层神经网络MLP（Pytorch 05）

一 多层感知机 最简单的深度网络称为多层感知机。多层感知机由 多层神经元 组成&#xff0c;每一层与它的上一层相连&#xff0c;从中接收输入&#xff1b;同时每一层也与它的下一层相连&#xff0c;影响当前层的神经元。 softmax 实现了 如何处理数据&#xff0c;如何将 输出…
阅读更多...
【算法】小强爱数学（迭代公式+数论取模）

【算法】小强爱数学（迭代公式+数论取模）

文章目录 1. 问题2. 输入3. 输出4. 示例5. 分析6. 思路7. 数论&#xff0c;取模相关公式8. 数论&#xff0c;同余定理9. 代码 1. 问题 小强发现当已知 x y B xyB xyB以及 x y A xyA xyA时,能很轻易的算出 x n x_ {n} xn​ y n y_ {n} yn​ 的值.但小强想请你在已知A和B的…
阅读更多...
Java IO的基本使用和常见类的介绍及其案例讲解

Java IO的基本使用和常见类的介绍及其案例讲解

Java IO&#xff08;Input/Output&#xff09;是Java编程语言中用于处理输入输出的机制。IO包含了读取和写入数据的功能&#xff0c;可以实现文件的读写、网络通信、和各种设备的输入输出操作。在Java中&#xff0c;IO操作主要由输入流&#xff08;Input Stream&#xff09;和输…
阅读更多...
mysql基础2多表查询

mysql基础2多表查询

多表查询 多表关系: 一对多 案例: 部门 与 员工的关系 关系: 一个部门对应多个员工&#xff0c;一个员工对应一个部门 实现: 在多的一方建立外键&#xff0c;指向一的一方的主键 多对多 案例: 学生 与 课程的关系 关系: 一个学生可以选修多门课程&#xff0c;一门课程也可以…
阅读更多...
javaWeb奶茶商城前后台系统

javaWeb奶茶商城前后台系统

一、简介 在当前数字化时代&#xff0c;电子商务已成为人们生活中不可或缺的一部分。为了满足用户对奶茶的需求&#xff0c;我设计并实现了一个基于JavaWeb的奶茶商城前后台系统。该系统涵盖了用户前台和管理员后台两大模块&#xff0c;包括登录注册、商品展示、购物车管理、订…
阅读更多...
java面向对象编程基础

java面向对象编程基础

对象&#xff1a; java程序中的对象&#xff1a; 本质上是一种特殊的数据结构 对象是由类new出来的&#xff0c;有了类就可以创建对象 对象在计算机的执行原理&#xff1a; student s1new student();每次new student(),就是在堆内存中开辟一块内存区域代表一个学生对象s1变…
阅读更多...
蓝桥杯物联网Lora通信功能总结

蓝桥杯物联网Lora通信功能总结

1、LORA通信在函数LORA被初始化的时候就已经处于接收状态 即开机即能接收数据 2、LORA数据的接收以及发送都通过FIFO数据线 3、LORA的收发同时进行会产生FIFO数据线的通信干扰 4、LORA_Rx在FIFO中有数据的时候才会取出数据&#xff0c;FIFO没有数据会直接跳过 当LORA在发送数…
阅读更多...
UDP建立聊天群

UDP建立聊天群

参考网上代码 接收端 #include<myhead.h> #define PRINT_ERR(msg) \ do \ { \ printf("%s,…
阅读更多...
求解线性方程组

求解线性方程组

如图题意看出x1有且仅有两种可能&#xff0c;1或者0&#xff0c;且知道了所有a的值&#xff0c;且因为要求所得答案字典序最小&#xff0c;所以先假设x10。 又因a2x1x2所以可以求出x2的值&#xff0c;又如a2x1x2x3,所以可以求出x3的值依次求出所有x的值&#xff0c;但每求出一…
阅读更多...
Java 基础知识- 创建线程的几种方式

Java 基础知识- 创建线程的几种方式

大家好我是苏麟 , 今天聊聊创建线程的几种方式 . 创建线程的几种方式 1. 继承Thread类实现多线程 /*** className: ThreadTest* author: SL 苏麟**/ public class ThreadTest extends Thread{public static void main(String[] args) {ThreadTest threadTest new ThreadTes…
阅读更多...
第十二届蓝桥杯省赛CC++ 研究生组-路径

第十二届蓝桥杯省赛CC++ 研究生组-路径

记录到每个结点的最短距离&#xff0c;以此为基础计算后续结点最优值 #include<iostream> #include<algorithm> using namespace std; typedef long long ll;ll gcd(int a, int b){if(!b) return a;return gcd(b, a % b); }int main(){ll dp[2022] {0};//dp[i]记…
阅读更多...
ppp协议

ppp协议

一.实验拓扑 二.实验要求 1.R1和R2使用PPP链路直连&#xff0c;R2和R3把2条PPP链路捆绑为PPP MP直连 2.按照图示配置IP地址 3.R2对R1的PPP进行单向chap验证 4.R2和R3的PPP进行双向chap验证 三.实验思路 1.R2对R1进行ppp单向chap验证&#xff1a; R2配置为主&#xff0c;…
阅读更多...
数据库语言一些基本操作

数据库语言一些基本操作

1&#xff0c;消除取值重复的行。 例如&#xff1a;查成绩不及格的学号&#xff1a;SELECT DISTINCT sno FROM SC WHERE grade<60. 这里使用DISTINCT表示取消取值重复的行。 2&#xff0c;比较。 例如&#xff1a;查计算机系全体学生的姓名&#xff1a;SELECT Sname FROM…
阅读更多...
模拟实现字符串库函数（一）

模拟实现字符串库函数（一）

在C语言的标准库中提供了很多针对字符串的库函数&#xff0c;这篇文章我们会学习并模拟实现几个简单的库函数 求字符串长度函数strlen strlen函数我们在之前已经用过很多次了&#xff0c;同时也模拟实现过&#xff0c;但是都不是模仿标准库中的strlen来实现&#xff0c;首先我…
阅读更多...
三.寄存器（内存访问）

三.寄存器（内存访问）

1.内存中字的存储 2.并不是所有cpu都支持将数据段送入段寄存器&#xff0c;所以有时候用个别的寄存器先把数据段存储起来&#xff0c;再把该寄存器mov到段寄存器。 3.字的传送 4.栈 5.栈机制 举例说明 6.栈顶超界问题 push超界 pop超界 7.栈段
阅读更多...
pta-洛希极限

pta-洛希极限

科幻电影《流浪地球》中一个重要的情节是地球距离木星太近时&#xff0c;大气开始被木星吸走&#xff0c;而随着不断接近地木“刚体洛希极限”&#xff0c;地球面临被彻底撕碎的危险。但实际上&#xff0c;这个计算是错误的。 洛希极限&#xff08;Roche limit&#xff09;是一…
阅读更多...
最新文章

Copyright @ 2022~2023