一、循环队列简介
在实际开发中,队列是一种常用的数据结构,而循环队列(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* {
MyCircularQueue* cq = (MyCircularQueue*)((MyCircularQueue));
cq->a = (*)(() * (k + ));
cq->front = ;
cq->tail = ;
cq->k = k;
cq;
}
{
(myCircularQueueIsFull(obj)) ;
obj->a[obj->tail] = value;
++obj->tail;
obj->tail %= (obj->k + );
;
}
{
(myCircularQueueIsEmpty(obj)) ;
obj->front = (obj->front + ) % (obj->k + );
;
}
{
(myCircularQueueIsEmpty(obj)) ;
obj->a[obj->front];
}
{
(myCircularQueueIsEmpty(obj)) ;
(obj->tail == ) obj->a[obj->k];
obj->a[obj->tail - ];
}
{
obj->front == obj->tail;
}
{
(obj->tail + ) % (obj->k + ) == obj->front;
}
{
(obj->a);
(obj);
}


