LeetCode 设计循环队列(C语言)

简介: LeetCode 设计循环队列(C语言)

题目要求

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

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

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

MyCircularQueue(k): 构造器,设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空,返回 -1 。

Rear: 获取队尾元素。如果队列为空,返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

来源:力扣(LeetCode)

代码模板:

typedef struct {
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
int myCircularQueueFront(MyCircularQueue* obj) {
}
int myCircularQueueRear(MyCircularQueue* obj) {
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
}
void myCircularQueueFree(MyCircularQueue* obj) {
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 * bool param_2 = myCircularQueueDeQueue(obj);
 * int param_3 = myCircularQueueFront(obj);
 * int param_4 = myCircularQueueRear(obj);
 * bool param_5 = myCircularQueueIsEmpty(obj);
 * bool param_6 = myCircularQueueIsFull(obj);
 * myCircularQueueFree(obj);
*/

分析

tail为队尾,head为队头,如果想出队head就顺时针走,入队tail也是顺时针走,出队的时候不用管里面的数据是什么,因为我们只看head和tail(包括head和tail指向的地方)这段距离中的数据。

我们也不需要考虑扩容的问题。

这里有两种方法,一个是用链表,一个是用顺序表,这里我们用顺序表。

顺序表因为是数组的原因,所以不会有链表那种循环。

一开始head和tail是在同一个点,因为队里没有任何的数据,如果想入队,那么tail往后走一步,head不动:

出队列就是head走一步。

那么,这是个循环队列,head和tail走到末尾之后,再走一步就回到了最开始的地方。

最重要的就是判断队列是否为空,是否满队列,空队列就是head和tail指向了同一个位置,但是如果一直入队,等到满队,条件也是head和tail指向了同一个地方

这样我们就没办法判断倒是是满队还是空队,所以我们需要加一个新的空间,新开出来的空间是缓冲满队列的。

现在tail指向的位置就是多余出来的地方,这7个格子中任何一个地方可能都会是多余的那个,这样判断满队的条件就是tail的下一个是head了。

代码实现

队列的结构体

typedef struct {
    int* a;//数组的起始位置
    int head;//队头
    int tail;//队尾
    int N;//数组的长度
} MyCircularQueue;

初始化

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));//开辟数组的空间,多开辟一个int长度
    obj->head=obj->tail=0;//起始位置为下标0
    obj->N=k+1;
    return obj;
}

这里开辟的是结构体的空间,因为用malloc开辟不会因为函数的消失而销毁。

判断是否满队,是否空队

空队

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head==obj->tail;
}

满队

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%obj->N==obj->head;
}

满队的判断依据是tail的下一个是haed就为满,但是这里会有边界的问题

紫色的是下标,因为head和tail都是靠下标定位,所以让(tail+1)%7(这里的7是队列长度,只是在假设长度是7)就能让tail指向下标为0的地方,也就是head指向的位置,如果是7以下的数%7,就不会变动。

获取队尾队首元素

队空返回-1.

队首

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->head];
}

队尾

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[(obj->tail-1 + obj->N)%obj->N];
}

我们知道tail-1才是队尾元素的下标,但如果tail等于0,就等于-1了。

这里我们只要让tail加上一个队列长度,在%队列长度就好了。

插入,删除

插入,删除成功返回真,否咋返回假

插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->a[obj->tail]=value;
        obj->tail++;
        obj->tail%=obj->N;//这里也要注意tail不能超过队列长度。
    }
    return true;
}

删除

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->head++;
        obj->head%=obj->N;//这里也要注意head不能超过队列长度。
    }
    return true;
}

删除直接让head++即可,后面的不会被读取,就算有新的插入也是覆盖掉原来的元素。

销毁队列

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


目录
打赏
0
0
0
0
18
分享
相关文章
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(上)
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣
60 0
Leetcode—— 删除排序数组中的重复项——C语言
Leetcode—— 删除排序数组中的重复项——C语言
Leetcode----旋转数组 ------C语言篇
Leetcode----旋转数组 ------C语言篇
|
9月前
|
LeetCode---消失的数字---C语言实现
LeetCode---消失的数字---C语言实现
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
77 7
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
89 5
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
65 1
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
57 1
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(上)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
84 1
|
9月前
|
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
72 1