网站建设厘金手指排名二一,阿里企业邮箱怎么样,校园网站建设需求,网站如何制作浙江创作不易#xff0c;给个三连吧#xff01;#xff01;
一、前言
对于循环队列#xff0c;博主也是源自于一道力扣的OJ题
力扣#xff1a;循环队列的设置 后来我在网上查过#xff0c;这个循环队列是有自己的应用场景的#xff01;#xff01;并不是出题者为了出题… 创作不易给个三连吧
一、前言
对于循环队列博主也是源自于一道力扣的OJ题
力扣循环队列的设置 后来我在网上查过这个循环队列是有自己的应用场景的并不是出题者为了出题而产生的所以我觉得不光要能做会这道题还得多去探究这道题的不同方式。而且这道题虽然是循环队列看似好像要把头和尾连起来但实际上实现过程中是可以不需要的这也是他非常特别的一点因此在这我会重点介绍他的数组实现和链式结构实现。
二、数组实现循环队列
怎么用数组去实现循环队列呢我们来画图研究一下 2.1 结构体的创建
typedef int QDataType;
typedef struct MyCircularQueue
{ QDataType* a;//动态数组int capacity;//记录循环队列的容量int front;//记录队首int rear;//记录队尾
} MyCircularQueue;
2.2 构造一个k长度的队列并返回
根据我们之前的思路我们要多创建一块空间
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (obj NULL){perror(malloc obj fail);exit(1);}obj-a (QDataType*)malloc(sizeof(QDataType) * (k 1));if (obj-a NULL){perror(malloc obj-a fail);exit(1);}obj-front obj-rear 0;obj-capacity k;return obj;
}
2.3 向循环队列插入一个元素。如果成功插入则返回真。
我们要往循环队列中插入一个元素那么首先必须确保队列不为满后面会封装那我们之前分析过队列不为满的情况是rear指针的下一个位置是front但是我们要注意一个特殊情况如下图 bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{if (myCircularQueueIsFull(obj))return false;obj-a[obj-rear] value;obj-rear;obj-rear % (obj-capacity 1);return true;
} 但是我们要注意的是实际上我们是多开了一个空间%的时候要把多的空间算上
2.4 向循环队列删除一个元素。如果成功删除则返回真。
我们要往循环队列中删除一个元素那么首先必须确保队列不为空后面会封装front就行了同样front也会遇到上面这种情况处理当时一样完后%上数组的实际大小
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % (obj-capacity 1);return true;
}
2.5 从队首获取元素。如果队列为空返回 - 1
直接取头指针就行了
int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}2.6 从队尾获取元素。如果队列为空返回 - 1
要注意rear指针指向的是最后一个元素的下一个位置所以要取得的话就要找到rear的前一个位置的下标这里我们不能直接让rear--因为我们只是获取队列尾的元素并不能去改变rear的指向所以我们要算出rear前面那个位置的下标其实也是一样利用%的修正让rear加上数组实际大小-1然后再%数组的大小就刚还是rear前面的位置的下标了
int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-rear obj-capacity) % (obj-capacity 1)];
}
2.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-rear;
}
2.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-rear 1)%(obj-capacity 1) obj-front;//rear为k的时候正好
}
2.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);//没必要置空因为obj用不了obj-a也用不了 front rear k 也没必要释放free(obj);//obj NULL;
}
2.10 全部代码
2.10.1 MyCircularQueue.h
#pragma once
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int QDataType;
typedef struct MyCircularQueue
{ QDataType* a;//动态数组int capacity;//记录循环队列的容量int front;//记录队首int rear;//记录队尾
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列2.10.2 MyCircularQueue.c
#includeMyCircularQueue.hMyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (obj NULL){perror(malloc obj fail);exit(1);}obj-a (QDataType*)malloc(sizeof(QDataType) * (k 1));if (obj-a NULL){perror(malloc obj-a fail);exit(1);}obj-front obj-rear 0;obj-capacity k;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{if (myCircularQueueIsFull(obj))return false;obj-a[obj-rear] value;obj-rear;obj-rear % (obj-capacity 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % (obj-capacity 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;return obj-a[(obj-rear obj-capacity) % (obj-capacity 1)];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-rear 1)%(obj-capacity 1) obj-front;//rear为k的时候正好
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);//没必要置空因为obj用不了obj-a也用不了 front rear k 也没必要释放free(obj);//obj NULL;
}
2.11 相关选择题
5.现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为(假设队头不存放数据) A (rear - front N) % N 1 B (rear - front N) % N C (rear - front) % (N 1) D (rear - front N) % (N - 1)
答这题就是根据我们上面那道题的一个变形所以我们知道肯定是%上长度的所以可以直接选B
三、链式结构实现循环队列
怎么用链式结构来实现循环队列呢我们来分析一下 3.1 结构体的创建
我们按照链式队列的思路创建一个队列结构体来管理头尾指针同时加上capacity容量和size有效数据
typedef int QDataType;
typedef struct QNode
{struct QNode* next;//节点QDataType val;//数据域
}QNode;typedef struct MyCircularQueue
{QNode* front;//链表的头指针QNode* rear;//链表的尾指针int capacity;//记录链表的容量int size;//记录链表的有效节点
}MyCircularQueue;
3.2 构造一个k长度的队列并返回
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (obj NULL){perror(malloc fail);exit(1);}obj-front obj-rear NULL;obj-size 0;obj-capacity k;return obj;
}3.3 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{//如果为满了直接就返回falseif (myCircularQueueIsFull(obj))return false;//不满足就创建节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-val value;newnode-next NULL;//创建成功要考虑队列为空和不为空的情况if (myCircularQueueIsEmpty(obj))//为空让新节点成为头obj-front obj-rear newnode;else//不为空让tail继续往后遍历{obj-rear-next newnode;obj-rear newnode;}obj-size;return true;
}3.4 向循环队列删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{//为空就没有删的必要了if (myCircularQueueIsEmpty(obj))return false;//不为空删除头节点让下一个节点成为新的头然后释放掉QNode* cur obj-front-next;free(obj-front);obj-front cur;obj-size--;return true;
}
3.5 从队首获取元素。如果队列为空返回 - 1
int myCircularQueueFront(MyCircularQueue* obj)
{//为空返回1if (myCircularQueueIsEmpty(obj))return -1;//不为空就获取头指针的数据return obj-front-val;
}
3.6 从队尾获取元素。如果队列为空返回 - 1
int myCircularQueueRear(MyCircularQueue* obj)
{//为空返回1if (myCircularQueueIsEmpty(obj))return -1;//不为空就获取尾指针的数据return obj-rear-val;
}
3.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-size 0;
}3.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return obj-size obj-capacity;
}
3.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{//本质是链表要一个个释放QNode* pcur obj-front;//用来遍历删除的while (pcur){QNode* next pcur-next;free(pcur);pcur next;}free(obj);
}
3.10 全部代码
3.10.1 MyCircularQueue.h
#pragma once
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int QDataType;
typedef struct QNode
{struct QNode* next;//节点QDataType val;//数据域
}QNode;typedef struct MyCircularQueue
{QNode* front;//链表的头指针QNode* rear;//链表的尾指针int capacity;//记录链表的容量int size;//记录链表的有效节点
}MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
3.10.2 MyCircularQueue.c
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (obj NULL){perror(malloc fail);exit(1);}obj-front obj-rear NULL;obj-size 0;obj-capacity k;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{//如果为满了直接就返回falseif (myCircularQueueIsFull(obj))return false;//不满足就创建节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-val value;newnode-next NULL;//创建成功要考虑队列为空和不为空的情况if (myCircularQueueIsEmpty(obj))//为空让新节点成为头obj-front obj-rear newnode;else//不为空让tail继续往后遍历{obj-rear-next newnode;obj-rear newnode;}obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{//为空就没有删的必要了if (myCircularQueueIsEmpty(obj))return false;//不为空删除头节点让下一个节点成为新的头然后释放掉QNode* cur obj-front-next;free(obj-front);obj-front cur;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{//为空返回1if (myCircularQueueIsEmpty(obj))return -1;//不为空就获取头指针的数据return obj-front-val;
}int myCircularQueueRear(MyCircularQueue* obj)
{//为空返回1if (myCircularQueueIsEmpty(obj))return -1;//不为空就获取尾指针的数据return obj-rear-val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{return obj-size obj-capacity;
}void myCircularQueueFree(MyCircularQueue* obj)
{//本质是链表要一个个释放QNode* pcur obj-front;//用来遍历删除的while (pcur){QNode* next pcur-next;free(pcur);pcur next;}free(obj);
}
四、总结 我们会发现在这边无论是用数组实现和链表实现本质上我们只是从逻辑层次上把它认为是相连的但是物理层次上并没有把它连在一起虽然链表是可以做到相连的但是相连的话会比较复杂不相连我们也可以解决只要保证我们能够控制得住边界问题就行
