💡💡接着上期讲解,我们知道在用数组完成队列的模拟时,发现当出队列时会造成空间的浪费,因为头索引无法直接回到前面,就算通过设置到0号索引,但是会出现数组不连续的情况,所以这种情况下,数组只能使用一次。
~~~那么接下来接引出一个结构,叫做循环队列 。
图片如下:
循环队列,顾名思义就是数组组成了一个圈,开始时队数组的头索引和为索引都在一个位置下。
在表示循环队列下标时,不能简单通过索引加一,如果数组最大索引为7,那么加一就会越界,此时就要通过取余的思想。
例如:当最大索引为7,我们希望下一个索引为0,那么就有(索引+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时,不知道是空了还是满了。
public boolean enQueue(int value) {
if(isFull()){
return false;
}
elem[rear]=value;
rear=(rear+1)%elem.length;
return true;
}
🌟🌟在插入元素之前要判断队列是否为空,然后再在队尾插入元素,尾部索引加一。上述所示索引的变化为rear=(rear+1)%elem.length;
public boolean deQueue() {
if(isEmpty()){
return false;
}
front=(front+1)%elem.length;
return true;
}
🌟🌟在删除元素之前判断队列是否为空,删除就是头指针往后移,实际没有删除元素,但是再次使用这个空间时,输入数据实际是将之前的数据覆盖了。
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索引前一个索引即可。
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队列为满。
💡💡在此之前我们知道队列是先进先出,栈是先进后出,所以在队列实现栈时,我们不可能用一个队列实现栈,所以这里我们就要运用两个队列。
💡💡如上图,我们将要输出的元素,即最后一个元素之前的所以元素传给空队列,然后输出5后,queue1又变成了空队列,然后要输出4就将之前的元素传给queue1,输出4后queue2又变成了空队列循环以此。
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;
}
🌟🌟首先初始化两个队列,并进行非空判断。
public void push(int x) {
if (empty()) {
queue1.offer(x);
} else {
if (queue1.isEmpty()) {
queue2.offer(x);
} else {
queue1.offer(x);
}
}
}
🌟🌟在第一次加入数据时,我们规定先加入一个数据在queue1然后再次加入数据时要判断那个不为空就加入那个队列。
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个数据传给另一个队列,然后输出队列的唯一一个数据就是栈顶元素。
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,这样不会改变队列的数据。并做到了输出栈顶元素的操作。
以上两个题目均来自力扣:
循环队列:. - 力扣(LeetCode)
队列实现栈的模拟:. - 力扣(LeetCode)
🌅🌅🌅大家有什么问题,可以在评论区指正,期待各位uu的发言。
💪💪💪以上就是本期内容了, 感兴趣的话,就关注一下小编吧。
😊😊 期待你的关注~~~