如何设计循环队列（两种方法）

  • 开发
  • 32

文章目录

前言

前面有提到过队列的知识，这次来说一下怎么设计一个循环队列

一.循环队列（力扣）

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/description/

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

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

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

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

思路:循环队列无论使用数组实现还是链表实现，都要多开一个空间，也就意味着要是存K个数据的循环队列，就要开K+1个空间，不然无法实现判空和判满

方法一:数组法

注意数组法的判空和判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

1.0初始化

初始化一个数组，有头front，尾tail，数组明a

typedef struct {
	int* a;
	int front;
	int tail;
	int k;

} MyCircularQueue;

1.1创建

MyCircularQueue* myCircularQueueCreate(int k) 
{
	//开辟一个循环队列的空间
	MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//开辟一个数组的空间用来实现循环队列，要多开辟一个
	q->a = (int*)malloc(sizeof(int) * (k + 1));
	//初始化
	q->front = q->tail = 0;
	q->k = k;
	return q;
}

1.2判空，判满

判空:就是front==tail的时候就是空的，判满:当（tail+1)%(k+1)==front就是满的

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->k + 1) == obj->front;
}

1.3插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	//如果循环队列是满的就不能插入
	if (myCircularQueueIsFull(obj))
		return false;
	//把末尾的值插入值
	obj->a[obj->tail] = value;
	//然后tail的往后走
	++obj->tail;
	//防止数组越界，%(k+1)把下标都控制在k之内
    //把越界的重置
	obj->tail %= (obj->k + 1);
	return true;
}

1.4删除

数组的删除不用向链表这些Pop，直接覆盖就可以了

//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	//如果是空的就不能删
	if (myCircularQueueIsEmpty(obj))
		return false;
	//头往前走
	++obj->front;
	//止数组越界，%(k+1)把下标都控制在k之内
	obj->front %= (obj->k + 1);
	return true;
}

1.5拿出最后一个数

int myCircularQueueRear(MyCircularQueue* obj) {
	//如果是空的就拿不了
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数
	if (obj->tail == 0)
		return obj->a[obj->k];
	else
		return obj->a[obj->tail - 1];
}

1.6拿出头数据和销毁

//直接拿出
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}

	return obj->a[obj->front];

}

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

1.7总代码

注意把判空判满提前引用！！！

typedef struct {
	int* a;
	int front;
	int tail;
	int k;

} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) 
{
	//开辟一个循环队列的空间
	MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	//开辟一个数组的空间用来实现循环队列，要多开辟一个
	q->a = (int*)malloc(sizeof(int) * (k + 1));
	//初始化
	q->front = q->tail = 0;
	q->k = k;
	return q;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	//如果循环队列是满的就不能插入
	if (myCircularQueueIsFull(obj))
		return false;
	//把末尾的值插入值
	obj->a[obj->tail] = value;
	//然后tail的往后走
	++obj->tail;
	//防止数组越界，%(k+1)把下标都控制在k之内
	obj->tail %= (obj->k + 1);
	return true;
}

//数组的删除不用向链表这些Pop，直接覆盖就可以了
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	//如果是空的就不能删
	if (myCircularQueueIsEmpty(obj))
		return false;
	//头往前走
	++obj->front;
	//止数组越界，%(k+1)把下标都控制在k之内
	obj->front %= (obj->k + 1);
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}

	return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {
	//如果是空的就拿不了
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	//存在特殊情况，当tail为0时，尾才最后，所以不能直接拿出tail之前的数
	if (obj->tail == 0)
		return obj->a[obj->k];
	else
		return obj->a[obj->tail - 1];
}

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

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

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

方法二.链表法

2.0初始化

先初始化一个链表，在定义结构

typedef struct listNode {
    int data;
    struct Node* next;
}Node;

typedef struct {
    Node* front;
    Node* tail;
    int k;
}MyCircularQueue;

2.1创建

这个是最难的部分，就是在创建的时候要创造一个循环链表，注意:这里其实已经开辟了k+1个空间了,不懂的自己画图

MyCircularQueue* myCircularQueueCreate(int k) {

    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->tail = (Node*)malloc(sizeof(Node));
    cq->k = k;
    //创造一个循环链表
    //这里其实已经开辟了k+1个空间了注意
    while (k)
    {
        Node* cur= (Node*)malloc(sizeof(Node));
        cur->data = 0;
        cur->next = NULL;
        cq->tail->next =cur;
        cq->tail= cq->tail->next;
        k--;
    }
    //开辟好了之后还要把尾和头发一起
    cq->tail->next =cq->front;
    cq->tail= cq->front;

    return cq;
}

