循环队列（Circular Queue）详解

一、循环队列简介

在实际开发中，队列是一种常用的数据结构，而循环队列（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);
}