1、队列介绍
- 队列是一个有序列表，可以用数组或链表来实现，数组实现的叫做顺序队列，链表实现的叫做链式队列
- 队列遵循先进先出的原则
- enqueue：入队，队列尾部存入一个元素
- dequeue：出队，队列头部取出一个元素
2、数组模拟队列
2.1 数组模拟队列思路
队列本身是有序列表，我们使用数组结构来存储队列的数据
队列有一个最大容量 maxSize，需要有两个变量 head 和 tail 分别记录队列前后端的下标，head 随着数据输出改变，tail 随着数据输入改变。
将尾指针往后移，tail + 1，当 head == tail，队列为空
如果尾指针 tail 小于队列的最大下标 maxSize - 1，将数据存放到 tail 所指的数组元素中，否则无法存入数据。tail = maxSize - 1 时，队列满
2.2 数组模拟队列代码实现
package com.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(3);
Scanner scanner = new Scanner(System.in);
boolean quit = true;
String key = "";
System.out.println("add【添加数据】");
System.out.println("get【出队列】");
System.out.println("show【获取所有数据】");
System.out.println("tail【获取尾部数据】");
System.out.println("head【获取头部数据】");
System.out.println("exit【退出】");
while (quit){
key = scanner.next();
switch (key){
case "add" :
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case "get":
try {
System.out.println(arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "show" :
arrayQueue.showQueue();
break;
case "tail" :
try {
System.out.println(arrayQueue.tailQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "head" :
try {
System.out.println(arrayQueue.headQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit" :
quit = false;
break;
default:
break;
}
}
}
}
class ArrayQueue {
private int maxSize; // 数组最大容量
private int head; // 指向队列头部（不包含），队列头的前一个位置
private int tail; // 指向队列尾部（包含），队列尾的最后一个数据位置
private int[] array; // 存放数据，模拟队列
// 队列构造方法
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
array = new int[maxSize];
head = -1;
tail = -1;
}
// 判断队列是否已满
public boolean isFull() {
return tail == maxSize - 1;
}
// 判断队列是否为空
public boolean isEmpty() {
return tail == head;
}
// 添加数据到队列中，入队列
public void addQueue(int n) {
// 判断队列是否已满
if (isFull()) {
System.out.println("队列已满，无法加入数据");
return;
}
// tail 后移一位位置添加数据 n
tail++;
array[tail] = n;
}
// 获取队列数据，出队列
public int getQueue() {
// 判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出数据");
}
// 将 head 后移一位，取出数据
head++;
return array[head];
}
// 显示所有的数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，没有数据");
return;
}
for (int i = 0; i < array.length; i++) {
System.out.printf("arr[%d] = %d\n", i, array[i]);
}
}
// 显示队列头部数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，头部没有数据");
}
return array[head+1];
}
// 显示队列尾部数据
public int tailQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，尾部没有数据");
}
return array[tail];
}
}
3、数组模拟环形队列
3.1 数组模拟环形队列思路
head 原来指向第一个元素的前一个元素，现在指向第一个元素，array[head] 就是队列的第一个元素，tail 和 head 的初始值为 0
tail 原来指向队列的最后一个位置，现在指向队列最后一个元素的后一个位置，空出一个空间作为约定空间
当队列满时，
(tail + 1) % maxSize == head：最后元素后一个位置 +1 与 数组大小取模，结果等于 head 的位置队列满当队列空时，
tail == head队列中有效数据的个数为：
(tail + maxSize - head) % maxSize
3.2 数组模拟环形队列代码实现
package com.queue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
// 最大值为 4，可用为 3，一个作为约定空间，不占用
CircleArrayQueue arrayQueue = new CircleArrayQueue(4);
Scanner scanner = new Scanner(System.in);
boolean quit = true;
String key = "";
System.out.println("add【添加数据】");
System.out.println("get【出队列】");
System.out.println("show【获取所有数据】");
System.out.println("tail【获取尾部数据】");
System.out.println("head【获取头部数据】");
System.out.println("exit【退出】");
while (quit){
key = scanner.next();
switch (key){
case "add" :
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case "get":
try {
System.out.println(arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "show" :
arrayQueue.showQueue();
break;
case "tail" :
try {
System.out.println(arrayQueue.tailQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "head" :
try {
System.out.println(arrayQueue.headQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit" :
quit = false;
break;
default:
break;
}
}
}
}
class CircleArrayQueue {
private int maxSize; // 数组最大容量
private int head; // 指向队列第一个元素
private int tail; // 指向队列尾部最后数据后一个位置
private int[] array; // 存放数据，模拟队列
// 队列构造方法
public CircleArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
array = new int[maxSize];
}
// 判断队列是否已满
public boolean isFull() {
return (tail + 1) % maxSize == head;
}
// 判断队列是否为空
public boolean isEmpty() {
return tail == head;
}
// 添加数据到队列中，入队列
public void addQueue(int n) {
// 判断队列是否已满
if (isFull()) {
System.out.println("队列已满，无法加入数据");
return;
}
// tail 位置添加数据 n
array[tail] = n;
// tail 后移，考虑取模
tail = (tail + 1) % maxSize;
}
// 获取队列数据，出队列
public int getQueue() {
// 判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出数据");
}
// head 指向队列的第一个元素
int value = array[head];
head = (head + 1) % maxSize;
return value;
}
// 显示所有的数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，没有数据");
return;
}
for (int i = head; i < head + size(); i++) {
System.out.printf("arr[%d] = %d\n", i % maxSize, array[i % maxSize]);
}
}
// 获取队列有效数据的个数
public int size(){
return (tail + maxSize - head) % maxSize;
}
// 显示队列头部数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，头部没有数据");
}
return array[head];
}
// 显示队列尾部数据
public int tailQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，尾部没有数据");
}
return array[tail-1];
}
}