1. Toy模板网首页
  2. > Toy博客

Leetcode循环队列（数组实现及链表实现）

10月前 作者：Dark Fire 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了Leetcode循环队列（数组实现及链表实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这道题十分考验我们对队列的理解。

队列的介绍

 队列是一种只允许在一段进行插入，在另一端进行删除的数据操作的特殊线性结构，，因此决定了他具有先入先出的特点，其中进行插入操作的一段叫做队尾，出队列的一端叫做队头。

Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记

队列的实现

 队列可以使用链表或者数组进行实现，对于这两种实现方法，使用链表实现效果更好一点，两个指针中front为链表的头，即队列的队头，出数据的话只需要找到front的下一个假设为pre，将front销毁，front置为pre即可，如果是用数组的结构的话，出队列在数组头上出数据，效率会很低。
链表实现队列代码如下
Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;


typedef struct Queue
{
	QNode* head;//头
	QNode* tail;//尾
	int size;//大小
}Que;
void QueueInit(Que* pq);//初始化
void QueuePush(Que* pq,QDataType);//入队列
void QueueDestroy(Que* pq);//销毁
void QueuePop(Que* pq);//出队列
QDataType QueueFront(Que* pq);//队头的数据
QDataType QueueBack(Que* pq);//队尾的数据

bool QueueEmpty(Que* pq);//检查是否为空
int QueueSize(Que* pq);//队列元素

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queueh.h"

void QueueInit(Que* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;

}

void QueuePush(Que* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;

	if (pq->tail == NULL)//这里要先进行判断
	{
		pq->head = pq->tail = newnode;//如果队列里没有一个元素
		//那么head和tail都为空，将newnode设置为队头，当然也是队尾，毕竟只有一个元素。
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判空，避免引起不必要的错误。
	if (pq->head->next != NULL)
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	else
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	pq->size--;
}

QDataType QueueFront(Que* pq)
{
	assert(pq);
	//判断是否为空
	assert(!QueueEmpty(pq));
	return pq->head->data;//队头位置
}

QDataType QueueBack(Que* pq)
{
	assert(pq);
	//判断是否为空
	assert(!QueueEmpty(pq));
	return pq->tail->data;//队尾位置
}

bool QueueEmpty(Que* pq)//判断是否为空，为空则返回true
{
	if (pq->head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

进入正题

链接：设计循环队列
Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记

 前边的队列如果空间不够就会扩容，但是这里的循环队列大小是固定的，只可以保存k个元素，当然还是遵循先入先出的规则。

 例如下边的环形队列，在pop掉队头数据后，这块空间不会被销毁的，可以继续存储值覆盖原来的值，假设k等于5，当入6个元素后，这个循环队列就满了，当出队列时，此时这个队列的首位置就可以继续存储数据。
Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记

数组的方法

结构体声明如下

typedef struct {
    int* a;
    int front;
    int rear;//尾
    int k;
} MyCircularQueue;

初始化函数如下

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个方便区分空和满
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->k=k;
    obj->front=obj->rear=0;
    return obj;
}

Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记
数组也面临一个同样的问题，如何判断是满还是空？
可以多开一块空间。k==5，开6块空间，最后一块空间浪费不用。
Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记
如果front等于tail就为空，在这里设置tail的值为0~5（要注意下标和位置有减一的关系），如果tail的下一个位置为front时，表示队列已满。

obj->tail%=(obj->k+1);//obj为循环队列变量

控制tail的值的变化范围，当tail等于6时置tail为0。
当然，在出队列过程中，front是会不断变化的。
我们看front变化的情况
pop一个数据后，向后移一位
Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记

判断是否队列已满的条件判断句如下

(obj->tail+1)%(obj->k+1 )==obj->front

前边已经说过了，tail的变化范围为0~5，此时tail被置为0，但front为1，不相等，就表示还有空余的位置，队列没有满，所以上边的判断语句在任何场景都是正常使用的。

判断是否已满函数如下（题目中tail被rear替换）

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

返回类型为布尔值，如果相等就返回true，不相等就返回false。
判断是否为空很简单，直接比较rear和front的值是否相等即可。

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

置空函数

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

获取队头元素
很简单，返回front位置的元素即可

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

获取队尾元素
这里就要思考一下了
如果rear不在数组第一个空间上，直接返回数组rear-1处的值即可，当rear位于数组首元素，就要返回数组第k个元素。
代码如下

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        if(obj->rear==0)
        {
            return obj->a[obj->k];
        }
        else{
            return obj->a[obj->rear-1];
        }
		//下边是综合写法
        //return obj->a[(obj->rear+obj->k)%(obj->k+1)];
    }
}

出队列deQueue()
出队列只需要将front++即可，就算之前的数据不销毁，下次入队列操作也会覆盖他的数据。
代码如下

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

注意是要有返回值的，如果队列为空，就没有出数据，返回false，出数据成功就返回true。
入队列
代码如下：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->a[obj->rear]=value;
    obj->rear++;

    obj->rear%=(obj->k+1);

    return true;
}

 首先判断循环队列是否已满，如果已满就返回false，如果没有满就将rear位置的值改为value，然后rear++，判断是否超出范围，如果超出就置为0。最后入队列成功返回true。
 到了这里这道题目就顺利解决了，如果使用双向链表来做这道题的话当然也可以，但是会稍微麻烦一点，有兴趣可以尝试尝试。
