【数据结构】循环队列

修修修也

发布于 2024-04-01 16:04:00

21800

代码可运行

文章被收录于专栏：修也的进阶日记修也的进阶日记

运行总次数：0

代码可运行

🎏队列顺序存储的不足

我们假设用一个可以存放为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

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

🎏设计循环队列

题目链接

622. 设计循环队列

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);
}

提交运行: