[数据结构与算法]【数据结构】2.1设计循环队列

【数据结构】设计循环队列

“Don’t dwell on missed opportunities Just remember to live in the present.”

Hello，大家好，我们又见面了。😊

不知道大家对上一篇博客中栈和队列理解咋样啦。今天让我们快马加鞭进入下一个层次，一起来学习一下循环队列的设计??

题目链接:622. 设计循环队列

1.为什么我们需要循环队列

虽然在上篇博客中，我们实现队列的底层为链表。但是当我们用数组来实现一个队列时会存在一些缺陷。这时候便我们需要进行改进。

先让我们来看一看用数组实现队列的示意图：

这有什么缺陷呢？你且看：

在上图入队和出队的过程中，Rear已经指向数组最后一个元素了，此时如果再继续入队会产生数组越界的的错误。可实际上我们在数组下标为0，1，2，3的位置上的的地方还是空闲的，这中情况我们称之为：“假溢出”

也就是说==我们每次出队，原来队头的空间就运用不了了，存在严重的内存浪费。==

所以我们就进行了这样一个设计：当Front或者Rear等于队列最大容量size时，让他们自动回到0这个位置，也就产生一个循环。故称：循环队列。

由于循环队列的特性，我们可以把它想象成环状（这对我们理解问题很有帮助）

循环队列有这样的特点：

1. 循环队列是定长的；
2. 循环队列的空间可以重复利用

2.设计循环队列时的问题

我们借助想象中的循环队列示意图来理解我们遇到的问题：

如上图所示：判断循环队列为空与满时的标志都是Rear==Front

判断条件将出现二义性

这里有三种解决方法：

1. 设置一个flag变量，出队时置为0，入队置为1

   （这样我们就可以知道到底是入队还是出队导致了Rear==Front，这样 用flag来判断空还是满）

2. 增加一个size变量，动态记录队列的长度，当size==MaxSize时队列为满。

3. 增加一个空余的空间（不用来存储数据）

   （队列为满的条件为：Front-Rear==1,

   ? 队列为空的条件为：Front==Rear）(实际实现会比这个条件要复杂，后面说)

   

这里我们在实现时主要运用第三种（空余空间）的方法来实现我们的循环队列

3.循环队列的实现

?我们将分别用数组和链表作为底层来实现我们的循环队列

3.1 接口汇总（注：源自leetcode）

//构造器，设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k);
//向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
//从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);
//从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj);
//获取队尾元素。如果队列为空，返回 -1 
int myCircularQueueRear(MyCircularQueue* obj);
//检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) ;
//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj);

3.2 数组实现循环队列

3.2.1 结构设计

typedef struct {
    int* a;
    int front;
    int rear;
    int size;	//有效空间数量 
} MyCircularQueue;

3.2.2 创建初始化循环队列

MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->size=k; 
    return obj;
}

注意需要多开一个空余空间

3.2.3 入队

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear]=value;
	if(obj->rear==obj->size)
		obj->rear%=obj->size;
	else
		obj->rear++;
	return true;
}

根据定义，rear指向队尾元素后一个位置，入队时，我们直接放在rear位置。

放完数据后调整rear时得有循环的逻辑判断处理。

思考：直接放数据会不会越界？

不会，初始时rear=0，不越界，每次放完数据的调整后rear都满足rear<=size,下标size处我们是开辟了空间的。

同时这也提醒我们：空闲的空间是动态的，不一定一直是最后的那个空间。最后那个空间是有可能放数据的。

3.2.4 出队

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
	if(myCircularQueueIsEmpty(obj))
		return false;
	if(obj->front==obj->size)
		obj->front%=obj->size;
	else
		obj->front++;
	return true;		
}

注意：front的循环调整

3.2.5 获取队头元素

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

注意非空的判断！！！下同

3.2.6 获取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) 
{
	if(myCircularQueueIsEmpty(obj))
		return -1;
	return obj->rear==0?obj->a[obj->size]:obj->a[obj->rear-1];
}

3.2.7 判断队列是否为空

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

3.2.8 判断队列是否满

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
	if(obj->rear==obj->size&&obj->front==0)
		return true;
	return obj->front-obj->rear==1;
}

考虑特殊情况，也是我们上面说的稍复杂的判断条件

3.2.9 销毁队列

“一出好戏，终将落幕”

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

3.3 链表实现循环队列

3.3.1 结构设计

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

typedef struct 
{
    Node* front;
    Node* rear;
    int size;
} MyCircularQueue;

3.3.2 创建初始化队列

MyCircularQueue* myCircularQueueCreate(int k) 
{
	MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	Node *head=NULL,*tail=NULL;
	for(int i=0;i<k+1;i++)
	{
		Node* newnode=(Node*)malloc(sizeof(Node));
		if(head==NULL)
			head=newnode;
		else
			tail->next=newnode;
		tail=newnode;
	}
    tail->next=head;
	obj->size=k;
	obj->front=obj->rear=head;
	return obj;
}

初始化时就把整个链表创建出来，要熟悉整个创建链表的操作

要将头尾相连形成循环

3.3.3 入队

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
	if(myCircularQueueIsFull(obj))
		return false;
	obj->rear->data=value;
	obj->rear=obj->rear->next;
	return true;
}

因为链表直接就首尾相连接起来了，直接就可以调整rear，下同

3.3.4 出队

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
	if(myCircularQueueIsEmpty(obj))
		return false;
	obj->front=obj->front->next;
	return true;
}

3.3.5 获取队头元素

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

3.3.6 获取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) 
{	
	if(myCircularQueueIsEmpty(obj))
		return -1;
	Node* p=obj->front;
	while(p->next!=obj->rear)
		p=p->next;
	return p->data;
}

此处要找rear前面一个节点

3.3.7 判断队列是否为空

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

3.3.8 判断队列是否满

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

3.3.9 销毁队列

void myCircularQueueFree(MyCircularQueue* obj) 
{
	Node* cur=obj->front;
	int size=obj->size+1;
	while(size--)
	{
		Node* next=cur->next;
		free(cur);
		cur=next;
	}
	obj->front=obj->rear=NULL;
	free(obj);
}

🤔思考题：为什么不直接free(head)，free(obj)？？？【链表的内存结构，内存泄漏】

🤗到此我们这篇循环队列的博客也接近尾声了。

😊希望大家能在阅读完后有所收获！！！这将是对我最大的激励！

敲代码，码字，作图不易，期待一个小小的点赞??

如果你对博客内容有什么疑惑，或者对思考题有什么不解，很欢迎大家来和我交流讨论哦?

本期所有的代码我将传到我的gitee仓库中，如有需要可自行下载

仓库传送门：数据结构

我们下篇博客见！😘

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读