【队列】循环队列（CircularQueue）详解

文章目录 一、循环队列简介二、循环队列的判空和判满三、循环队列的实现leetcode 622. 设计循环队列

一、循环队列简介

在实际开发中，队列是一种常用的数据结构，而循环队列（Circular Queue）则一般是一种基于数组实现的队列（也可使用循环链表）。与传统的 FIFO 队列相比，循环队列通过将数组首尾相连形成一个 “环”，能够更高效地利用内存空间。

循环队列的主要思想是：当队尾指针到达数组末端时，如果数组前面还有空余空间，就可以从数组头部重新利用这些空间进行入队操作。也就是说，数组的末端和头部通过逻辑上的连接，形成一个环状结构，从而避免了顺序队列中由于出队操作而导致的空间浪费问题。

如下图就是一个典型的循环队列，其中的 front 表示头指针，指向队头。rear 则表示尾指针，指向队尾元素的下一个位置。

二、循环队列的判空和判满

在循环队列中，front 与 rear 都是可以循环移动的，当队空时，front == rear 成立；当队满时，front == rear 也成立。因此显然不能只凭 front == rear 来判断队空还是队满。

为了解决这个问题，在循环队列中约定：少用一个元素空间，当队尾标识的 rear在队头标识front 的上一个位置时，队列为满。此时，判断队空和队满的条件分别如下：

队空时：front == rear

队满时：(rear + 1) % MAXSIZE == front

其中，MAXSIZE 是队列容量的大小

两种情况下队列中指针的状态如下图所示：

既然少一个元素空间，这就意味着，如果要存储的数据个数最大为 k，那么你需要开辟的循环队列的大小应为 k+1

三、循环队列的实现

我们来以具体的一道题目来实现循环队列的各种操作

leetcode 622. 设计循环队列

typedef struct { int* a; int front; // 头“指针”指向队头数据 int tail; // 尾“指针”指向队尾的下一个位置 int k; // 一会儿开辟的队列大小为 k+1 } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); // 前面先实现的函数要用到这两个接口，所以事先声明一下 // 循环队列的初始化 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->a = (int*)malloc(sizeof(int)*(k+1)); cq->front = 0; // 初始化数据 cq->tail = 0; cq->k = k; return cq; } // 入队 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; // 满了就不能再入了 obj->a[obj->tail] = value; // 将数据入进来 ++obj->tail; // 更新tail obj->tail %= (obj->k+1); // tail 自增了之后可能超出循环队列的大小范围所以要取模 // 模的是循环队列的大小 k+1 return true; } // 出队 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; // 为空就不能再删 obj->front = (obj->front+1)%(obj->k+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; if(obj->tail == 0) return obj->a[obj->k]; // 跨越了一个循环的情况 else return obj->a[obj->tail-1]; } // 判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail; } // 判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1) % (obj->k+1) == obj->front; // tail的后一个是front说明满了，但是有可能tail+1跨过了一个循环。所以要取模 } // 释放 void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); // 注意这里要先释放结构体内的数组！！！不然会可能内存泄漏 free(obj); }