【数据结构初阶】顺序循环队列和链式循环队列
2023-02-25 18:20:13 时间
目录
1.知识点
让我们先对比一下普通队列和循环队列
https://blog.csdn.net/qq_64428099/article/details/126173181
第一个问题:顺序循环队列和链式循环队里怎么做到循环? 循环队列是定长的数组,循环数组在循环方面物理上肯定不能做到循环,所以我们采用逻辑上循环的方式,当tail或者front到了边界的时候,手动"拉到"合适的位置,逻辑上造成一种循环. 而循环链表在循环方面物理上是可以做到循环的(循环链表) 而逻辑上就更是自动->next就能回到合适的位置造成循环. 第二个问题:由于循环队列是定长的,定长的话和普通队列不一样,不定长的话,只用考虑为队列空的情况,定长的话,除了考虑为空的情况,还需要考虑队列为满的情况. 至于如何判断队列为空和队列满了?请往下看
回顾一下我们以前队列判空的逻辑:(指向同一个值为空的数组元素或者节点 顺序普通队列:a[front]==a[tail] 链式普通队列:front==tail 如果我们和之前一样的方式判断满的话,我们会发现
这判断队列满的方式怎么和判断队列空的方式一模一样,这可怎么整啊!倒时候没办法区分不是乱套了吗?!别急,有办法~~
解决判断队列为空和队列满有两种解决方案:
- 方法一: 在MyCircularQueue结构体中设置一个size成员变量,用于记录实际的元素个数,而定长K是题目会给的,我们也相应的记录为capacity就行了,空就是size==0;满就是size==capacity;
- 方法二 多开一个空间,使得满的时候永远有一个位置不存数据,就好比这样就是满了
下面以方法2为例:
特别注意:这里的方法二中的满的时候永远空出一个空间,不一定是最后一个空间! 当入队列时有元素出队列时此时就可以使得空出的那一个位置不是最后那个空间!例如上图链式循环队列.
2.顺序循环队列
https://leetcode.cn/problems/design-circular-queue/submissions/
typedef struct {
int* a;
int k;
int front;
int tail;
} 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->tail=0;
return obj;
}
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail]=value;
//书写方式1:
// obj->tail++;
// if(obj->tail==obj->k+1)
// {
// obj->tail=0;
// }
//书写方式2:
obj->tail=(obj->tail+1)%(obj->k+1);
return true;
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) ;
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
//书写方式1:
// obj->front++;
// if(obj->front==obj->k+1)
// {
// obj->front=0;
// }
//书写方式2:
obj->front=(obj->front+1)%(obj->k+1);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
// int tailPrev=obj->tail-1;
// if(tailPrev==-1)
// {
// tailPrev=obj->k;
// }
// return obj->a[tailPrev];
return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
// int tailNext=obj->tail+1;
// if(tailNext==obj->k+1)
// {
// tailNext=0;
// }
int tailNext=(obj->tail+1)%(obj->k+1);
return obj->front==tailNext;
// return obj->a[obj->tail+1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->tail=obj->front=0;
obj->k=0;
free(obj);
}
3.链式循环队列
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>;
#include<stdbool.h>
typedef struct ListNode
{
int val;
struct ListNode* next;
}ListNode;
typedef struct MyCirQue
{
ListNode* front;
ListNode* prev;
ListNode* tail;
int size;
}MyCirQue;
MyCirQue* MyCirQueInit(int k)
{
MyCirQue* ps = (MyCirQue*)malloc(sizeof(MyCirQue));
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = NULL;
ps->prev = NULL;
ps->front = ps->tail = newnode;
ps->size = 0;
while (--k)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = NULL;
ps->tail->next = newnode;
ps->tail = ps->tail->next;
ps->size++;
}
ps->tail->next = ps->front;
ps->tail = ps->front;
}
bool MyCirQueIsEmpty(MyCirQue* ps)
{
return ps->front == ps->tail;
}
bool MyCirQueIsFull(MyCirQue* ps)
{
return ps->tail->next == ps->front;
}
bool MyCirQuePush(MyCirQue* ps, int x)
{
if (MyCirQueIsFull(ps))
{
return false;
}
else
{
ps->tail->val = x;
ps->prev = ps->tail;
ps->tail = ps->tail->next;
return true;
}
}
bool MyCirQuePop(MyCirQue* ps)
{
if (MyCirQueIsEmpty(ps))
{
return false;
}
else
{
ps->front = ps->front->next;
return true;
}
}
int MyCirQueFront(MyCirQue* ps)
{
if (MyCirQueIsEmpty(ps))
{
return -100;
}
else
{
return ps->front->val;
}
}
int MyCirQueTail(MyCirQue* ps)
{
if (MyCirQueIsEmpty(ps))
{
return -100;
}
else
{
return ps->prev->val;
}
}
void MyCirQuePrint(MyCirQue* ps)
{
ListNode* cur = ps->front;
while (cur != ps->tail)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
}
void SListDestory(MyCirQue* ps)
{
ListNode* cur = ps->front;
while (ps->size--)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
}
void MyCirQueDestory(MyCirQue* ps)
{
SListDestory(ps);
free(ps);
}
int main()
{
MyCirQue* ps = MyCirQueInit(5);
MyCirQuePush(ps, 1);
MyCirQuePush(ps, 2);
MyCirQuePush(ps, 3);
MyCirQuePush(ps, 4);
MyCirQuePop(ps);
MyCirQuePrint(ps);
MyCirQueDestory(ps);
return 0;
}
4.一道妙的选择题
- 题目: 现有一顺序循环队列,其队头为front,队尾为rear,循环队列长度为N,最多存储N-1个数据。其队内有效长度为( B)
- 内容: A.(rear - front + N) % N + 1 B.(rear - front + N) % N C.(rear - front) % (N + 1) D.(rear - front + N) % (N - 1)
- 答案:B
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023