JAVA数据结构- 环形数组模拟队列
程序员文章站
2022-06-06 20:56:29
...
1.使用普通数组时,定一个m长度的数组
0 | 1 | 2 | 3 |
把数据存入数组满时, 再取出时, 就不能再向这个数组添加数据 , 因为该数组最后一个位置
2.环形数组
定义第一个数据也就是第一个先添加的数据的位置 first 初始值为0
定义最后一个添加进来的数据 的后一个位置为 last 初始值为0 所以实际最大容量为 max-1
3.添加数据
4.取出数据
5.查看所有数据
完整代码
package dataStructure.环形队列;
import java.util.Scanner;
public class CircleArrayQueue {
public static void main(String[] args) {
//测试一把
System.out.println("测试数组模拟环形队列的案例~~~");
// 创建一个环形队列
CircleArray queue = new CircleArray(4); //说明设置 4, 其队列的有效数据最大是 3
char key = ' '; // 接收用户输入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
key = scanner.next().charAt(0);// 接收一个字符
switch (key) {
case 's':
queue.show();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g': // 取出数据
try {
int res = queue.getOne();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h': // 查看队列头的数据
try {
queue.showHead();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray {
private int maxSize; //定义数组的最大容量,实际最大容量为maxSize-1 因为 last指向最后一个数据的后一个
private int last; //定义数组最后一个数据的 后一个数据的位置 初始值为0
private int first; //定义数组的第一个数据的位置 初始值为0
private int arr[]; //存放数据的数组
public CircleArray(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
}
/**
* 判断数组是否为空
*
* @return
*/
public Boolean isEmpty() {
return last == first;
}
/**
* 判断数组是否满,(last+1)%maxSize就是将指针移到开头,因为是环形的所以取模
*
* @return
*/
public Boolean isFull() {
return (last + 1) % maxSize == first;
}
/**
* 添加数据,添加的数据在队未
* @param num
*/
public void add(int num) {
if (isFull()) {
System.out.println("队列满,不能添加~~");
return;
}
arr[last] = num; //因为last就指向最后一个数据的后一个,所以直接是
last = (last + 1) % maxSize; //后移一位,考虑环形
}
/**
* 获得一个数据,获得的数据是队首
*
* @return
*/
public int getOne() {
if (isEmpty()) {
throw new RuntimeException("队列空,不能取~~");
}
int value = arr[first];
first = (first + 1) % maxSize; //后移一位,考虑环形
return value;
}
/**
* 查看所有数据
*/
public void show() {
int length = (last - first + maxSize) % maxSize; //先得到当前数据个数
//从第一个数开始遍历就是first
for (int i = first; i < first + length; i++) {
System.out.printf("array[%d]=%d\n", i, arr[i]);
}
}
public void showHead() {
if (isEmpty()) {
throw new RuntimeException("队列空,不能查看~~");
}
System.out.printf("队列头的数据是:%d\n", arr[first]);
}
}
下一篇: 数据结构之循环队列