当前位置：首页 > news >正文

数据结构：设计循环队列

news 2026/7/11 5:41:19

这道题让我们设计一个循环队列，队尾的下一个元素是队头，但不同的是，这个循环队列是固定大小的，队列满则无法插入元素。
我们有两种选择可以设计这个循环队列，一种是链表，一种是顺序表，我们比较一下再实现循环队列上的优劣来决定采用哪种选择。

选择哪种底层结构

在初始化的时候，链表要申请k个结点的空间，顺序表只需要申请k个元素的大小，从初始化来看，顺序表比链表简单。。

在入队的时候，链表插入一个数据，ptail就往后移，直到队列满，ptail就指向最后一个结点。

顺序表入队就入到rear所在的位置，rear后移一个，当队列满了的时候，rear=4，rear与k（k=4）取模就能回到原来的位置。

入队方面这两个差不多。

出队的时候，链表的phead只需要后移一个就可以了，顺序表的front也只需要后移一个就好了，也差不多。

从这些来看，顺序表比链表实现简单，所以我们在这使用顺序表来实现循环队列。

思路

在判断队列是否为空的时候，只需要判断front==rear是否成立就好了。

但我们发现，判断队列满的条件和判空条件一模一样：

所以我们选择多开一个空间，开k+1个长度的数组：
此时队列为满，rear=4，当（rear+1）%（k+1）==0时，队列就为满。
然后我们出队一个数据，再入队一个5：

此时队列里面的数据是：2 3 4 5，然后rear越界了，此时rear=5，我们只需要让rear%（k+1），就可以确保每次入队后rear没有越界了。

然后rear为0，（rear+1）%（k+1）front，也能判断出队列满了，说明我们这个判断队列是否满的条件没有问题。
我们此时再出队2 3 4 5，然后front就会一直后移，变成这样子：

我们发现front也会出现越界的情况，所以每次出队后都执行front%（k+1），防止front越界。

然后发现rearfront，又说明我们的队列判空条件也没有问题。
因为在函数中我们要用到大小k，所以多定义一个capacity用来表示容量。
综合以上分析，我们把思路理清楚了，可以来实现一下代码了。

使用顺序表实现循环队列

定义结构体

首先是定义结构体，我们需要一个指针接收数组首地址，队头front，队尾rear，容量capacity。

初始化

然后就是初始化这个队列的函数MyCircularQueue* myCircularQueueCreate(int k)
我们创建一个结构体类型的指针，然后申请结构体大小的空间，再用arr接收申请的k+1个大小的空间，让front=0，rear=0，capacity=k就好了。

判断队列是否为空和为满

我们先写判断队列是否为空的函数myCircularQueueIsEmpty(MyCircularQueue* obj)和是否为满的函数myCircularQueueIsFull(MyCircularQueue* obj)。
只需要判断表达式rear==front（是否为空）和表达式（rear+1）%（k+1）==front（是否为满）的结果就好了。

入队

然后就是入队操作，当队为满时则入队失败，返回false，反之插入元素，rear后移一位，然后rear和（k+1）取模（保证rear不越界）。

出队

然后是出队函数myCircularQueueDeQueue(MyCircularQueue* obj)，出队需要判断队列是否为空，为空则返回false，不为空则执行出队操作，front++，然后front%（k+1）防止越界问题。

返回队头

接下来是队头函数myCircularQueueFront(MyCircularQueue* obj)，如果队列是空返回-1，反之直接返回队头就好了。

返回队尾

然后是队尾函数myCircularQueueRear(MyCircularQueue* obj)，如果队列为空，返回-1，不为空则返回rear前一个位置的元素，所以我们定义一个prev来代表队尾位置的元素。

但有一种特殊情况，当rear=0时，prev就等于-1了，所以当rear=0时，我们的prev应该等于k，这才是队尾元素。

代码如下：