2.2判空，判满

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->front;
}

2.3插入

//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判满
    if (myCircularQueueIsFull(obj))
        return false;
    //直接在尾上插入
    obj->tail->data = value;
    obj->tail= obj->tail->next;
    return true;
}

2.4删除

//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判空
    if (myCircularQueueIsEmpty(obj))
        return false;
    //头删
    obj->front = obj->front->next;
    return true;
}

2.5去头元素

int myCircularQueueFront(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}

2.6去尾元素

注意尾是前一个元素，所以不可以直接拿出，实在不理解看一下直接的动图

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //去找尾
    Node* cur= obj->front;
    while (cur->next != obj->tail)
        cur= cur->next;

    return cur->data;

}

2.7销毁

这个是我自己犯的错误

cur=cur->next,为什么不可以，因为cur等于头节点，cur等于cur->next，再释放cur，相当于把头节点next释放掉了，那我头节点后面的后面怎么去找呢？所以我们是从头节点开始释放的，把头节点用cur记录下来，释放之前让头节点走了，但是cur是头节点的傀儡节点，所以释放cur相当于是释放头节点了。

void myCircularQueueFree(MyCircularQueue* obj) {
   //和单链表的销毁一样
    Node* tmp = obj->front;
    while (obj->k + 1)
    {
        //cur=cur->next；为什么不可以
        obj->front = obj->front->next;
        free(tmp);
        tmp = obj->front;
        obj->k--;
    }
    free(obj);
}

2.8总代码

注意把判空判满提前引用！！！

typedef struct listNode {
    int data;
    struct Node* next;
}Node;

typedef struct {
    Node* front;
    Node* tail;
    int k;
}MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {

    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->tail = (Node*)malloc(sizeof(Node));
    cq->k = k;
    //创造一个循环链表
    //这里其实已经开辟了k+1个空间了注意
    while (k)
    {
        Node* cur= (Node*)malloc(sizeof(Node));
        cur->data = 0;
        cur->next = NULL;
        cq->tail->next =cur;
        cq->tail= cq->tail->next;
        k--;
    }
    //开辟好了之后还要把尾和头发一起
    cq->tail->next =cq->front;
    cq->tail= cq->front;

    return cq;
}
//插入
//他这个题目其实是提前开辟好了，让你直接插入就可以了
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判满
    if (myCircularQueueIsFull(obj))
        return false;
    //直接在尾上插入
    obj->tail->data = value;
    obj->tail= obj->tail->next;
    return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判空
    if (myCircularQueueIsEmpty(obj))
        return false;
    //头删
    obj->front = obj->front->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //去找尾
    Node* cur= obj->front;
    while (cur->next != obj->tail)
        cur= cur->next;

    return cur->data;

}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
   //和单链表的销毁一样
    Node* tmp = obj->front;
    while (obj->k + 1)
    {
        obj->front = obj->front->next;

        free(tmp);
        tmp = obj->front;

        obj->k--;
    }
    free(obj);
}

总结

用两种解法理解了循环队列，想必对链表和队列的知识做到了巩固

阅读全部

相关推荐

  4. 设计循环队列

    2024-03-25 08:44:03       69 阅读

  6. 设计循环队列

    2024-03-25 08:44:03       27 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-25 08:44:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-25 08:44:03       100 阅读

  9. 在Django里面运行非项目文件

    2024-03-25 08:44:03       82 阅读

  19. Python语言-面向对象

    2024-03-25 08:44:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-03-25 08:44:03       85 阅读

热门阅读

  4. FPGA时钟资源详解——Clock-Capable Inputs

    2024-03-25 08:44:03       39 阅读

  9. 一文解读ISO26262安全标准：软件及测试安全分析的相关解读

    2024-03-25 08:44:03       48 阅读

  17. 【DevOps云实践】Azure Function中使用发布/订阅模式

    2024-03-25 08:44:03       42 阅读

  19. spring boot常见的面试题

    2024-03-25 08:44:03       39 阅读

  22. 解决 Jupyter Notebook 中没有显示想要的内核的问题

    2024-03-25 08:44:03       36 阅读

  26. C语言题目:字符提取（自定义函数）

    2024-03-25 08:44:03       41 阅读

  28. ipv4、ipv6、tcp、udp包结构以及字段解释

    2024-03-25 08:44:03       45 阅读

  29. 快速入门Kotlin③类与对象

    2024-03-25 08:44:03       44 阅读