【数据结构】循环队列

🎏队列顺序存储的不足

我们假设用一个可以存放为n个数据的数组arr来实现队列:

很容易可以知道:给arr中入队时时间复杂度为O(1),而出队时时间复杂度却是O(n).

按照传统方式每次出队时都要将所有元素向前挪动是非常麻烦的,我们不如在出队时让头指针也动起来,即在出队时不移动后面的元素,而是让front向后移动,指向新的队头元素:

这样出队和入队的时间复杂度都是O(1)了,但是使用这种方式,当我们入队又出队后会造成"假溢出"问题:

即数组前面有空着的空间,但因为队列入队要追加在队伍的末尾,因此只能追加在下图中9的后面,但9后面没有空间了,这时就会造成"假溢出"问题.

你想想,如果你今天去教室上课,因为是水课,后面3排都坐满了人,而前排还有很多空位,你会怎么做?直接走出教室,并告诉自己后面没有座位可坐了?

现实生活中我们不会那样做的,前面有座位,我们当然是可以坐的,除非真的满了,那才需要考虑向老师申请一个大教室.

🎏循环队列的定义

因此,解决假溢出的办法就是后面满了,就从头再开始,也即头尾相接的循环.

我们把队列的这种头尾相接的顺序存储结构称为循环队列.

在刚才的例子中,我们可以改变rear指向下标为0的位置,这样就可以继续入队元素了:

当我们继续一直入队元素,rear一直向后移动,直到将数组入满,此时rear和front重合,同时指向下标为5的位置,如图:

此时我们需要思考几个问题,我们刚才说,空队列时,front等于rear,而现在队列满时,也是front等于rear,那么该如何判断此时的队列究竟是空还是满?

• 办法一是设置一个标志flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满.
• 办法二是当队列空时,条件是front=rear,当队列满时,我们修改其条件,保留一个元素空间.也就是说,当数组中只剩一个空闲单元时,我们就认为队列满了,如下图所示:

由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈.

所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front

(这里的取模"%"的目的就是为了解决rear可能会比front大一圈的问题).

队列的长度计算也要特别注意,通用的计算队列长度公式为:

(rear-front+QueueSize)%QueueSize

有了以上关于循环队列的知识储备,我们接下来实战实现一个循环队列.

🎏设计循环队列

题目链接

https://leetcode.cn/problems/design-circular-queue/

题目描述

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

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

你的实现应该支持如下操作：

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

题目详情

解题思路

循环队列的设计思路其实在文章前面的简介部分我们已经阐述过了,但在具体实现时,我们仍需注意以下几点:

• 注意题目要求的返回值,如入队/出队函数要求成功返回true,失败返回false.
• 注意队列判满的条件
• 注意rear,front在持续向后移动过程中,如果数值超过了合理的数组下标范围,,则需要想办法将其修正到合理的范围内.

解题代码

综上,解题代码如下:

typedef struct 
{
    int *arr;   //存数据
    int front;  //头指针
    int rear;   //尾指针
    int k;      //存个数
} MyCircularQueue;
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//判空,为空返回true
{
    return (obj->front==obj->rear);
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj)//判满,为满返回true
{
    return ((obj->front)==((obj->rear+1)%(obj->k+1)));
}
 
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if(obj==NULL)
    {
        perror("malloc fail::");
        return NULL;
    }
    obj->arr=(int*)malloc(sizeof(int)*(k+1));//留空一个,便于判断
    if(obj->arr==NULL)
    {
        perror("malloc fail::");
        return NULL;
    }
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队
{
    //队满返回false
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //队未满尾插
    else
    {
        obj->arr[obj->rear]=value;
        obj->rear++;
        obj->rear%=(obj->k+1);
        return true;
    }
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队
{
    //队空返回false
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else//队非空则头删
    {
        obj->front++;
        obj->front%=(obj->k+1);
        return true;
    }
}
 
int myCircularQueueFront(MyCircularQueue* obj)//取队头
{
    if(myCircularQueueIsEmpty(obj))//为空则失败
    {
        return -1;
    }
    return obj->arr[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj)//取队尾
{
    if(myCircularQueueIsEmpty(obj))//为空则失败
    {
        return -1;
    }
    return obj->arr[(obj->rear+obj->k)%(obj->k+1)];//如果rear=0,rear-1=-1会导致越界访问
}
 
void myCircularQueueFree(MyCircularQueue* obj)//销毁,开几个销几个
{
    free(obj->arr);
    free(obj);
}

提交运行:

结语

希望这篇有关数据结构循环队列的文章能对您有所帮助,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

数据结构栈与队列篇思维导图: