数据结构——循环队列的实现(上）

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

之前我们学习过数据结构中的栈和队列，详情可点击这里数据结构——lesson5栈和队列详解进行查看🥳🥳，队列是一种先进先出的结构，但是我们之前讲的队列都是类似于线性的物理结构，这次我们所介绍的队列则是一直类似于环状的循环结构，它依旧保持着队列的特性——先进先出。

1.循环队列的介绍

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

循环队列的实现应该支持如下操作：

1. MyCircularQueue(k): 构造器，设置队列长度为 k 。
2. Front: 从队首获取元素。如果队列为空，返回 -1 。
3. Rear: 获取队尾元素。如果队列为空，返回 -1 。
4. enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
5. deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
6. isEmpty(): 检查循环队列是否为空。
7. isFull():检查循环队列是否已满。

题目链接——循环队列OJ题大家也可以在学习完栈和队列后自己尝试写一写。

2.循环队列实现思路分析

首先根据题目要求，队列长度为k，所以一开始我们要使用malloc开辟k个节点的空间，而不是和之前的队列一样在增加数据时再开辟节点，循环队列的长度是固定的，最开始就已经开辟好了，所以不需要再在使用时开辟节点空间。

如上图所示，已经在内存中开辟了完整的空间，最开始队列的头尾指针都指向开始的位置，每加一个元素，rear指针也就是尾指针的位置就往后挪动一位，删除数据就把头指针front往后挪一位，当rear指针指向最后一个元素时，队列满了，此时的判断条件应该时rear->pNext = front;

也就是说rear的下一个位置是front，如下图所示：

思考一下：rear指向的是尾部的元素还是尾部元素的下一位呢？

1.zz如果rear指向的是尾部元素，那么在实现时判断循环队列是否满的条件就是rear->pNext = front;

但是💥💥判断循环队列是否为空的条件就不简单是rear == front，因为在插入第一个元素时，front指向该元素，rear指向最后一个元素也就是刚刚插入的第一个元素，因为此时队列中只有一个元素，此时rear == front ，但此时循环队列不为空；

2.但如果循环队列的rear指针指向尾部元素的下一个就好判断了，为空时rear==front；

不为空时rear！=front；即使只有一个元素，rear也不指向该元素而是指向该元素的下一位，但是💥💥在判断循环队列是否满时又出了问题，当循环队列满了的时候，rear指向队尾元素的下一个，此时rear指向front，这不就和为空的条件冲突了吗？

解决办法：

🥳🥳1.针对第一种rear指向尾部元素：

可以考虑在创建队列时不单单创建front（队列头指针）和rear（队列尾指针）这两个元素，可以增加一个 size来记录此时队列里的节点个数；

🥳🥳2.针对第二种rear指向尾部元素的下一个位置：

①也可以增加一个size来记录存放的节点个数

②考虑多开辟一个节点的空间（需要k个节点就开辟k+1个节点的空间），剩下一个节点的位置不存放数据，是专门用来防止队列满时rear的下一个元素指向front，如果增加一个空闲的位置，队列满时rear的下一个位置就不再指向front

💫💫在决定选哪种方法之前，我们先要考虑一下是使用链表来实现还是使用数组也就是顺序表来实现循环队列；当然这里土土会将两种方法都写下来，并和大家一起分析两种方法的优劣之处，以便大家选择合适和喜欢的形式🥰🥰（对于顺序表链表有疑问的可以在土土的数据结构专栏里——数据结构学习笔记 进行查看复习哦~）

3.用单链表实现循环队列

✨✨经过我深思熟虑（其实是随便选的😎😎），决定采用第一种rear指向队尾元素的方法来实现，虽然第二种方法我给出了两种解决办法，但是我发现第一种方法在求队尾元素时异常的方便，只要return rear->data就好了，如果是第二种rear指向队尾元素的下一个，那么我们求队尾元素时还需要找到rear的前一个指针，如果我们使用双向链表就会很简单，但这里我选择使用单链表来实现；

3.1设计队列结构

前面我们提到过设计队列时考虑加上一个size记录存放节点个数以便判断队列是否为空

typedef struct {
  CQNode* front;
  CQNode* rear;
  int size;//记录容量
} MyCircularQueue;

队列的节点和单链表一致：data存放数据；pNext存放下一个节点指针

// 链式结构：表示队列 
typedef int CQDataType;
typedef struct CQListNode
{
  struct CQListNode* pNext;
  CQDataType data;
}CQNode;

3.2构造队列（k个节点）

MyCircularQueue(k): 构造器，设置队列长度为 k

这里我们除了需要malloc k个节点外，还需要将这k个节点串联在一起使他们物理结构上成环（对于malloc有疑问的可以查看土土的博客——C语言动态内存函数介绍）代码如下：

//构造k个节点的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
  
  //开辟k个空间并链接k个节点

  CQNode* kqueue = (CQNode*)malloc(sizeof(CQNode) * k);
  if (kqueue == NULL)
  {
    perror("malloc fail1");
    return NULL;
  }
  for (int i = 0; i < k - 1; i++)//注意这里是k-1，因为尾节点需要单独链接头节点
  {
    (kqueue + i)->pNext = kqueue + i + 1;
  }
  //最后再把尾指针指向的下一位指向头即可成环
  (kqueue + k - 1)->pNext = kqueue;
  
  //开辟循环队列空间
  MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  if (queue == NULL)
  {
    perror("malloc fail2");
    return NULL;
  }


  queue->front = kqueue;
  queue->rear = kqueue;//尾指向最后一个元素，不是最后元素的下一个
  queue->size = 0;//记录队列大小
  return queue;

}

