文章目录

  • 前言
  • 一、循环队列
  • 二、实现循环队列
    • 1.思路分析
    • 2.代码中的循环队列
  • 总结

前言

(来源）

建议基本掌握普通队列的操作及实现再看本文章

一、循环队列

循环队列是基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环
正常我们平时实现的普通队列，大部分是以链表的方式存储，循环队列当然也可以，
但是循环队列使用顺序表的方式较普遍。

原因是无论是链表还是顺序表实现，都要考虑它的三种状态

  • 空队列
  • 有元素但未满的队列
  • 满队列

而这时候，顺序表的判断操作比起链表要简单，故普遍使用顺序表来实现循环队列

二、实现循环队列

1.思路分析

用两个下标来标识

  1. front–>头
  2. rear–>尾

初始状态的时候，front和rear都指向开始的位置，
队列满的时候在这个没有多开一个空间的队列中，满了之后也会两个下标指向同一个位置，
这时候就无法区分front==rear是空队列还是满队列

考虑到要区分这两个状态，我们可以多开一个空间，使得rear+1==front就为满队列，原来的rear==front就为空队列

循环队列的动图

注意：上面动画中的n是队列的总长度，也就是它把多开的那个一个空间也算进去了，
我下面的N表示的是循环队列的有效长度，也就是没把多开的一个空间算进去，
N+1=上面动画的n

那么循环队列的三个状态中最主要的两个已经解决了，循环队列的实现也就基本可以实现了

下面就是在代码中如何实现上面的思路

2.代码中的循环队列

下面代码可以直接复制到LeetCode运行–>✨题目地址

typedef struct {    int *a;//顺序表地址    int Front;//头下标    int rear;    int N;} MyCircularQueue;//MyCircularQueue(k): 构造器，设置队列长度为 k 。MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));    obj->a=(int*)malloc(sizeof(int)*(k+1));    obj->Front=obj->rear=0;    obj->N=k+1;    return obj;}//isEmpty(): 检查循环队列是否为空。bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->Front==obj->rear;}//isFull(): 检查循环队列是否已满。bool myCircularQueueIsFull(MyCircularQueue* obj) {    return obj->Front==(obj->rear+1)%obj->N;}//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    if(myCircularQueueIsFull(obj))        return false;    obj->a[obj->rear]=value;    obj->rear++;    obj->rear%=obj->N;    return true;}//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))         return false;    obj->Front++;    obj->Front%=obj->N;    return true;}//Front: 从队首获取元素。如果队列为空，返回 -1 。int myCircularQueueFront(MyCircularQueue* obj) {     if(myCircularQueueIsEmpty(obj))        return -1;    return obj->a[obj->Front];}//Rear: 获取队尾元素。如果队列为空，返回 -1 。int myCircularQueueRear(MyCircularQueue* obj) {     if(myCircularQueueIsEmpty(obj))        return -1;        return obj->a[(obj->rear-1+obj->N)%obj->N];}void myCircularQueueFree(MyCircularQueue* obj) {    free(obj->a);    free(obj);}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了循环队列的实现，而更多的操作实现细节还需要各位自行实现才能知道