1. 什么是队列
先进先出
可以使用数组或者链表来实现
image.png
front 队列头，随着数据输出而改变
rear队列尾，随着数据输入而改变
2. 数组模拟队列
addQueue
- 将rear向后移动，rear + 1，当front == rear时队列为空
- 若rear小于maxSize - 1，则将数据存入rear所指向的元素位置，否则无法存入数据，rear = maxSize - 1为队列满
rear 是队列最后（含）
front是队列最前元素（不含）
package com.ds.queue;
public class ArrayQueue {
private int maxSize;
private int front;
private int rear;
private int[] arr; //数组用于存放数据，模拟队列
/***
* 构造器
* @param queueSize
*/
public ArrayQueue(int queueSize) {
maxSize = queueSize;
arr = new int[queueSize];
front = -1;
rear = -1;
}
/***
* 判满
* @return
*/
public boolean isFull() {
return rear == maxSize - 1;
}
/***
* 判空
* @return
*/
public boolean isEmpty() {
return front == rear;
}
/***
* 添加元素
* @param elem
*/
public void addElemToQueue(int elem) {
// 判断是否满
if (isFull()) {
System.out.println("队列满。");
return;
}
rear++;
arr[rear] = elem;
}
/***
* 取数据
* @return
*/
public int getElemFromQueue() {
// 判空
if (isEmpty()) {
// 这里不抛异常的话，不知道怎么处理return
throw new RuntimeException("队列空");
}
front++;
return arr[front];
}
/***
* 打印队列
*/
public void printQueue() {
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
/***
* 显示队列头数据
* @return
*/
public int getHeader() {
return arr[front + 1];
}
}
测试代码：
package com.ds.queue;
import java.util.Scanner;
public class Test {
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(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据");
System.out.println("g(get): 取出数据");
System.out.println("h(head): 查看队列头数据");
System.out.println("-------------------------");
key = scanner.next().charAt(0); // 接收第一个字符
switch (key) {
case 's':
arrayQueue.printQueue();
break;
case 'a':
System.out.println("输入一个数：");
int anInt = scanner.nextInt();
arrayQueue.addElemToQueue(anInt);
break;
case 'g':
try {
int res = arrayQueue.getElemFromQueue();
System.out.printf("取出的数是：%d\t", res);
} catch (Exception e) {
System.out.println(e);
}
break;
case 'h':
try {
int header = arrayQueue.getHeader();
System.out.printf("队列头是： %d\t", header);
} catch (Exception e) {
System.out.println(e);
}
break;
default:
break;
}
}
}
}
这样写并不合理，因为即使取出数据，实际上数组的空间还是被占用的，优化成环形队列可以解决空间浪费的问题。
