点击上方“IT那活儿”公众号--专注于企业全栈运维技术分享，不管IT什么活儿，干就完了！！！
队列及环形队列定义
队列是一种线性数据结构，它遵循先进先出或后近后出的原则。队列允许在一端插入元素，另一端删除元素。队列有时也被称为待办事项列表，尤其是在计算机程序中，它被广泛用于任务排队、缓存和异步处理方案中。
环形队列，它可以在固定大小的数组中循环使用。它类似于普通队列，但与普通队列不同的是，在环形队列中，队列的队尾可以接到数组的开头，使数组像一个圆环一样循环。因此，环形队列往往比普通队列的效率更高，尤其是在实现循环缓冲区等应用时。环形队列主要的操作有入队和出队。
环形队列的特点
队列的存储结构是一个环形结构，即队列的头尾相连，形成一个环形。 队列有固定的大小，通常用数组来实现。 队列的插入和删除操作只能在队头和队尾进行，而不能在中间进行。 当队列的头指针或尾指针达到队列的末尾时，它们将指向队列的起始位置，形成环形。 环形队列的操作效率较高，只需要通过指针的移动来完成插入和删除操作。
设计背景和思路
3.1 设计背景
在计算指标生成的时候，当该时间段没有统计到该指标，就取他最近前两个指标的平均值，这样的话历史指标的保存和获取，就要用到一个队列来存储，考虑环形队列的特点，自动清理过期数据，使用效率高的特点，所以设计一个数组环形队列。
3.2 设计思路
front
就指向队列的第一个元素, front 的初始值 = 0；
rear
指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定,rear 的初始值 = 0；
当队列满时，条件是 (rear + 1) % maxSize == front 【满】；
对队列为空的条件， rear == front 【空】；
队列中有效数据的个数 (rear + maxSize - front) % maxSize。
测试结果
ArrayQueue arrayQueue = new ArrayQueue(4); //初始化一个队列
arrayQueue.addQueue(1);
arrayQueue.addQueue(2);
arrayQueue.addQueue(3);
arrayQueue.addQueue(4);
arrayQueue.addQueue(5); //右边的图多了这个操作
代 码
package structure;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 环形队列测试
*/
//支持，队列满了后，自动删除最老的数据
publicclassArrayQueueDemoV2 {
publicstaticvoidmain(String[] args) {
// List<Integer> list = new ArrayList<>(3);
// list.add(1);
// list.add(2);
// System.out.println("size:"+list.size());
// list.add(3);
// list.add(4);
//
// for (Integer i : list) {
// System.out.println(i);
// }
test03();
}
publicstaticvoidtest03(){
ArrayQueue arrayQueue = new ArrayQueue(6); //初始化一个队列
int i = 0;
while(i< 100){
arrayQueue.addQueue(i++);
arrayQueue.addQueue(i++);
System.out.println("按照asc：");
arrayQueue.showQueue();
System.out.println("按照desc：");
List<Integer> list = arrayQueue.showQueueByDesc(2);
for (Integer integer : list) {
System.out.println(integer);
}
}
}
publicstaticvoidtest02(){
ArrayQueue arrayQueue = new ArrayQueue(6); //初始化一个队列
int i = 0;
while(i< 100){
arrayQueue.addQueue(i++);
arrayQueue.addQueue(i++);
System.out.println("按照asc：");
arrayQueue.showQueue();
System.out.println("按照desc：");
arrayQueue.showQueueByDesc();
}
}
publicstaticvoidtest01(){
ArrayQueue arrayQueue = new ArrayQueue(4); //初始化一个队列
arrayQueue.addQueue(1);
arrayQueue.addQueue(2);
arrayQueue.addQueue(3);
arrayQueue.addQueue(4);
arrayQueue.addQueue(5);
// arrayQueue.addQueue(6);
System.out.println("获取队头数据："+arrayQueue.headQueue());
System.out.println("打印队列当前数据：");
arrayQueue.showQueue();
}
publicstaticvoidprintTest(){
ArrayQueue arrayQueue = new ArrayQueue(3); //初始化一个队列
char key = ' '; //用于判断用户的操作
Scanner scanner = new Scanner(System.in);
boolean flag = true;
while (flag) {
System.out.println("s(show),显示队列");
System.out.println("a(add),添加数据到队列");
System.out.println("g(get),从队列取出数据");
System.out.println("h(head),查看对头数据");
System.out.println("e(exit),退出程序");
key = scanner.next().charAt(0);
switch (key) {
case's':
arrayQueue.showQueue();
break;
case'a':
System.out.println("请输入一个数字");
int val = scanner.nextInt();
try {
arrayQueue.addQueue(val); //如果队列中没有数据则会报错,所以用了个try,catch防止报错
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case'g':
try {
System.out.println("取出的数据是:" + arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case'h':
try { //如果队列中没有数据则会报错,所以用了个try,catch防止报错
System.out.println("队列头数据是:" + arrayQueue.headQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case'e':
flag = false;
scanner.close();
break;
}
}
System.out.println("退出程序成功");
}
publicstaticclassArrayQueue {
privateint maxSize; //表示数组最大容量
privateint front; //队列头部
privateint rear;//队列尾
privateint[] arr; //模拟队列的数组
publicArrayQueue(int maxSize) {
front = 0; //指向队列元素第一位
rear = 0; //指向队列最后一个元素的后一位
this.maxSize = maxSize;//赋值队列的最大容量
arr = newint[maxSize];//初始化模拟队列的数组
}
//判断队列是否为满
public boolean isFull() {
return (rear + 1) % maxSize == front; //这里环形数组会预留一个位置
// return rear % maxSize == front; 这里环形数组会预留一个位置
// 所以maxsize为3的时候 只会存入2个数值
}
//判断队列是否为空
public boolean isEmpty() {
return rear == front; //如果头指针等于尾指针则队列为空
}
//添加数据到队列
publicvoidaddQueue(int num) {
// 判断队列是否满
if (isFull()) {
//todo 方案1：队列满了，不让再继续入队列
//System.out.println("队列满，不能加入数据!!!");
//todo 方案2：队列满了，自动清理，最早入队的那个数据
System.out.println("队列满了,数据出队列："+getQueue());
//return;
}
//直接将数据加入
arr[rear] = num;
//将 rear 后移, 这里必须考虑取模,当rear指向最后一个位置的时候，
// 加1则会重新标记为第一个位置，从而实现了环形
rear = (rear + 1) % maxSize;
}
//数据出队列
publicintgetQueue() {
//判断队列是否为空
if (isEmpty()) {
thrownew RuntimeException("队列为空!");
}
int val = arr[front]; //先把front指向的数据取出来
front = (front + 1) % maxSize; //头指针后移
return val; //返回数据
}
//显示队列内容,按照先后顺序打印
publicvoidshowQueue() {
// 2 2+ 3
for (int i = front; i < front + size(); i++) {
// 2,3,4下表
int index = i%maxSize;
System.out.println(arr[index]);
}
}
publicvoidshowQueueByDesc() {
// 2 2+ 3
for (int i = front + size() -1; i >= front; i--) {
// 4,3,2表
int index = i%maxSize;
System.out.println(arr[index]);
}
}
public List<Integer> showQueueByDesc(int count) {
// 2 2+ 3
List<Integer> list = new ArrayList<>(count);
for (int i = front + size() -1; i >= front; i--) {
// 4,3,2表
int index = i%maxSize;
//System.out.println(arr[index]);
list.add(arr[index]);
if(list.size()==count){
break;
}
}
return list;
}
publicintsize() {
// 1+ 4 - 2 4 = 3
return (rear + (maxSize) - front) % maxSize;//其实也是rear-front演化过来
//小伙伴可以好好思考一下
}
//查看队列第一个元素
publicintheadQueue() {
//判断队列是否为空
if (isEmpty()) {
thrownew RuntimeException("队列为空!");
}
return arr[front]; //返回数据
}
}
}
本文作者：田兆壮(上海新炬中北团队）
本文来源：“IT那活儿”公众号
文章转载自IT那活儿，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
