1. 应用场景
如银行排队系统等
2. 思路
*数组实现队列 Queue（一次性）（环形队列解决的是普通数组队列的不可复用的限制）
- 当添加数据时，rear指向数组最后一位且数组未满，则将 “rear+1” 后对 arraySize进行 取模，即将队列尾部移动到数组头部。
- front： 指向队列 第一个元素的位置，初始值为0
- rear： 指向队列 最后一个元素 的 下一个位置，初始值为0
- 队列 已满 的条件：
(rear + 1) % arraySize == front
- 队列 为空 的条件：
rear == front
- 队列中 有效数据的个数 ：
(maxSize + rear - front) % arraySize
- rear 所在位置不存放数据，方便取模
【数据结构与算法(Java)】数组实现环形队列Circle Queue1. 应用场景2. 思路3. 数据结构（类结构）4. 完整实现
3. 数据结构（类结构）
（1）成员变量（Field）
- ringArray： int 数组，用于存放队列 数据
- ringArraySize： int，队列的 最大容量
- front： int，指向队列 头部数据 的 前一个位置，随着数据 输出 改变
- rear： int，指向队列 尾部数据 的位置，随着数据 输入 改变
private int[] ringArray;
private int ringArraySize;
private int front;
private int rear;
（2）初始化 / 构造器（Constructor）
- 传入arraySize参数
- 初始化全部成员变量
public CircleArrayQueue(int ringArraySize) {
this.ringArraySize = ringArraySize;
this.ringArray = new int[ringArraySize];
this.rear = 0;
this.front = 0;
}
（3）方法（Methods）
- 判断队列是否为空：
isQueueEmpty() -> boolean
- rear 和 front 是否重合
public boolean isQueueEmpty() {
// rear 和 front 是否重合
return this.rear == this.front;
}
- 判断队列是否已满：
isQueueFull() -> boolean
- rear + 1 和 front 是否重合
public boolean isQueueFull() {
// rear + 1 和 front 是否重合
return (this.rear + 1) % this.ringArraySize == this.front;
}
- 获取已储存数据的个数：
getValidDataCount() -> int
- (rear + ringArraySize - front) % ringArraySize
public int getValidDataCount() {
return (this.rear + this.ringArraySize - this.front) % ringArraySize;
}
- 添加数据：
addData(int data)
1. 判断队列是否已满，已满则抛出异常，结束方法
2. 添加数据到 rear 所在位置
3. rear 后移，若到达数组最后一项，则通过 取模 回到第一项
public void addData(int data) {
// 1. 判断数组是否已满
if (this.isQueueFull()) {
throw new RuntimeException("The array is full");
}
// 2. 添加数据到 rear 所在位置
this.ringArray[this.rear] = data;
// 3. rear 后移，若到达数组最后一项，则通过取模回到第一项
this.rear = (this.rear + 1) % this.ringArraySize;
}
- 取出数据：
fetchData() -> int
1. 判断队列是否为空，为空则抛出异常，结束方法
2. 取出数据
（1）获取 front所在位置 数据，存入 临时变量
（2）原位置数据 设置为 0
（3）front后移一位
3. 返回临时变量的数据
public int fetchData(){
// 1. 判断数组是否为空
if (this.isQueueEmpty()) {
throw new RuntimeException("The array is empty!");
}
/* 2. 取出数据
（1）获取front所在位置数据，存入临时变量
（2）原位置数据设置为 0
（3）front后移一位
*/
int tempData = this.ringArray[this.front];
this.ringArray[front] = 0;
this.front = (this.front + 1) % this.ringArraySize;
// 3. 返回临时变量的数据
return tempData;
}
- 显示全部数据：
displayAll()
1. 判断队列是否为空，为空则直接return结束方法
2. 遍历 数组，从 front位置开始 打印数据，到 rear前一个位置停止
public void displayAllData(){
// 1. 判断数组是否为空
if (this.isQueueEmpty()) {
System.out.println("The array is empty!");
return;
}
// 2. 遍历数组，从front位置开始打印数据，到rear前一个位置停止
for (int position = this.front; position < this.front + this.getValidDataCount(); position++) {
System.out.print(this.ringArray[position % this.ringArraySize] + "\t");
}
}
- 获取头部数据：
peekHeadData() -> int
1. 判断队列是否为空，为空则抛出异常
2. array返回位于 front 所在位置 的数据
public int peekHeadData(){
// 1. 判断队列是否为空，为空则抛出异常
if (this.isQueueEmpty()) {
throw new RuntimeException("The array is empty!");
}
// 2. 返回 front 所在位置的数据
return this.ringArray[this.front];
}
4. 完整实现
// 数组模拟环形队列
public class CircleArrayQueue {
private int[] ringArray;
private int ringArraySize;
private int front;
private int rear;
public CircleArrayQueue(int ringArraySize) {
this.ringArraySize = ringArraySize;
this.ringArray = new int[ringArraySize];
this.rear = 0;
this.front = 0;
}
// 判断队列是否为空
public boolean isQueueEmpty() {
// rear 和 front 是否重合
return this.rear == this.front;
}
// 判断数组是否已满
public boolean isQueueFull() {
// rear + 1 和 front 是否重合
return (this.rear + 1) % this.ringArraySize == this.front;
}
// 获取已储存数据的个数
public int getValidDataCount() {
return (this.rear + this.ringArraySize - this.front) % ringArraySize;
}
// 添加数据
public void addData(int data) {
// 1. 判断数组是否已满
if (this.isQueueFull()) {
throw new RuntimeException("The array is full");
}
// 2. 添加数据到 rear 所在位置
this.ringArray[this.rear] = data;
// 3. rear 后移，若到达数组最后一项，则通过取模回到第一项
this.rear = (this.rear + 1) % this.ringArraySize;
}
// 取出数据
public int fetchData(){
// 1. 判断数组是否为空
if (this.isQueueEmpty()) {
throw new RuntimeException("The array is empty!");
}
/* 2. 取出数据
（1）获取front所在位置数据，存入临时变量
（2）原位置数据设置为 0
（3）front后移一位
*/
int tempData = this.ringArray[this.front];
this.ringArray[front] = 0;
this.front = (this.front + 1) % this.ringArraySize;
// 3. 返回临时变量的数据
return tempData;
}
// 显示全部数据
public void displayAllData(){
// 1. 判断数组是否为空
if (this.isQueueEmpty()) {
System.out.println("The array is empty!");
return;
}
// 2. 从front位置开始打印数据，到rear前一个位置停止
for (int position = this.front; position < this.front + this.getValidDataCount(); position++) {
System.out.print(this.ringArray[position % this.ringArraySize] + "\t");
}
}
// 显示头部数据
public int peekHeadData(){
// 1. 判断队列是否为空，为空则抛出异常
if (this.isQueueEmpty()) {
throw new RuntimeException("The array is empty!");
}
// 2. 返回 front 所在位置的数据
return this.ringArray[this.front];
}
public int getRear() {
return this.rear;
}
public int getFront() {
return this.front;
}
public int getRingArraySize() {
return this.ringArraySize;
}
public int[] getRingArray() {
return this.ringArray;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
CircleArrayQueue that = (CircleArrayQueue) o;
return ringArraySize == that.ringArraySize &&
rear == that.rear &&
front == that.front &&
Arrays.equals(ringArray, that.ringArray);
}
@Override
public int hashCode() {
int result = Objects.hash(ringArraySize, rear, front);
result = 31 * result + Arrays.hashCode(ringArray);
return result;
}
}
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)