java 循环队列实现_Java实现循环队列
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作
队列的实现方式
1、链表队列
2、静态队列(数组)
实现静态队列
class Queue {
private int front;
private int rear;
private Object[] objects;
private int size;
public Queue(int size) {
front = 0;
rear = 0;
this.size = size + 1;
objects = new Object[size];
}
public void add(Object o) {
if (isFull()) {
System.out.println("队列已满，无法添加");
return;
}
objects[rear] = o;
rear = (rear + 1) % size;
}
public Object get() throws EmptyException {
if (isEmpty()) {
throw new EmptyException("队列为空，无法取出元素");
}
Object o = objects[front];
front = (front + 1) % size;
return o;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % size == front;
}
public int getCount() {
return (rear - front + size) % size;
}
public void show() {
int count = getCount();
for(int i = 0; i < count; i++) {
System.out.println(objects[front]);
front = (front + 1) % size;
}
}
}
class EmptyException extends Exception {
public EmptyException() {
}
public EmptyException(String s) {
super(s);
}
}
简要分析代码
参数的意义
front 永远指向队列的 第一个元素
rear 永远指向队列的最后一个元素的 下一个位置
构造方法
队列进行初始化，front = 0，rear = 0;
为什么要 this.size = size + 1; 后面在解释
isEmpty() 和 isFull() 方法
根据 front rear 的意义，不难得出判断队列是否为空就是 front == rear
我们来看下判断队满的条件
如图，此时在添加元素5，队列就满了，同时 rear = 0
这个时候我们发现，rear == front
因此队列满的条件为：rear == front
这与判断队列空的条件相同，但是此时队列是有元素的
队列元素：2，6，3，0，1，5
因此队列满的条件不能是：rear == front
我们通常会舍弃一个空间(不用来存放数据)，也就是说，大小为 n 的数组，存放的元素的个数为 n – 1
这样判断队满的条件就变为：(rear + 1) % size == front
这也就是为什么 this.size = size + 1
因为别人不知道，你只能存放 n – 1 个数据
getCount() 方法
获取元素的个数
当 rear > front
元素个数为：rear – front
元素个数为：5 – 0 = 5
当 rear < front
第一段为：size – front
第二段为：rear – 0
因此，元素个数为：(rear – front + size)
结合两种情况：
rear > front
(rear – front + size) % size = rear – front
rear < front
(rear – front + size) % size = rear – front + size
因此，通用公式为： (rear – front + size) % size
show() 方法
遍历队列，如果我们知道队列中元素的个数，那么循环次数就确定了下来，通过前面分析，队列个数为 (rear – front + size) % size
每循环一次，就取出队列中 front 所指向的元素
取完之后，front = (front + 1) % size，指向下一个队列中的元素