淮安网站建设要多少钱,长沙景点分布图,海南网上报名系统,网站空间200m目录 循环队列的结构循环队列的实现循环队列的创建循环队列为空判断循环队列为满判断入队出队返回循环队列首元素返回循环队列尾元素释放循环队列 循环队列的结构
循环队列是队列的一种特殊结构#xff0c;它的长度是固定的k#xff0c;同样是先进先出#xff0c;理论结构是… 目录 循环队列的结构循环队列的实现循环队列的创建循环队列为空判断循环队列为满判断入队出队返回循环队列首元素返回循环队列尾元素释放循环队列 循环队列的结构
循环队列是队列的一种特殊结构它的长度是固定的k同样是先进先出理论结构是首尾相连的环形循环结构。其理论结构大致如下 具体结构描述可以参考LeetCode: 622. 设计循环队列的题目要求大致如下 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
循环队列的实现
循环队列的实现方式同样有两种–数组链表
数组循环队列 数组实现方式顾名思义就是动态开辟一个长度为k的数组那要怎么达到循环呢我们可以定义两个数一个指向队列头元素int front一个指向队列尾元素的下一个int back此处指向队尾下一个是为了方便队列空和满的判断这样当back走到最后一个时我们只需要将他重新置成0便又到了队列第一个元素如此设计理论上就达到了循环结构。 新的问题又来了当front back时要怎么区分队列是空还是满两种解决方案 增加一个size记录有效数据的节点数size 0队列就是空size k队列就是满。多开辟一个空间k1front back便是空(back1)%(k1) front就是满即在理论结构中back指向的下一个位置是front下文会讲解。 链表循环队列 链表实现的循环队列更有点循环的味即将尾指针的next指向头形成真正的循环但实现起来不如数组方便。链表实现循环队列同样要定义两个指针一个指向循环队列的头元素phead,一个指向循环队列尾元素的下一个ptail。判断循环队列空和满的方法和数组相似只不过判断条件从判断值相同改为判断址相同第二种方法判满改为phead ptail-next。 但用链表设计循环队列也会有新的困难1. 获取循环队列尾元素不方便还要遍历队列寻找2. 定义结构体时还要多定义一个装链表节点的结构体这也增加了代码的难度。 所以不论是用数组还是用链表实现循环队列都有各自的好处和问题下面实现循环队列我所介绍的方法是数组实现法判满和判空用的是多定义一个节点法。
依据上述方法可以定义如下结构体变量
typedef struct
{int* a;//数组int front;//队列头int back;//队列尾下一个位置int k;//循环队列可存储数据长度
} MyCircularQueue;循环队列的创建
注意此处所给的函数返回值类型为MyCircularQueue正是上述结构体类型。故须先动态开辟一个结构体类型大小并将front和back初始化为0然后再利用结构体指针来开辟长度为k1的数组最后返回结构体指针。 这样动态开辟而不直接定义结构体变量MyCircularQueue ps是因为这是在函数中出了函数的作用域此结构体变量就会销毁所以需要malloc将结构体动态开辟在堆区。
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* ps (MyCircularQueue*)malloc(sizeof(MyCircularQueue));ps-a (int*)malloc(sizeof(int)*(k1));ps-back ps-front 0;ps-k k;return ps;
}循环队列为空判断
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-back;
}循环队列为满判断 循环队列为满大致可以分为以上两种情况。
情况1 当队列尾back来到最后一个时此时如果back 1的话就会超过k 1的范围而我们的目的是想知道在循环队列中back 1后的位置即下标为0的位置所以此时我们只要将(obj-back 1)%(obj-k 1)此式的值便为0情况2 back 1的范围在k 1内此时判断back 1即可若(obj-back 1)%(obj-k 1)也不会影响值。
如此将两式合并便得到了简化的效果。
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-back1)%(obj-k1) obj-front;
}入队
题目描述enQueue(value):向循环队列插入一个元素。如果成功插入则返回真。 既如此那么先判断循环队列是否已满若满则返回false否则入队新值并将obj-back值更新obj-back % obj-k1;
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj))return false;obj-a[obj-back] value;obj-back;obj-back % obj-k1;return true;
}出队
题目描述deQueue():从循环队列中删除一个元素。如果成功删除则返回真。 与入循环队列相似。
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % obj-k1;return true;
}返回循环队列首元素
题目描述Front:从队首获取元素。如果队列为空返回 -1 。 先判断循环队列不为空若为空返回-1不为空返回下标为obj-front的值。
int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];}返回循环队列尾元素
题目描述Rear:获取队尾元素。如果队列为空返回 -1 。 同样要先判断循环队列是否为空为空返回-1。此处计算obj-back上一个的下标的方法中obj-back-1后还要加obj-k1是为了防止obj-back指向下标为0的情况再% (obj-k1)是为了防止超出下标范围的情况与判断队满相似。
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-back-1obj-k1) % (obj-k1)];
}释放循环队列
依次释放即可先释放最内层的数组然后释放最外层的结构体。
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
