leetcode622-设计循环队列

简介: leetcode622-设计循环队列

本题重点:

1. 选择合适的数据结构

2. 针对选择的数据结构判断“空”和“满”

这两点是不分先后次序的,在思考时应该被综合起来。事实上,无论我们选择链表还是数组,最终都能实现题中描述的“循环队列”的功能,只不过选择不同结构时,我们面临和需要解决的问题不同。

一、思路

1. 数组实现队列。定义变量 front 标识队头,变量 rear 标识队尾。

数组设计循环队列的好处:

1. 找队尾元素方便;使用链表实现时,需要找尾。

2. 循环实现方便,通过控制下标即可完成循环。

2. 初始时,front = rear = 0,每次插入一个元素,rear向后走一位。

3. 判断“空” 和 “满”。如果 front 和 rear 下标相同,队列为空,还是满?

4. 理解(rear + 1)% (k + 1)== front

若队列已满,则rear 的下一个位置为 front。

此外,每一次插入数据 或者 删除数据 后,都要进行取模操作

防止 front 和 rear 走出实际数组的范围,造成数组越界。

二、功能模块实现

1. MyCircularQueue(k): 设置队列长度为 k

typedef struct {
    int* a; // 指向的空间用来存储元素
    int front;
    int rear;
    int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front = obj->rear = 0;
    obj->k = k;
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    // 多创建1个空位,
    // 该位置不用来存储元素,仅用于判断队列“空”和“满”
    return obj;
}

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

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->rear == obj->front)
        return true;
    else
        return false;
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear + 1) % (obj->k + 1) == obj->front)
        return true;
    else
        return false;
}

4. enQueue(value): 向循环队列插入一个元素。

如果成功插入则返回真。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    else
    {
        obj->a[obj->rear] = value;
        obj->rear++;
        obj->rear %= obj->k + 1;
        return true;
    }
}

5. deQueue(): 从循环队列中删除一个元素。

如果成功删除则返回真。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    else
    {
        obj->front++;
        obj->front %= obj->k + 1;
        return true;
    }
}

6. Front: 从队首获取元素。

如果队列为空,返回 -1 。

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

7. Rear: 获取队尾元素。

如果队列为空,返回 -1 。

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

8. QueueFree: 销毁循环队列

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

 

三、所有代码

typedef struct {
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front = obj->rear = 0;
    obj->k = k;
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->rear == obj->front)
        return true;
    else
        return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear + 1) % (obj->k + 1) == obj->front)
        return true;
    else
        return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    else
    {
        obj->a[obj->rear] = value;
        obj->rear++;
        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;
    }
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}   
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear + (obj->k + 1) - 1) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}
相关文章
|
6月前
|
存储
622.设计循环队列(LeetCode)
622.设计循环队列(LeetCode)
622.设计循环队列(LeetCode)
|
6月前
|
存储
手把手设计C语言版循环队列(力扣622:设计循环队列)
手把手设计C语言版循环队列(力扣622:设计循环队列)
55 0
|
6月前
|
存储
「LeetCode」622. 设计循环队列
「LeetCode」622. 设计循环队列
48 0
LeetCode | 622. 设计循环队列
LeetCode | 622. 设计循环队列
|
存储
Leetcode622.设计循环队列
Leetcode622.设计循环队列
28 0
|
6月前
|
存储
LeetCode——622设计循环队列
LeetCode——622设计循环队列
|
索引
LeetCode:设计循环队列
LeetCode:设计循环队列
45 0
|
6月前
|
存储
leetcode-622:设计循环队列
leetcode-622:设计循环队列
37 1
|
6月前
|
机器学习/深度学习 存储
leetcode:循环队列
leetcode:循环队列
|
11月前
|
存储 算法 索引
【LeetCode刷题日志】622.设计循环队列
【LeetCode刷题日志】622.设计循环队列