今天的内容就到这里啦，如果有错误欢迎各位指正哦！
综合上述代码后即可通过本题。
Leetcode循环队列（数组实现及链表实现）,数据结构,leetcode,算法,c语言,笔记

链表实现

链表实现就较为简单了，思路和前边数组实现的思路很像。
首先声明结构体

typedef struct listNode
{
    struct listNode* next;
    int val;
}LS;

typedef struct {
    LS* head;
    LS* tail;
    int size;
    int k;
} MyCircularQueue;

节点的结构体保存下一个结构体的指针，并且存储值val。
循环链表结构体有头结点，尾节点，size是队列中元素的个数，k为设定的循环队列的容量。
入队列时，获取一个初始化后新节点，并把之前的尾结点与这个节点连接起来。
获取新节点的函数如下

LS* buylistNode(int x)
{
    LS*listnode =(LS*)malloc(sizeof(LS));
    listnode ->next=NULL;
    listnode ->val=x;
    return listnode;
}

函数返回新造的节点。以供入队列函数使用。

至于判空判满函数我想就不用过多介绍，重要的是入队列和出队列。
出队列只需要头结点向后移，然后size–就好。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(obj->head==NULL)
    {
        return false;
    }
    else
    {
        obj->head=obj->head->next;
        obj->size--;
        return true;
    }
}

入队列

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//如果已满，就返回false
    {
        return false;
    }
    LS*node=buylistNode(value);
    if(obj->head==NULL)//第一次插入
    {
        obj->head=node;
        obj->tail=node;
    }
    else
    {
        LS*tran=obj->tail;
        obj->tail=node;
        tran->next=obj->tail;
    }
    obj->size++;//注意size++
    return true;
}

全部代码如下

typedef struct listNode
{
    struct listNode* next;
    int val;
}LS;

typedef struct {
    LS* head;
    LS* tail;
    int size;
    int k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size==0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->k;
}
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->head=NULL;
    obj->tail=NULL;
    obj->size=0;
    obj->k=k;
    return obj;
}

LS* buylistNode(int x)
{
    LS*listnode =(LS*)malloc(sizeof(LS));
    listnode ->next=NULL;
    listnode ->val=x;
    return listnode;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    LS*node=buylistNode(value);
    if(obj->head==NULL)
    {
        obj->head=node;
        obj->tail=node;
    }
    else
    {
        LS*tran=obj->tail;
        obj->tail=node;
        tran->next=obj->tail;
    }
    obj->size++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(obj->head==NULL)
    {
        return false;
    }
    else
    {
        obj->head=obj->head->next;
        obj->size--;
        return true;
    }
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->tail->val;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    while(obj->head!=NULL)
    {
        LS*a=obj->head->next;
        free(obj->head);
        obj->head=a;
    }
    free(obj);
}

这篇文章到这里就结束啦，如果有问题欢迎大家指出。文章来源地址https://www.toymoban.com/news/detail-744533.html

到了这里，关于Leetcode循环队列（数组实现及链表实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法——TypeScript】数组、栈、队列、链表

    【数据结构与算法——TypeScript】数组、栈、队列、链表

    解决问题 的过程中，不仅仅 数据的存储方式会影响效率，算法的优劣也会影响效率 什么是算法？ 定义： 🟢 一个有限指令集，每条指令的描述不依赖于言语 （编写指令：java/c++/ts/js） 🟢 接收一些输入（有些情况下不需要输入）（接收：排序：无序数组） 🟢 产生输出 （

    2024年02月14日
    浏览(38)
  • 【数据结构】如何设计循环队列？图文解析（LeetCode）

    【数据结构】如何设计循环队列？图文解析（LeetCode）

    LeetCode链接：622. 设计循环队列 - 力扣（LeetCode） 目录 做题思路 只开辟 k 个空间 多开一个空间 代码实现 1. 循环队列的结构 2. 开辟空间 3. 判断空 4. 判断满 5. 队尾插入数据 6. 队头删除数据 7. 获取队头元素 8. 获取队尾元素 9. 销毁队列 全部代码 设计循环队列，使用数组或链表

    2024年02月10日
    浏览(44)

  • 数据结构之线性表的类型运用Linear Lists: 数组，栈，队列，链表

    定义 一个最简单，最基本的数据结构。一个线性表由多个相同类型的元素穿在一次，并且每一个元素都一个前驱（前一个元素）和后继（后一个元素）。 线性表的类型 常见的类型：数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(47)
  • Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出，先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(46)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、

    2024年01月20日
    浏览(45)

  • golang 基于数组、切片、链表实现队列

    数组 切片 链表 链表加锁实现线程安全 cas 实现 无锁队列

    2024年02月04日
    浏览(43)
  • 数据结构——循环队列的实现

    数据结构——循环队列的实现

    hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页：大耳朵土土垚的博客 💥 所属专栏：数据结构学习笔记 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信

    2024年03月24日
    浏览(42)

  • 王道408---用数组，链表以及双向链表实现栈、队列

    我在电脑上敲了一遍，又在纸上模拟了一遍 下面记录在电脑上敲的:    

    2024年02月14日
    浏览(32)

  • 王道408用数组，链表以及双向链表实现栈、队列

    我在电脑上敲了一遍，又在纸上模拟了一遍 下面记录在电脑上敲的:    

    2024年02月14日
    浏览(37)
  • 【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    1.1 概念 队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾（Tail/Rear） 出队列：进行删除操作的一端称为 队头（Head/Front） 队列和栈的区别： 队列是 先进先出（队

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包