leetcode 622. 设计循环链表

2023-12-15 04:44:23

这道题讲了两种方法,第一个代码是用数组实现的,第二个是用链表实现的,希望对你们有帮助

(最好在VS自己测试一遍,再放到 leetcode上哦)

下面的是主函数(作参考),静下心来慢慢测试


?622. 设计循环链表

题目

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

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

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

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

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文字 和 画图 分析

  1. 思考什么情况下,队列为空,队列为满

定义一个 指针head,用来存放头节点的地址,和一个指针tail,用来存放尾节点的地址(这个思路和队列的实现是一样的)

按照正常思路,大多数人会以为(队列长度为k):

当 head = tail 为空,而 tail 是第 k 个节点的时候为满,却忽略一点,这是个循环链表

以下这种情况就不成立:

通过图我们知道 head = tail 无法判断是空还是满

所以我们换一种思路:

存放 k 个元素,但是开辟(k + 1)个节点,故意留下一个节点不放元素

情况就是这样的:

我们发现:

当 head = tail 为空;

当 tail 的下一个节点 = head为满;

? ? 2.? 选用数组还是链表去做

这里两者思路我都讲(代码仅供参考,能通过,但是我个人觉得有些地方没有处理好,其实可以更完善,听思路即可)

  • 用数组(head 和 tail 就是元素下标)

a. 首先明确这本质是一个循环链表

b. 实现过程可能会遇到的问题:

问题1:

这里可以看到 tail 不可能一直加加

如果是正确的思路,此时的图应该是这样:

所以我们这里要对 tail 进行处理:

这里可以通用

tail = tail % (k + 1)(head也会出现这样的情况,同样要这么处理)

问题2:

判断为满时,我们可能会犯错误

这种情况我们非常容易知道:判断

tail + 1 == head

但是这种情况就不适用了:

所以我们要写一个通式:

(tail + 1 ) % (k + 1) == head

问题3:

找到尾元素

正常情况下的尾元素很好找

尾元素的下标就是 tail - 1

如果是这样,就不好判断了

这里我们可以用 if ,else语句做区分,

也可以写一个通式:

(tail - 1 + k + 1) % (k + 1)

即:(tail + k )%(k + 1)

  • 用链表(head 和 tail 就是头节点和 尾节点的地址)

a. 这里可以写一个循环链表

可以在初始化的时候先搭建好这个循环链表,后面再存放元素

b. 只有一个地方需要注意:

就是找尾元素(实际上,应该是tail的上一个节点)

这里选择可以记录上一个节点的地址

或者 循环找到上一个节点


代码

代码1:

typedef int SLType;
typedef struct StackList
{
    SLType* a;
    int top;
    int rear;
    int k;
}SL;//创建数组
void SLInit(SL* head, int k)
{
    assert(head);
    head->a = (SLType*)malloc((k + 1) * sizeof(SLType));
    head->top = 0;
    head->rear = 0;
    head->k = k;
}//初始化数组
void SLPush(SL* head, SLType x)
{
    assert(head);
    head->a[head->rear] = x;
    head->rear++;
}//存放元素
void SLPop(SL* head)
{
    assert(head);
    head->top++;
}//删除元素


//以上都是数组的实现

typedef struct
{
    SL q;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    SLInit(&obj->q, k);
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    SL* q1 = &obj->q;
    return  q1->rear == q1->top;
}//判断是否为空

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    SL* q1 = &obj->q;
    int a = q1->rear;
    a = (q1->rear + 1) % (q1->k + 1);
    return a  == q1->top;
}//判断是否为满

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        SLPush(&obj->q, value);
        SL* q1 = &obj->q;
         q1->rear = q1->rear % (q1->k + 1);
        return true;
    }

}//存放元素

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        SLPop(&obj->q);
        SL* q1 = &obj->q;
         q1->top = q1->top % (q1->k + 1);
        return true;
    }

}//删除元素

int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return (&obj->q)->a[(&obj->q)->top];
    }
}//返回头元素

int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        if ((&obj->q)->rear == 0)
         {
            return (&obj->q)->a[(&obj->q)->k];
         } 
        return(&obj->q)->a[(&obj->q)->rear - 1];
    }
}//返回尾元素


void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj);
}//销毁空间

?代码2:

typedef int QLType;
typedef struct QueueNode
{
    QLType val;
    struct QueueNode* next;
}QN;//创建节点
typedef struct StackList
{
    QN* head;
    QN* tail;

}QL;//创建队列
void  QNInit(QL* pphead, int k)
{
    pphead->head = pphead->tail = NULL;
    QN* prev = NULL;
    k = k + 1;
    while (k--)
    {
        QN* newnode = (QN*)malloc(sizeof(QN));
        if (pphead->head == NULL)
        {
           prev =  pphead->head = pphead->tail = newnode;
        }
        else
        {
            pphead->tail = newnode;
            pphead->head->next = pphead->tail;
            pphead->tail->next = prev;
            pphead->head = pphead->tail;
        }
    }
    pphead->head =pphead->tail = prev;
}//初始化并链接节点

QLType QLTop(QL* pphead)
{
    return pphead->head->val;
}//返回首元素
QLType QLtail(QL* pphead)
{
    QN* rear = pphead->head;
    while (rear->next != pphead->tail)
    {
        rear = rear->next;
    }
    return rear->val;
}//返回尾元素
void QLpush(QL* pphead, int val)
{
    pphead->tail->val = val;
    pphead->tail = pphead->tail->next;
}//存放元素
void QLPop(QL* pphead)
{
    pphead->head = pphead->head->next;
}//删除元素


//以上是链表的创建


typedef struct
{
    QL q;
} MyCircularQueue;

MyCircularQueue * myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    QNInit(&obj->q, k);
    return obj;
}//初始化
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    QL* q1 = &obj->q;
    return  q1->head == q1->tail;
}//判断是否为空

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    QL* q1 = &obj->q;
    return q1->tail->next == q1->head;
}//判断是否为满
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        QLpush(&obj->q, value);
        return true;
    }

}//存放元素

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        QLPop(&obj->q);
        return true;
    }
}//删除元素

int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return QLTop(&obj->q);
    }
}//返回首元素

int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return  QLtail(&obj->q);
    }
}//返回尾元素


void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj);
}//释放空间

文章来源:https://blog.csdn.net/2301_79789645/article/details/134863418
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。