【数据结构题目】循环队列，以及队列实现栈的模拟
【数据结构题目】循环队列，以及队列实现栈的模拟
📚️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;
}
}🌟🌟这里和出栈其实差别不大，最要时在进行数据传递给另一个队列后，要输出最后一个数据，并且完成后要将这个数据继续给另一个队列，
例如：queue1传给queue2（size-1）个元素后输出queue的最后一个元素后，再将这个元素继续传给queue2，这样不会改变队列的数据。并做到了输出栈顶元素的操作。
📚️3.结束语
以上两个题目均来自力扣：
循环队列：. - 力扣（LeetCode）
队列实现栈的模拟：. - 力扣（LeetCode）
🌅🌅🌅大家有什么问题，可以在评论区指正，期待各位uu的发言。
💪💪💪以上就是本期内容了， 感兴趣的话，就关注一下小编吧。
😊😊 期待你的关注~~~
腾讯云开发者
