四川网站建设找珊瑚云,哈尔滨营销网站建设,襄阳市建设公司网站,广告公司简介模板及介绍目录
设计循环队列
#x1f642;【1】数组循环队列
思路分析
❓1
❓2
❓3
易错总结
创建MyCircularQueue
初始化myCircularQueueCreate
为空否myCircularQueueIsEmpty
为满否myCircularQueueIsFull
插入元素myCircularQueueEnQueue
删除元素myCircularQueueDeQue…目录
设计循环队列
【1】数组循环队列
思路分析
❓1
❓2
❓3
易错总结
创建MyCircularQueue
初始化myCircularQueueCreate
为空否myCircularQueueIsEmpty
为满否myCircularQueueIsFull
插入元素myCircularQueueEnQueue
删除元素myCircularQueueDeQueue
获取首元素myCircularQueueFront
获取尾元素myCircularQueueRear
释放空间myCircularQueueFree
【1】总代码
【2】链表循环队列
思路分析
❓
易错总结
创建MyCircularQueue
初始化myCircularQueueCreate
为空否myCircularQueueIsEmpty
为满否myCircularQueueIsFull
插入元素myCircularQueueEnQueue
删除元素myCircularQueueDeQueue
获取首元素myCircularQueueFront
获取尾元素myCircularQueueRear
释放空间myCircularQueueFree
【2】总代码 另外扩展了解一下实际中我们有时还会使用一种队列叫【循环队列】。如操作系统讲解【生产者消费者模型】时可以就会使用循环队列。环形队列可以使用【数组】实现也可以使用循环【链表】实现。我们今天来实现一下。
设计循环队列 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 你的实现应该支持如下操作 MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 【1】数组循环队列 这个【数组循环队列】在逻辑上是如上图所示但是在物理上不是循环的。所以特别注意关于数组循环的这个点我们必须手动控制。
思路分析
❓1
空和放一个元素怎么区分 方法1back初始化为0指向队尾元素的下一个位置。方法2back初始化为-1指向队尾元素。 特别提醒用方法1比较好控制 ❓2
空和满怎样去区分用方法1区分空和一个元素 方法1设置size。方法2malloc多一个空间不放置元素。k1)以上两者方法都可以。 ❓3
怎么处理数组物理上不循环改成逻辑上循环 (back1)%(k1) fronobj-back % obj-k1return obj-a[(obj-back-1obj-k1)%(obj-k1)] 这里是以判空和满的来讲解其他的插入和取尾元素是同理的
易错总结
临时变量出了函数就销毁了必须mallocA%BAB对A来说是没有任何影响AB对A来说模去多余的B---用来处理数组回绕地方操作符优先级 所以最好都加上括号处理的表达式的左边不能为计算式❌obj-front1%obj-k1;判空和满直接下标运算即可不用用数组为什么不能用数组❓释放空间先释放数组空间在释放myCircularQueue 创建MyCircularQueue
//用数组实现多开辟一个空间不放元素
typedef struct {int*a;int front;int back;//数组下标int k;//循环队列的最多放置数据
} MyCircularQueue;
初始化myCircularQueueCreate
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int*tmp(int*)malloc(sizeof(int)*(k1));//多开辟一个空间obj-atmp;obj-front0;obj-back0;//指向最后一个元素的下一个obj-kk;return obj;
}
为空否myCircularQueueIsEmpty
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-back;//0
}
为满否myCircularQueueIsFull
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1) % (obj-k1) obj-front;//back1front//操作符优先级问题
}
插入元素myCircularQueueEnQueue 考虑下这个特殊情况 //插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}obj-a[obj-back] value;obj-back;obj-back % obj-k1;//处理//obj-front1%obj-k1;//处理左边不能为计算表达式return true;
}
删除元素myCircularQueueDeQueue 考虑下这个特殊情况
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj-front;obj-front%obj-k1;//处理return true;}
}
获取首元素myCircularQueueFront
//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}elsereturn obj-a[obj-front];
}
获取尾元素myCircularQueueRear 考虑下这个特殊情况 //获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else//return obj-a[(obj-back-1obj-k1)%(obj-k1)];return obj-a[(obj-backobj-k)%(obj-k1)];
}
释放空间myCircularQueueFree
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);objNULL;
}
【1】总代码
//用数组实现多开辟一个空间不放元素
typedef struct {int*a;int front;int back;//数组下标int k;//循环队列的最多放置数据
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int*tmp(int*)malloc(sizeof(int)*(k1));//多开辟一个空间obj-atmp;obj-front0;obj-back0;//指向最后一个元素的下一个obj-kk;return obj;
}
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-back;//0
}//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back1) % (obj-k1) obj-front;//back1front//操作符优先级问题
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}obj-a[obj-back] value;obj-back;obj-back % obj-k1;//处理//obj-front1%obj-k1;//处理左边不能为计算表达式return true;
}//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj-front;obj-front%obj-k1;//处理return true;}
}//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}elsereturn obj-a[obj-front];
}//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else//return obj-a[(obj-back-1obj-k1)%(obj-k1)];return obj-a[(obj-backobj-k)%(obj-k1)];
}//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);objNULL;
}
【2】链表循环队列 链表很简单对于处理循环的问题只要实现单项循环链表即可。这里的难点就是1创建单项循环链表。2找到back的前一个元素
思路分析
关于判【空/一个元素】 判【空/满】都是和上面数组是一样的。这里不过多阐述。
❓
怎么去找到back的前一个元素
其实这个问题在我们前面博文实现链表也详细讲解相信大家可以轻松掌握 Node*prevobj-front;while(prev-next ! obj-back){prevprev-next;}
易错总结
初始化一定要把back置回开头找back前一个元素要么用三个指针要么遍历一遍链表。释放空间不能遍历去释放会造成野指针。释放空间先把循环链表改变成单向链表才能循环遍历释放。
创建MyCircularQueue
typedef struct Node
{int val;struct Node*next;
}Node;//节点typedef struct {Node*front;Node*back; int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列
初始化myCircularQueueCreate
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-frontNULL;obj-backNULL;while(k--){Node*newnode(Node*)malloc(sizeof(Node));if(obj-front NULL){obj-frontobj-backnewnode;obj-front-val0;}else{obj-back-nextnewnode;obj-backnewnode;obj-back-val0;}}//循环obj-back-nextobj-front;//backobj-backobj-front;//obj-size0;return obj;
}
为空否myCircularQueueIsEmpty
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-size 0 obj-front obj-back)return true;elsereturn false;
}
为满否myCircularQueueIsFull
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj-size ! 0 obj-front obj-back)return true;elsereturn false;
}
插入元素myCircularQueueEnQueue
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}else{obj-back-valvalue;obj-backobj-back-next;obj-size;return true;}
}
删除元素myCircularQueueDeQueue
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}else{obj-frontobj-front-next;//❌易错obj-size--;return true;}
}
获取首元素myCircularQueueFront
//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-front-val;
}
获取尾元素myCircularQueueRear
//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}//❌易错else{Node*prevobj-front;while(prev-next ! obj-back){prevprev-next;}return prev-val;}
}
释放空间myCircularQueueFree
//释放空间
//❌易错
void myCircularQueueFree(MyCircularQueue* obj) {Node*prevobj-front;while(prev-next ! obj-front){prevprev-next;}//prev是最后一个prev-nextNULL;//while(obj-front-next ! NULL){Node*tmpobj-front;obj-frontobj-front-next;free(tmp);tmpNULL;}free(obj-front);obj-frontNULL;free(obj);objNULL;
}
【2】总代码
typedef struct Node
{int val;struct Node*next;
}Node;//节点typedef struct {Node*front;Node*back; int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-frontNULL;obj-backNULL;while(k--){Node*newnode(Node*)malloc(sizeof(Node));if(obj-front NULL){obj-frontobj-backnewnode;obj-front-val0;}else{obj-back-nextnewnode;obj-backnewnode;obj-back-val0;}}//循环obj-back-nextobj-front;//backobj-backobj-front;//obj-size0;return obj;
}//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-size 0 obj-front obj-back)return true;elsereturn false;
}//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj-size ! 0 obj-front obj-back)return true;elsereturn false;
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}else{obj-back-valvalue;obj-backobj-back-next;obj-size;return true;}
}//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}else{obj-frontobj-front-next;obj-size--;return true;}
}//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-front-val;
}//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}else{Node*prevobj-front;while(prev-next ! obj-back){prevprev-next;}return prev-val;}
}//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {Node*prevobj-front;while(prev-next ! obj-front){prevprev-next;}//prev是最后一个prev-nextNULL;//while(obj-front-next ! NULL){Node*tmpobj-front;obj-frontobj-front-next;free(tmp);tmpNULL;}free(obj-front);obj-frontNULL;free(obj);objNULL;
} 还有数据结构的【栈】和操作系统的【栈】是不一样的。数据结构的【栈】是一种线性表。操作系统的【栈】是内存的区域会发生栈溢出和内存泄露的问题递归程序/返回条件有问题但是数据结构【栈】不会。
✔✔✔✔✔最后感谢大家的阅读若有错误和不足欢迎指正
