当前位置：首页 > news >正文

【数据结构题目】循环队列，以及队列实现栈的模拟

news 来源：原创 2024/9/20 6:13:18

前言：

🌟🌟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.elem=new int[k+1];}

🌟🌟注意：小编这里k+1是因为为了空一格位置没有数据，目的是为了方便判断数组是否为空或者满，如果不预留一个位置，当front==rear时，不知道是空了还是满了。

2.插入元素：

 public boolean enQueue(int value) {if(isFull()){return false;}elem[rear]=value;rear=(rear+1)%elem.length;return true;}

🌟🌟在插入元素之前要判断队列是否为空，然后再在队尾插入元素，尾部索引加一。上述所示索引的变化为rear=(rear+1)%elem.length;

3.删除元素：

public boolean deQueue() {if(isEmpty()){return false;}front=(front+1)%elem.length;return true;}

🌟🌟在删除元素之前判断队列是否为空，删除就是头指针往后移，实际没有删除元素，但是再次使用这个空间时，输入数据实际是将之前的数据覆盖了。

4.输出对头元素，队尾元素：

public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index= (rear==0)?elem.length-1:rear-1;return elem[index];}

🌟🌟队头元素在判断队列状态后直接返回，在输出队尾元素时，这里我们是舍弃了0索引，所以当rear=0时就表示队列满了（在不出队列的情况下），然后输出0索引前一个索引即可。

5.判断队列状态：

public boolean isEmpty() {if(front==rear){return true;}return false;}public boolean isFull() {if((rear+1)%this.elem.length==front){return true;}return false;}

如图：

此时队列为空；即front==rear;

此时队列为满我们设此时rear所指为0下标，0下标就是我们预留的空位

所以就是当(rear+1)%elem.length==front队列为满。

📚️2.运用队列完成栈的模拟

🎥1.1引言：

💡💡在此之前我们知道队列是先进先出，栈是先进后出，所以在队列实现栈时，我们不可能用一个队列实现栈，所以这里我们就要运用两个队列。

🎥1.2思路：

💡💡如上图，我们将要输出的元素，即最后一个元素之前的所以元素传给空队列，然后输出5后，queue1又变成了空队列，然后要输出4就将之前的元素传给queue1，输出4后queue2又变成了空队列循环以此。

🎥1.3代码实现：

1.初始化两个队列以及状态判断

class MyStack {Queue<Integer> queue1;Queue<Integer> 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;}}

🌟🌟这里和出栈其实差别不大，最要时在进行数据传递给另一个队列后，要输出最后一个数据，并且完成后要将这个数据继续给另一个队列，