数组模拟队列
队列是一个有序列表，可以用数组或链表来实现，队列遵循先进先出的原则，即先存入的队列的数据要先取出，比如银行的排队叫号系统。
数组模拟队列
如下示意图，MaxSize代表队列能存储的最大容量 front和rear分别代表队列的前后端下标，它们初始化都为1； 当向队列中添加数据时，front不会发生改变，rear会不断递增。 当从队列中取出数据时，rear不会发生改变，front会不断递增。 这样就可以达到一个“先进先出”的效果
代码实现
public class ArrayQueue {
/**
* 数组模拟队列
* rear：队列后置标志 （随着队列元素增加而增加） 初始化=-1
* front:队列前置标志（队列中头一个位置-1）（随着队列减少而增加）初始化=-1
* 构造
* 添加
* maxSize:队列能够存储的最大元素
* isMax（是否超出队列最大限制） = maxSize-1(因为数组索引从0开始)、
* isEmpty
* showQueue 遍历 队列
* showHead 返回队列头部
* getQueue
*/
private int rear;
private int front;
private int maxSize;
private int[] arr;
public ArrayQueue(int maxSize) {
this.rear = -1; //队列尾下表
this.front = -1; //队列头前一个位置的下标
this.maxSize = maxSize;
this.arr = new int[maxSize];
}
//队列是否为空
public boolean isEmpty(){
return rear == front;
}
//队列是否已满
public boolean isMax(){
return rear == maxSize-1;
}
//将元素存入队列中
public void addQueue(int num){
if(!isMax()){
rear++;
arr[rear] = num;
System.out.println("元素添加成功");
}else{
System.out.println("队列已满不能添加数据");
}
}
//取出队列数据
public int getQueue(){
if(isEmpty()){
System.out.println("队列中没有数据");
throw new RuntimeException("队列中没有数据");
}
front++;
return arr[front];
}
//查询队列
public void showQueue(){
for(int a:arr){
System.out.println(a);
}
}
//返回队列头部
public int getHeadQueue(){
if(isEmpty()){
System.out.println("队列中没有数据");
throw new RuntimeException("队列中没有数据");
}
return arr[front+1];
}
}测试
...
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(3);
char key = ' ';//用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出菜单
while(loop){
System.out.println("s：显示队列");
System.out.println("e：退出程序");
System.out.println("a：添加队列");
System.out.println("g：从队列中取值");
System.out.println("h：查看队列头部");
key = scanner.next().charAt(0);
switch(key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("please inout number");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
System.out.println("取出的数据是：" + arrayQueue.getQueue());
} catch (Exception e) {
String message = e.getMessage();
System.out.println(message);
}
break;
case 'h':
try {
System.out.println("队列头的数据是：" + arrayQueue.getHeadQueue());
} catch (Exception e) {
String message = e.getMessage();
System.out.println(message);
}
break;
case 'e':
scanner.close();
loop = false;
break;
}
}
System.out.println("程序退出");
}
...数组模拟环形队列
上述代码已经完成了一个最基本的队列，但是存在问题如下
目前数组只能使用一次，达不到复用效果，数组中被取出的空间不能被利用 解决办法 将这个数组使用算法改进成环形数组，就可以达到复用的效果，核心是取模（%）
思路分析
1.front变量的含义做调整：front指向队列的第一个元素（为了后面比较取模后的结果方便） 2.rear变量含义做调整：rear指向队列的最后一个元素的后一个位置（为了空出一个位置，方便运算） front和rear开始都为0；
即：front代表下次获取的位置，rear代表下次存入的位置。
由于我们要模拟一个环形队列，且front和rear都进行了调整，所以队列满的条件也发生了变化
3.当队列满时，条件是**(rear+1) % maxSize=front**
至于为什么会出现上面那个小算法，是因为我们要做一个环形队列 我们先从以下几点来说明 首先我们要实现一个环形队列，我们在向队列添加数据的时候，会使得rear不断增长，即使rear已经到达MaxSize的时候由于环形队列的特性rear还是会无限制的增长，很明显环形队列的MaxSize就那么大，rear不断增长肯定会使得我们不能一眼看出元素的真实位置，所以这里我们用了取模 (rear+1)%maxSize就可以得到元素在环形队列上的真实位置，得到这个真实位置很有用！
当我们得到元素的真实位置之后，就可以判断元素的真实位置是否与front相等，如果相等则说明队列已满即上面提到的公式
(rear+1) % maxSize=front验证 （rear+1）% maxSize=front
为了方便计算，我们将maxSize设置为4，front初始值是0
第一种情况(队列只存，没取过数据) 假设队列中已经入了3条数据，那么rear=2+1=3此时如果还要存入数据，我们要判断队列前面是否还有空间以便存入下一个数据，即( rear+1）% maxSize=front？？？ 如果取模后的结果等于front说明队列已满，反之则可以存入数据
(3+1) % 4 = 0 == front(0) // true可以看到取模后的结果=0，我们也没有取过数据，front是一直等于0的，这就代表队列已满
第二种情况（向队列中取过数据） 我们在第一种情况的基础之上，取出一个数据，如果取出一个数据那么会导致 front递增，此时的front就等于1 当前的rear还是等于3，此时在向队列存入数据，这个时候我们要判断队列前是否还有空间 ( rear+1）% maxSize=front？？？
(3+1) % 4 = 0 ==front(1) //false可以看到取模后的结果等于0，但是由于取过数据的原因导致的front变成了1， 0!=1即队列未满，可以存入数据。 如果这个存入数据的操作成功了，此时数组中的最后一个元素的下标应该是3，rear就变成了0。 为什么变成0因为到3的时候已经是数组的尽头了，只能往数组前面看看还有没有可以存数据的地方，这里就是0
这个时候在还没有取出数据的情况下，我们在向这个队列添加数据 首先会进行判断
(0+1) % 4 =1 ==front(1) //true可以看到队列已满 第三种情况（先取在添加） 如果此时在取一个数据那么front就会变成2，rear还是等于0，此时在向队列存入数据，首先会进行判断
(0+1) % 4 =1 ==front(2) //false可以看到队列没满，因此可以添加数据，如果这个添加数据的操作成功了，此时rear等于最后一个元素的位置的后一个位置即1，
（1+1） % 4 = 2 == front(2) //true可以看到当再次存入数据后队列又满了。 就这样依此类推就实现了一个环形队列
需要注意的是这个算法导致了队列牺牲了一个空间，作为rear的指向，队列实际的元素只能保存到倒数第二个
4.队列为空的条件是：rear==front 5.队列中有效数据的个数是：(rear+maxSize-front) % maxSize
数组模拟环形队列代码实现
class CircleArray{
private int maxSize; //数组最大容量
private int front; //队列头 初始=0
private int rear; //队列尾 初始=0 最后一个元素的后一个位置
private int[] arr; //存放数据
public CircleArray(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
}
//队列是否为空
public boolean isEmpty(){
return rear == front;
}
//队列是否已满
public boolean isMax(){
return (rear+1) % maxSize == front;
}
//将元素存入队列中
public void addQueue(int num){
if(isMax()){
System.out.println("队列已满，无法添加");
return;
}
arr[rear] = num;
//将rear后移 这里要考虑取模（环形队列）
rear = (rear+1) % maxSize;
}
//取出队列数据
public int getQueue(){
if(isEmpty()){
throw new RuntimeException("队列中没有数据");
}
int value = arr[front];
//front 后移
//不能直接使用 front++ 会造成数组越界
front = (front + 1) % maxSize;
return value;
}
//查询队列
public void showQueue(){
if(isEmpty()){
System.out.println("队列中没有数据");
return;
}
//从front 遍历，防止打印被取出的元素
for(int i = front; i < front + size() ; i++){
System.out.printf("arr[%d]=%d\n", i % maxSize,arr[i % maxSize]);
}
}
public int size(){
return (rear+maxSize-front) % maxSize;
}
//返回队列头部
public int getHeadQueue(){
if(isEmpty()){
throw new RuntimeException("队列中没有数据");
}
return arr[front];
}
}腾讯云开发者
