当前位置：首页 > news >正文

海门公司网站制作费用网站建设与管理读书心得

news 2025/9/18 11:32:49

海门公司网站制作费用,网站建设与管理读书心得,策划品牌全案,移动网站自助制作🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 🎏队列顺序存储的不足 🎏循环队列的定义 🎏设计循环队列结语 🎏队列顺序存储的不足我们假设用一个可以存放为n个数据…

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

🎏队列顺序存储的不足

🎏循环队列的定义

🎏设计循环队列

结语

🎏队列顺序存储的不足

我们假设用一个可以存放为n个数据的数组arr来实现队列:

很容易可以知道:给arr中入队时时间复杂度为O(1),而出队时时间复杂度却是O(n).

按照传统方式每次出队时都要将所有元素向前挪动是非常麻烦的,我们不如在出队时让头指针也动起来,即在出队时不移动后面的元素,而是让front向后移动,指向新的队头元素:

这样出队和入队的时间复杂度都是O(1)了,但是使用这种方式,当我们入队又出队后会造成"假溢出"问题:

即数组前面有空着的空间,但因为队列入队要追加在队伍的末尾,因此只能追加在下图中9的后面,但9后面没有空间了,这时就会造成"假溢出"问题.

你想想,如果你今天去教室上课,因为是水课,后面3排都坐满了人,而前排还有很多空位,你会怎么做?直接走出教室,并告诉自己后面没有座位可坐了?

现实生活中我们不会那样做的,前面有座位,我们当然是可以坐的,除非真的满了,那才需要考虑向老师申请一个大教室.

🎏循环队列的定义

因此,解决假溢出的办法就是后面满了,就从头再开始,也即头尾相接的循环.

我们把队列的这种头尾相接的顺序存储结构称为循环队列.

在刚才的例子中,我们可以改变rear指向下标为0的位置,这样就可以继续入队元素了:

当我们继续一直入队元素,rear一直向后移动,直到将数组入满,此时rear和front重合,同时指向下标为5的位置,如图:

此时我们需要思考几个问题,我们刚才说,空队列时,front等于rear,而现在队列满时,也是front等于rear,那么该如何判断此时的队列究竟是空还是满?

办法一是设置一个标志flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满.
办法二是当队列空时,条件是front=rear,当队列满时,我们修改其条件,保留一个元素空间.也就是说,当数组中只剩一个空闲单元时,我们就认为队列满了,如下图所示:

由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈.

所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front

(这里的取模"%"的目的就是为了解决rear可能会比front大一圈的问题).

队列的长度计算也要特别注意,通用的计算队列长度公式为:

(rear-front+QueueSize)%QueueSize

有了以上关于循环队列的知识储备,我们接下来实战实现一个循环队列.

🎏设计循环队列

题目链接

622. 设计循环队列https://leetcode.cn/problems/design-circular-queue/

题目描述

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

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

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

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

题目详情

解题思路

循环队列的设计思路其实在文章前面的简介部分我们已经阐述过了,但在具体实现时,我们仍需注意以下几点:

注意题目要求的返回值,如入队/出队函数要求成功返回true,失败返回false.
注意队列判满的条件
注意rear,front在持续向后移动过程中,如果数值超过了合理的数组下标范围,,则需要想办法将其修正到合理的范围内.

解题代码

综上,解题代码如下:

typedef struct 
{int *arr;   //存数据int front;  //头指针int rear;   //尾指针int k;      //存个数
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj)//判空,为空返回true
{return (obj->front==obj->rear);
}bool myCircularQueueIsFull(MyCircularQueue* obj)//判满,为满返回true
{return ((obj->front)==((obj->rear+1)%(obj->k+1)));
}MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail::");return NULL;}obj->arr=(int*)malloc(sizeof(int)*(k+1));//留空一个,便于判断if(obj->arr==NULL){perror("malloc fail::");return NULL;}obj->front=obj->rear=0;obj->k=k;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队
{//队满返回falseif(myCircularQueueIsFull(obj)){return false;}//队未满尾插else{obj->arr[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队
{//队空返回falseif(myCircularQueueIsEmpty(obj)){return false;}else//队非空则头删{obj->front++;obj->front%=(obj->k+1);return true;}
}int myCircularQueueFront(MyCircularQueue* obj)//取队头
{if(myCircularQueueIsEmpty(obj))//为空则失败{return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj)//取队尾
{if(myCircularQueueIsEmpty(obj))//为空则失败{return -1;}return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//如果rear=0,rear-1=-1会导致越界访问
}void myCircularQueueFree(MyCircularQueue* obj)//销毁,开几个销几个
{free(obj->arr);free(obj);
}

提交运行: