leetcode 622. 设计循环链表
这道题讲了两种方法，第一个代码是用数组实现的，第二个是用链表实现的，希望对你们有帮助
（最好在VS自己测试一遍，再放到 leetcode上哦）
下面的是主函数（作参考），静下心来慢慢测试
?622. 设计循环链表
题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
- MyCircularQueue(k): 构造器，设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空，返回 -1 。
- Rear: 获取队尾元素。如果队列为空，返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
题目链接
文字 和 画图 分析
- 思考什么情况下，队列为空，队列为满
定义一个 指针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);
}//释放空间本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！