数组模拟队列
队列数据结构的特点是先进先出，后进后出。
使用数组和链表可以模拟队列的实现。
这里用Java的数组来实现一个队列。
- 创建Java类，包含成员变量maxSize来表示队列的最大容量。front表示队列前端的索引下标，rear表示队列后端的索引下标。
arr数组表示队列存储的内容。
/**
* 队列最大长度
*/
private int maxSize;
/**
* 队列头
*/
private int front;
/**
* 队列尾
*/
private int rear;
/**
* 数组
*/
private int[] arr;
- 构造函数初始化队列。初始化时front值为-1，rear值为-1。
/**
* 构造函数
*/
public ArrayQueue(int arrMaxSize) {
this.maxSize = arrMaxSize;
int[] arr = new int[maxSize];
front = -1;
rear = -1;
}
- 编写方法，判断队列是否为满，当 rear = maxSize - 1 时满。
/**
* 判断队列是否满,rear 等于 maxsize - 1时满
*/
public Boolean isFull() {
return rear == maxSize - 1;
}
- 编写方法，判断队列是否为空，当 rear = front 时为空。
/**
* 判断队列是否为空,rear 等于 front时为空
*/
public Boolean isEmpty() {
return rear == front;
}
- 编写方法，将数据添加到队列，添加数据的时候，队列头是不会动的，而队尾rear的位置往后移动一位。
/**
* 将数据添加到队列
*/
public void add(int num) {
//判断队列是否为满，为满给出提示
if (isFull()) {
System.out.println("队列满，不能加入到队列");
}
//将队尾++
rear++;
arr[rear] = num;
}
- 编写方法，从队列中取数据。取数据的时候从队列头取，所以要将队头front的位置往后移动一位。
/**
* 从队列中取数据
*/
public int get() {
//判断队列是否为空，为空抛出异常
if (isEmpty()) {
throw new RuntimeException("队列为空，无数据可取");
}
front++;
return arr[front];
}
- 编写方法，遍历数组。
/**
* 遍历数组
*/
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列空的，没有数据。。。。");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d\n", i, arr[i]);
}
}
- 编写方法，显示队列头的信息。队列头front由于指向的是队列的前一个位置的信息，所以front应该+1
/**
* 显示队列头的信息
*/
public int showHead() {
//判断是否为空
if (isEmpty()) {
System.out.println("队列为空，无数据");
}
return arr[front + 1];
}
- 编写测试方法，来模拟队列的添加和取出数据的过程。
public static void main(String[] args) {
//创建一个容量为3的数组
ArrayQueue queue = new ArrayQueue(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.showQueue();
break;
case 'e':
System.out.println("程序退出~");
loop = false;
scanner.close();
break;
case 'a':
try {
System.out.println("请输入要添加的数字：");
int num = scanner.nextInt();
queue.add(num);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
int i = queue.get();
System.out.printf("从队列取出的数据是：%d", i);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.showHead();
System.out.printf("队列头数据是：%d", head);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
}
}
}
刚开始输入s显示队列，会显示队列为空。
然后添加三个数字10，20，30到队列。
显示队列中的内容：
输入g，从队列中取出数据，会从头开始取，第一次会取出10，然后输入h查看队列头的数据，会显示为20：
依次取出20和30，最后会显示队列为空，无数据：
这个时候,由于队列加入了3个数据，rear的值已经由-1变成了2，再回顾下队列是否满的判断，rear的值为maxsize-1的时候队列满。所以这个队列已经无法再添加任何数据了。
数组模拟环形队列
这个时候可以改造下代码来实现环形队列。
这里修改下rear和front的定义，rear表示的是队尾的后面一个位置，初始值为0，表示占据一个未使用的位置，front表示的是对头的位置，初始值也为0。
这里通过推断得出：队列满的判断应该是 (rear + 1) % maxSize = front; 而队列的个数应该是 （rear + maxSize - front）% maxSize。
- 改造下构造方法，这里由于int初始值默认为0，所以省略掉了 int rear = 0 ; int front = 0 ;
public CircleArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
- 改造数组是否为满方法，当 （rear + 1）% maxSize == front 时为满。
/**
* 判断队列是否满, (rear + 1) % maxSize == front 时满
*/
public Boolean isFull() {
return (rear + 1) % maxSize == front;
}
- 改造添加数据到队列方法。将队列rear位置的值赋值为num，由于rear值有可能会重新回到起始位置，所以需要将值+1，然后对maxSize取模。
/**
* 将数据添加到队列
*/
public void add(int num) {
//判断队列是否为满，为满给出提示
if (isFull()) {
System.out.println("队列满，不能加入到队列。。");
return;
}
//将队尾++
arr[rear] = num;
rear = (rear + 1) % maxSize;
}
- 改造从队列取出数据的方法， 记录队列front位置的值，然后将(front+1)%maxSize，这么做和rear同理，为了达到位置循环使用的目的。然后将记录的值返回。
/**
* 将数据添加到队列
*/
public void add(int num) {
//判断队列是否为满，为满给出提示
if (isFull()) {
System.out.println("队列满，不能加入到队列。。");
return;
}
//将队尾++
arr[rear] = num;
rear = (rear + 1) % maxSize;
}
- 改造遍历数组的方法，循环是从front开始，循环的次数是队列的有效个数次。所以首先创建获取队列个数的方法。
/**
* 获取数组中有效元素的个数
*
* @return
*/
private int size() {
return (rear + maxSize - front) % maxSize;
}
- 遍历数组。为了保证不会发生索引越界，（i的值有可能大于数组的个数），所以要对数组取模。
/**
* 遍历数组
*/
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列空的，没有数据。。。。");
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);
}
}
- 编写测试方法开始测试。
public static void main(String[] args) {
//创建一个容量为3的数组
CircleArrayQueue queue = new CircleArrayQueue(4);
//接受用户输入
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.showQueue();
break;
case 'e':
System.out.println("程序退出~");
loop = false;
scanner.close();
break;
case 'a':
try {
System.out.println("请输入要添加的数字：");
int num = scanner.nextInt();
queue.add(num);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
int i = queue.get();
System.out.printf("从队列取出的数据是：%d", i);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.showHead();
System.out.printf("队列头数据是：%d", head);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
}
首先向队列添加10，20，30三个数字。
然后再从队列取三次数据。
这个时候，再从数据添加数据，就可以添加了。
这样就实现了一个环形的队列。