【LeetCode】环形队列实现-易微帮

前言

之前我们学习环形链表相关问题，现在我们来看看环形队列有什么不同呢

1. 环形队列概念

循环队列是一种线性数据结构，其操作依然是先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
最大的特点就是可以用利用这个队列之前用过的空间。
在这里插入图片描述

2. 循环队列实现设计

循环链表可以使用数组或链表实现
我这里用数组实现
如果需要存放是k个数据，我们就需要开辟k+1个数据空间，不然就无法判定空和满，导致数据插入和删除异常
需要两个变量来标识头（head）和尾（tail），出队front就向前移动，入队rear向前移动，但是这样会造成一个问题数组越界，循环就很好解决了这个问题，越界了就回到第一个数据位置。

判空：head == tail
盘满：head+1 == tail

3. 功能实现

3.1 定义

我们使用数组实现，需要一个数组，还有2个标志头(head)和尾(tail)的变量，和一个标志存放多少数据的变量k

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;

3.2 初始化

首先我们需要创建队列结构体，在给里面成员赋值，之前说了我们需要k+1数据的空间，防止不知道满了和空的情况，head和tail刚开始都是0，k还是实参传过来的，我们需要的是k+1数据的空间
在这里插入图片描述

MyCircularQueue* myCircularQueueCreate(int k) {
    // 创建队列结构体
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
    // 为队列里的数组创建k+1空间
    cq->a = (int*)malloc((k+1) * sizeof(int));
    cq->head = cq->tail = 0;
    cq->k = k;
    
    return cq;
}

3.3 判断队列是否为空

head和tail相等，就是空，不是就有数据

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    // head和tail相等就是空
    return obj->head == obj->tail;
}

3.4 判断队列是否为满

因为多开了一个数据空间，所以可以判断队列是否为满，tail+1 == head，就满了，多开一个数据的空间，可以保证满了的时候，tail和head无论什么情况，都至少有一个空间的距离，但是tail可能会越界，我需要取余
a只要取余b， a % b，余数一定是 0——b - 1，所以tail取余就不会越界，正好也满足了越界回到第一个数据位置。
而且还需要注意优先级问题，tail和k都是先加1，在进行取余
(obj->tail+1) % (obj->k+1) == obj->head

在这里插入图片描述

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // tail+1取余k+1，等于head，就是满
    return (obj->tail+1) % (obj->k+1) == obj->head; 
}

3.5 入栈

满了的就不能入数据了
插入数据tail就会增加，可能会越界，同样需要取余

在这里插入图片描述

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    // 队列满了，就不能插入数据
    if (myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->tail] = value;
    obj->tail++;
    
    // 插入数据会导致tail下标越界，越界处理：越界了就回到开始位置
    obj->tail %= obj->k+1;
    return true;
}

3.6 出栈

队列为空不能出数据
出栈，head就会向前移动，同样也会有越界问题，也需要取余

ool myCircularQueueDeQueue(MyCircularQueue* obj) {
    // 队列为空，不能删除数据
    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->head++;
    // 删除数据会导致head下标越界，越界处理：越界了就回到开始位置
    obj->head %= obj->k+1;
    return true;
}

3.7 获取队头数据

队列为空不能取数据，返回数据的head位置的数据即可

int myCircularQueueFront(MyCircularQueue* obj) {
     // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 返回头下标的数据
    return obj->a[obj->head];
}

3.8 获取队尾数据

队列为空不能取数据，由于是先插入数据，后++，我们要取tail数据，需要-1，这个有两个情况，需要特殊处理

tail不为0，直接取数组tail - 1位置即可
tail为0，我们减1，tail为-1就会越界，返回最后一个数据的下标就是k的位置，这里有两种解决方法1、if判断 2、取余

if判断

int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // tail等于0会越界，取消返回最后一个数据的下标
    if (obj->tail == 0)
        return obj->a[obj->k];

    return obj->a[obj->tail - 1];
}

取余
由于空间长短是k+1，下标是k，他们之间最少也会差1，所以当前位置tail+k，在取余k+1，刚好就返回了tail的位置的前一个数据位置
tail+k = k+1
tail - 1


int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 由于空间长短是k+1，下标是k，他们之间最少也会差1
    // 所以当前位置tail+k，在取余k+1，刚好就返回了tail前一个数据位置
    // tail+k = k+1
    // tail - 1
    int tail = (obj->tail+obj->k) % (obj->k+1);
    return obj->a[tail];
}

3.9 销毁

同样也有两层结构，我们需要前销毁里层，在销毁外层
在这里插入图片描述

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

4. 总结

循环队列用数组实现就需要多注意数组越界问题

5. 完整通过代码

typedef struct {
    int* a;
    int head;	// 头
    int tail;	// 尾
    int k;		// 队列长度
} MyCircularQueue;

// 由于要先调用这两个函数，所以先声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    // 创建队列结构体
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
    // 为队列里的数组创建k+1空间
    cq->a = (int*)malloc((k+1) * sizeof(int));
    cq->head = cq->tail = 0;
    cq->k = k;
    
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    // 队列满了，就不能插入数据
    if (myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->tail] = value;
    obj->tail++;
    
    // 插入数据会导致tail下标越界，越界处理：越界了就回到开始位置
    obj->tail %= obj->k+1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    // 队列为空，不能删除数据
    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->head++;
    // 删除数据会导致head下标越界，越界处理：越界了就回到开始位置
    obj->head %= obj->k+1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
     // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 返回头下标的数据
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 由于空间长短是k+1，下标是k，他们之间最少也会差1
    // 所以当前位置tail+k，在取余k+1，真好就返回了前一个数据位置
    // tail+k = k+1
    // tail - 1

    // 取余法
    //int tail = (obj->tail+obj->k) % (obj->k+1);
    //return obj->a[tail];

     if (obj->tail == 0)
        return obj->a[obj->k];

    return obj->a[obj->tail - 1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    // head和tail相等就是空
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // tail+1取余k+1，等于head，就是满
    return (obj->tail+1) % (obj->k+1) == obj->head; 
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->head = obj->tail = obj->k = 0;
    free(obj);
}

【LeetCode】环形队列实现

目录

前言