深圳网站(建设信科网络),wordpress 中文视频教程,微购电商小程序,国内建网站软件前言#xff1a; #x1f31f;#x1f31f;Hello家人们#xff0c;这期讲解数据结构队列的基础知识#xff0c;希望你能帮到屏幕前的你。 #x1f4da;️上期博客在这里#xff1a;http://t.csdnimg.cn/oOkvk #x1f4da;️感兴趣的小伙伴看一看小编主页#xff1a;G… 前言 Hello家人们这期讲解数据结构队列的基础知识希望你能帮到屏幕前的你。 ️上期博客在这里http://t.csdnimg.cn/oOkvk ️感兴趣的小伙伴看一看小编主页GGBondlctrl-CSDN博客 那么正片开始~~~ 目录
️1.循环队列 1.1引言 1.2什么是循环队列 1.3循环队列的下标表示 1.4代码实现
1.实现构造函数
2.插入元素
3.删除元素
4.输出对头元素队尾元素
5.判断队列状态
️2.运用队列完成栈的模拟 1.1引言 1.2思路 1.3代码实现
1.初始化两个队列以及状态判断
2.入栈模拟
3.出栈模拟
4.输出栈顶数据
️ 3.结束语 ️1.循环队列 1.1引言 接着上期讲解我们知道在用数组完成队列的模拟时发现当出队列时会造成空间的浪费因为头索引无法直接回到前面就算通过设置到0号索引但是会出现数组不连续的情况所以这种情况下数组只能使用一次。 ~~~那么接下来接引出一个结构叫做循环队列 。 1.2什么是循环队列
图片如下 循环队列顾名思义就是数组组成了一个圈开始时队数组的头索引和为索引都在一个位置下。 1.3循环队列的下标表示 在表示循环队列下标时不能简单通过索引加一如果数组最大索引为7那么加一就会越界此时就要通过取余的思想。 例如当最大索引为7我们希望下一个索引为0那么就有索引1%数组的长度就等于下一个索引 1.4代码实现
1.实现构造函数
class MyCircularQueue {private int elem[];private int front;private int rear;public MyCircularQueue(int k) {this.elemnew int[k1];} 注意小编这里k1是因为为了空一格位置没有数据目的是为了方便判断数组是否为空或者满如果不预留一个位置当frontrear时不知道是空了还是满了。 2.插入元素 public boolean enQueue(int value) {if(isFull()){return false;}elem[rear]value;rear(rear1)%elem.length;return true;} 在插入元素之前要判断队列是否为空然后再在队尾插入元素尾部索引加一。上述所示索引的变化为rear(rear1)%elem.length;
3.删除元素
public boolean deQueue() {if(isEmpty()){return false;}front(front1)%elem.length;return true;} 在删除元素之前判断队列是否为空删除就是头指针往后移实际没有删除元素但是再次使用这个空间时输入数据实际是将之前的数据覆盖了。
4.输出对头元素队尾元素
public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index (rear0)?elem.length-1:rear-1;return elem[index];} 队头元素在判断队列状态后直接返回在输出队尾元素时这里我们是舍弃了0索引所以当rear0时就表示队列满了在不出队列的情况下然后输出0索引前一个索引即可。
5.判断队列状态
public boolean isEmpty() {if(frontrear){return true;}return false;}public boolean isFull() {if((rear1)%this.elem.lengthfront){return true;}return false;}
如图 此时队列为空即frontrear; 此时队列为满我们设此时rear所指为0下标0下标就是我们预留的空位
所以就是当(rear1)%elem.lengthfront队列为满。 ️2.运用队列完成栈的模拟 1.1引言
在此之前我们知道队列是先进先出栈是先进后出所以在队列实现栈时我们不可能用一个队列实现栈所以这里我们就要运用两个队列。 1.2思路 如上图我们将要输出的元素即最后一个元素之前的所以元素传给空队列然后输出5后queue1又变成了空队列然后要输出4就将之前的元素传给queue1输出4后queue2又变成了空队列循环以此。 1.3代码实现
1.初始化两个队列以及状态判断
class MyStack {QueueInteger queue1;QueueInteger queue2;public MyStack() {this.queue1 new LinkedList();this.queue2 new LinkedList();}public boolean empty() {if (queue2.isEmpty() queue1.isEmpty()) {return true;}return false;} 首先初始化两个队列并进行非空判断。
2.入栈模拟
public void push(int x) {if (empty()) {queue1.offer(x);} else {if (queue1.isEmpty()) {queue2.offer(x);} else {queue1.offer(x);}}} 在第一次加入数据时我们规定先加入一个数据在queue1然后再次加入数据时要判断那个不为空就加入那个队列。
3.出栈模拟 public int pop() {if (queue2.isEmpty()) {while (queue1.size() 1) {int ret queue1.poll();queue2.offer(ret);}return queue1.poll();} else {while (queue2.size() 1) {int ret queue2.poll();queue1.offer(ret);}return queue2.poll();}} 那个不为空就将那个队列的数组的size-1个数据传给另一个队列然后输出队列的唯一一个数据就是栈顶元素。
4.输出栈顶数据 public int top() {if (queue2.isEmpty()) {while (queue1.size() 1) {int ret queue1.poll();queue2.offer(ret);}int ret queue1.peek();queue1.poll();queue2.offer(ret);return ret;} else {while (queue2.size() 1) {int ret queue2.poll();queue1.offer(ret);}int ret queue2.peek();queue2.poll();queue1.offer(ret);return ret;}}
这里和出栈其实差别不大最要时在进行数据传递给另一个队列后要输出最后一个数据并且完成后要将这个数据继续给另一个队列 例如queue1传给queue2size-1个元素后输出queue的最后一个元素后再将这个元素继续传给queue2这样不会改变队列的数据。并做到了输出栈顶元素的操作。 ️3.结束语
以上两个题目均来自力扣
循环队列. - 力扣LeetCode
队列实现栈的模拟. - 力扣LeetCode 大家有什么问题可以在评论区指正期待各位uu的发言。 以上就是本期内容了 感兴趣的话就关注一下小编吧。 期待你的关注~~~
