备案控制台
开发者社区 云计算 文章 正文

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

2023-11-20 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Leetcode循环队列（数组实现及链表实现）

队列的介绍

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

队列的实现

 队列可以使用链表或者数组进行实现，对于这两种实现方法，使用链表实现效果更好一点，两个指针中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;
}

进入正题

链接：设计循环队列

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

 例如下边的环形队列，在pop掉队头数据后，这块空间不会被销毁的，可以继续存储值覆盖原来的值，假设k等于5，当入6个元素后，这个循环队列就满了，当出队列时，此时这个队列的首位置就可以继续存储数据。

数组的方法

结构体声明如下

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;
}

数组也面临一个同样的问题，如何判断是满还是空？

可以多开一块空间。k==5，开6块空间，最后一块空间浪费不用。

如果front等于tail就为空，在这里设置tail的值为0~5（要注意下标和位置有减一的关系），如果tail的下一个位置为front时，表示队列已满。

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

控制tail的值的变化范围，当tail等于6时置tail为0。

当然，在出队列过程中，front是会不断变化的。

我们看front变化的情况

pop一个数据后，向后移一位

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

(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。

 到了这里这道题目就顺利解决了，如果使用双向链表来做这道题的话当然也可以，但是会稍微麻烦一点，有兴趣可以尝试尝试。

今天的内容就到这里啦，如果有错误欢迎各位指正哦！

综合上述代码后即可通过本题。

链表实现

链表实现就较为简单了，思路和前边数组实现的思路很像。

首先声明结构体

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);
}

这篇文章到这里就结束啦，如果有问题欢迎大家指出。

文章标签：
存储
关键词：
链表数组
数组链表
LeetCode链表
LeetCode数组
链表leetcode
DarkFire
目录
相关文章
小李很执着
|
19小时前
|
存储 C语言
Leetcode—— 删除排序数组中的重复项——C语言
Leetcode—— 删除排序数组中的重复项——C语言
小李很执着
4 0
稻草人敲代码
|
1天前
力扣2834. 找出美丽数组的最小和
力扣2834. 找出美丽数组的最小和
稻草人敲代码
3 0
稻草人敲代码
|
1天前
|
C语言 C++ 索引
力扣 138. 随机链表的复制
力扣 138. 随机链表的复制
稻草人敲代码
4 0
稻草人敲代码
|
1天前
力扣421. 数组中两个数的最大异或值（字典树）
力扣421. 数组中两个数的最大异或值（字典树）
稻草人敲代码
4 0
老板这功能得加钱
|
5天前
|
存储 Android开发 算法
Android技能树 — 数组,链表,散列表基础小结，android教程零基础入门
Android技能树 — 数组,链表,散列表基础小结，android教程零基础入门
老板这功能得加钱
7 0
程序员行者孙
|
7天前
LeetCode链表hard 有思路？但写不出来？
LeetCode链表hard 有思路？但写不出来？
程序员行者孙
7 0
toKeep
|
8天前
|
索引
每日一题：力扣328. 奇偶链表
每日一题：力扣328. 奇偶链表
toKeep
15 4
Bigcrab__
|
8天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
Bigcrab__
13 0
天玑y
|
8天前
|
算法
leetcode代码记录（寻找两个正序数组的中位数
leetcode代码记录（寻找两个正序数组的中位数
天玑y
15 2
天玑y
|
8天前
|
索引
leetcode代码记录（最长重复子数组
leetcode代码记录（最长重复子数组
天玑y
15 0

热门文章

最新文章

  • 1
    代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
  • 2
    标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
  • 3
    [leetcode～数位动态规划] 2719. 统计整数数目 hard
  • 4
    刷题之Leetcode206题(超级详细)
  • 5
    代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
  • 6
    [leetcode~dfs]1261. 在受污染的二叉树中查找元素
  • 7
    代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
  • 8
    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
  • 9
    [leetcode] 快乐数 E
  • 10
    【leetcode】剑指 Offer II 105. 岛屿的最大面积-【深度优先DFS】
  • 1
    【数据结构算法（二）】链表总结
    18
  • 2
    《剑指offer》——合并两个排序的链表
    21
  • 3
    《剑指offer》——从尾到头打印链表
    21
  • 4
    【移除链表元素】LeetCode第203题讲解
    21
  • 5
    【顺序表和链表的对比】
    18
  • 6
    【双向链表】数据结构双向链表的实现
    22
  • 7
    【单链表】数据结构单链表的实现
    38
  • 8
    实现单链表的基本操作（力扣、牛客刷题的基础&笔试题常客）
    146
  • 9
    快慢指针该如何操作？本文带你认识快慢指针常见的三种用法及在链表中的实战
    29
  • 10
    leetcode82. 删除排序链表中的重复元素 II
    25

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考