建立网站怎么申请,流程平台,建设英文网站的请示,淮北seo排名前言 今天我们将学习循环队列实现#xff0c;我们首先介绍队列的概念和结构#xff0c;之后一步步讲解循环队列由来与实现。 一、队列的概念与结构
1、队列的概念
队列#xff1a; 只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表。队列是…前言 今天我们将学习循环队列实现我们首先介绍队列的概念和结构之后一步步讲解循环队列由来与实现。 一、队列的概念与结构
1、队列的概念
队列 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。队列是一种先进先出FIFOfirst in first out的线性表允许插入的一端称为队尾允许删除的一端称为队头。这种结构很符合我们生活中的习惯排在第一个的优先出列最后来的当然就在队伍最后。
2、队列的结构 3、实例
比如 ①键盘的输入输入“abc”输出也是“abc”②生活中的排队等等。
二、循环队列
1、队列的实现方式有两种
线性表有顺序存储和链式存储。同样队列作为一种特殊的线性表也同样存在这两种存储方式。
2、队列顺序存储的不足
队列的顺序存储其实就是使用数组来实现。数组实现队列一般数组下标为0的一端为队头数组尾为队尾。 入队 入队是在队尾插入数据即在数组尾追加一个数据不需要移动数据所以时间复杂度为O1。如下图
出队 出队是在队头删除数据即数组的头删需要挪动后面的所有元素保证所有元素都从队头出去此时时间复杂度为ON。如下图
但是每一次出队列都需要挪动数据效率不太好。那能不能不将队头的位置固定在下标为0的位置即每出队列一次队头向后跳过一个元素此时时间复杂度为O(1)。如下图
使用这种方法出队列虽然效率提高了但又引出了一个新问题——“假溢出”。 假溢出 如下图假设队列的总个数为5当数组末尾的空间已经被占用了此时再入队就会产生数组越界的问题可实际上我们队列在下标0、1、2的地方还是空闲的。这种现象就叫做“假溢出”。
那“假溢出”有没有解决方案呢 答案是有的有三种解决方案。 ①当队列满了就扩容。但缺点就是空间利用率低。 ②不改变队头的位置挪动数据。缺点时间复杂度为O(N)。 ③循环队列。优点效率高。缺点实在来说就只有队列大小实现前要确定好。
3、循环队列的定义
循环队列 我们把队头与队尾是相互链接的队列称为循环队列。因为循环队列首尾相连所以只要队列没有满就可以插入数据不会产生假溢出问题。 理解 ①队列的大小要事先确定②队列首尾相连。 实现①顺序存储实现②链式存储实现。这两种实现方式哪种更好呢 答案是顺序存储实现更好。假设队列大小为5队首指针为front队尾指针的下一个为rear分析如下 ①链式存储实现 问题1队列空与队列满情况一样如下图 解决方案 ①队列成员加一个成员size变量储存有效数据个数——队列满size k队列空size 0。 ②队列多开辟一个空间——队列满rear-next front;队列空rear front。这里我们使用方案2解决。 问题2取队尾元素不好取如下图 解决方案①双向链表②队列加一个成员变量prev储存rear的前驱结点。 ②顺序存储实现 问题1怎么实现首尾相连即rear与front到了下标k的位置怎么回到下标0的位置。 tip ①取队尾rear - 1 k 1% k 1 ②队列满rear 1% k 1 front队列空rear front 总结 由上分析可知链式存储对比顺序存储的劣势有①多一个指针域浪费空间②不好找队尾元素③代码实现复杂等等。所以下面我们将使用顺序存储实现循环队列。
4、循环队列的实现
队列的实现应该支持如下操作
MyCircularQueue(k)构造器在堆区申请队列对象初始化队首、队尾指针、队列长度。Front获取队首元素。如果队列为空返回-1。Rear获取队尾元素。如果队列为空返回-1。enQueue(value)入队列——队尾插入一个元素。如果成功插入返回真。deQueue()出队列——队头删除元素。如果成功删除返回真。isEmpty()检查队列是否为空。isFull()检查队列是否已满。Free()销毁队列。
循环队列在力扣有题目大家可以先去做一做。链接在下面。 循环队列链接
循环队列的代码实现
//循环队列的结构
typedef struct
{int* a;//指向堆区开辟的数组int front;//队首指针——表示队首位置int rear;//队尾指针——表示队尾的下一个int length;//队列长度
} MyCircularQueue;//初始化——在堆区开辟队列对象与队列空间并初始化队首与队尾,队列长度
MyCircularQueue* myCircularQueueCreate(int k)
{//在堆区开辟循环队列的对象MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//判断是否开辟成功if(NULL obj){//打印错误信息perror(malloc fail);return NULL;}//申请队列空间——为避免队列满与空情况一样队列多开辟一个空间obj-a (int*)malloc(sizeof(int) * (k 1));//判断是否开辟成功if(NULL obj){//打印错误信息perror(malloc fail);return NULL;}//初始化队首、队尾指针obj-front 0;obj-rear 0;//初始化队列长度obj-length k 1;//返回在堆区开辟循环队列对象return obj;
}
//检查队列是否已满满返回真
bool myCircularQueueIsFull(MyCircularQueue* obj)
{//断言obj不为空assert(obj);//相等则满return (obj-rear 1) % obj-length obj-front;
}//入队列队尾插入数据成功返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{assert(obj);//调用myCircularQueueIsFull判断队列是否满if(myCircularQueueIsFull(obj)){return false;//满直接返回假}//队尾插入数据obj-a[obj-rear] value;//插入之后rear1obj-rear;//rear每一次1后防止越界当rear k时取模回到下标0obj-rear % obj-length;//插入成功返回真return true;
}
//检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);//相等队列为空return obj-rear obj-front;
}
//出队列队头出队列即front出队列成功返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{assert(obj);//调用myCircularQueueIsEmpty判断队列是否为空if(myCircularQueueIsEmpty(obj)){return false;}//删除队头即frontobj-front;//front每一次1后防止越界即当front k时取模回到下标0obj-front % obj-length;//出队列成功返回真return true;
}
//获取队首元素。如果队列为空返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj)
{assert(obj);//调用myCircularQueueIsEmpty判断队列是否为空if(myCircularQueueIsEmpty(obj)){//为空返回-1return -1;}//不为空返回队首元素return obj-a[obj-front];
}
//获取队尾元素。如果队列为空返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj)
{assert(obj);//调用myCircularQueueIsEmpty判断队列是否为空if(myCircularQueueIsEmpty(obj)){//为空返回-1return -1;}//返回队尾元素rear为队尾的下一个(rear - 1 obj-length) % obj-length)即为队尾位置注意不能使用--操作符return obj-a[(obj-rear - 1 obj-length) % obj-length];
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj);//注意销毁的顺序要先释放队列结构中的数组再释放队列对象free(obj-a);//free之后obj-a指向不变防止野指针置为空obj-a NULL;free(obj);obj NULL;
}希望对大家有帮助循环队列就讲解完成了。循环队列有个缺点就是必须先开辟队列空间队列的大小实现就要确定好那有没有队列空间按需提供的呢答案是有的就是链式队列。在下一期作者会对其详细讲解。
