循环队列
一、循环队列
为充分利用向量空间,克服"假溢出"现象,将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列。
喏,百度上找的图片hiahiahia
消除假溢出就是当队尾指针rear和队首指针front到达存储空间的最大值maxsize时,让rear指针自动转化为存储空间的最小值;
二、解决指针的转化问题
[问题1]:当rear指针到达存储空间最大值maxSize时,怎样让它自动转化为存储空间的最小值?
this.rear = (this.rear+1) % maxSize;
-
rear + 1为在front位置添加元素后,rear指针应该移动的位置
-
当rear + 1<maxSize时,让rear + 1对maxSize进行求余操作时,其值依然是它本身;
-
如图,假设这时在rear = 5的位置让f入队,此时rear(5) + 1 = 6,等于maxSize,
(this.rear+1) % maxSize
的值就等于0,相当于使rear指针回到了最开始的队首位置,实现了队列的循环;
[问题2]:同理,当front到达maxSize时,若此时队列里还有元素,再进行一次出队操作时,front指针也需回到0号位置,则front要自动转化也需要满足:this.front = (this.front+1) % maxSize
[问题3]:循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front == rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有两种:
-
另设一布尔变量以区别队列的空和满;
-
另一种方式就是数据结构常用的: 队满时:(rear+1)%maxSize ==front,maxSize为队列长度(所用数组大小),由于rear,front均为所用空间的指针,循环只是逻辑上的循环,所以需要求余运算。
- 判满
判断条件:(this.rear+1)%maxSize == this.front
与上面使rear指针回到0号位置的分析类似,当(rear+1)% maxSize = front 时,rear和front指针相遇,即此时确定队列已经满了,但rear位置其实并没有存放元素,空出来一个位置用来区分队列的满空状态,也就是说队列实际容量比数组容量小1;
- 判空
判断条件this.front == this.rear
在上面已经说过,队满时有(rear+1)% maxSize = front
,所以队列中有元素时,rear与front永远不会相等,所以当rear == front
时,队列为空;
三、实现一个循环队列
- 数据结构
class Queue<E> {
private int front;//队头
private int rear;//队尾
private Object[] elem;
private int usedSize = 0;
private int maxSize; //数组最大容量
public Queue() {
this(10);
}
public Queue(int size) {
this.front = 0;
this.rear = 0;
this.elem = new Object[size];
maxSize = this.elem.length;
}
- 具体操作
除了rear和front指针需要转化之外(已经在第二个问题中进行过分析),循环队列的操作和顺序队列的操作几乎相同,点击顺序队列,有较为详细的注释;
- 判空
public boolean isEmpty() {
return this.front == this.rear;
}
- 判满
//判满
public boolean isFull() {
return ((this.rear+1) % maxSize == this.front);
}
- 入队列
//入队列
public void push(E val) {
if (isFull()) {
System.out.println("队列已满,无法入队");
return;
}
this.elem[this.rear] = val;
this.rear = (this.rear+1) % maxSize;
this.usedSize++;
}
- 出队列
//出队列
public void pop() {
if (isEmpty()) {
throw new UnsupportedOperationException("队列为空");
}
this.front = (this.front+1) % maxSize;
this.usedSize--;
}
- 获取队首元素
//获取队首元素
public E peek() {
if (isEmpty()) {
throw new UnsupportedOperationException("队列为空");
}
E data = (E)this.elem[this.front];
return data;
}
- 打印
//打印
public void show() {
for (int i = this.front;i != this.rear;i = (i+1) % maxSize) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
}