【力扣--622】设计循环队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣--622】设计循环队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🖊作者 : D. Star.
📘专栏 : 数据结构
😆今日分享 : 丢脸其实并没有那么可怕，我们可以从另一个角度来想：别人能够记住我了，而且过了还有多少人能记得我呢？虽然这种出场不太优雅😆

【力扣--622】设计循环队列

🔎题目链接：

【力扣–622】设计循环队列

🔎题目：

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

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

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

🔎解题思路：

通过一个定长数组实现循环队列
入队：首先要判断队列是否已满，再进行入队的操作，入队操作需要考虑索引循环的问题，当索引越界，需要让它变成最小值
出队：首先要判断队列是否为空，再进行出队操作，出队也需要考虑索引循环的问题
判空：队头 == 队尾
判满：队尾 + 1 == 队头

🔎代码详情：

typedef struct {
    int* a;
    int front;
    int rear;
    int k;//数组大小
} MyCircularQueue;


//构造器，设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

//检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return ((obj->rear+1) % (obj->k+1) == obj->front);
}

// 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front == obj->rear;
}

//向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        //法一：
        // obj->a[obj->rear] = value;
        // obj->rear = (obj->rear+1)%(obj->k+1);

        //法二：
        obj->a[obj->rear++] = value;
        obj->rear %= (obj->k+1);

        return true;  
    }
}

//从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        //出数据
        obj->front++;
        obj->front %= (obj->k+1);
        return true;
    }
}

// 从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

// 获取队尾元素。如果队列为空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;  
    else
    {
        int ret = obj->rear == 0 ? obj->k : obj->rear - 1;
        return obj->a[ret];
    }
}

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