调试时我们发现成功构造了循环队列：

后面pNext又回到了最开始的位置说明我们链接成功啦🎉🎉🎉

我们还将队列的头尾指针与开辟的k个节点做了连接，使得队列的头尾指针指向了k个节点的地址，并将size初始化为0；

3.3 向循环队列插入一个元素

myCircularQueueEnQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。代码如下：

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
  assert(obj);
  //判断队列是否满了
  if(myCircularQueueIsFull(obj))
    {
        return false;
    }
  
  //插入队列
  //1.队列无元素的情况
  if (myCircularQueueIsEmpty(obj))
    {
        obj->front->data = value;
        obj->rear->data = value;
        obj->size++;
        return true;
    }
//2.队列有元素的情况
    obj->rear->pNext->data = value;
    obj->rear = obj->rear->pNext;
    obj->size++;
    return true;
}

🥳🥳 ①这里首先要判断队列是否满了，如果满了则不能再插入元素直接返回false；

🥳🥳② 其次因为我们的rear是指向最后一个元素的所以在插入元素时要分两种情况来看——一种只有一个节点的情况头尾指针都需要变；另一种存放多个节点的情况只需要改变尾指针；

🥳🥳③此外增加元素size++；

✨✨④最后判断循环队列是否为空函数在下面介绍；

3.4判断循环队列是否为空

myCircularQueueIsEmpty(): 检查循环队列是否为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
  assert(obj);
  if (obj->size == 0)//size为0时队列为空
    return true;
  return false;
}

3.5判断循环队列是否满了

myCircularQueueIsFull(): 检查循环队列是否已满。

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
  assert(obj);
  //?if(obj->size == k)
  if (obj->rear->pNext == obj->front)
    {
    //只有一个节点的情况
    if (obj->size != 0)
    {
      return true;
    }
    }
  return false;
}

这里我们看到我打了一个？，obj->size ==k是不能判断队列是否满了的，因为k并没有作为参数传给判满函数，我们根本不能使用k，k

只在构造队列时出现过；

✨✨我们还发现这里出现了只有一个节点的情况，因为当队列构造时传的k == 1，也就是整个循环队列只有一个节点，那么无论队列中是否有节点rear的下一个位置始终时front，此时该判断条件不成立，所以我们需要将该情况单独列出来，当rear->pNext 等于front时并且obj->size 不等于0时才能判断队列满了return true；其他情况return false；

3.6从循环队列中删除一个元素

myCircularQueueDeQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。注意队列先进先出，是头删。

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
  assert(obj);
  if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
  //头删，因为是先进先出
  //1.只有一个元素，此时头尾指针指向同一个位置，都需要改
  if (obj->front == obj->rear)
  {
    obj->front = obj->front->pNext;
    obj->rear = obj->rear->pNext;
    obj->size--;
    return true;
  }
  //2.多个元素
  obj->front = obj->front->pNext;
  obj->size--;
    return true;
}

这里和插入一个元素一样也要分两种情况，size对应-1；就不过多赘述

3.7 从队首获取元素

myCircularQueueFront: 从队首获取元素。如果队列为空，返回 -1 。

int myCircularQueueFront(MyCircularQueue* obj) 
{
  assert(obj);
  if(myCircularQueueIsEmpty(obj))
        return -1;
  return obj->front->data;
}

3.8获取队尾元素

Rear: 获取队尾元素。如果队列为空，返回 -1 。

int myCircularQueueRear(MyCircularQueue* obj) 
{
  assert(obj);
  if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
  return obj->rear->data;
}

3.9销毁循环队列

void myCircularQueueFree(MyCircularQueue* obj)
{
  assert(obj);
  free(obj->front);
  free(obj);
  return;
}

3.10结果如下

数据结构——循环队列的实现（下）：https://developer.aliyun.com/article/1496805