👨🏻🎓博主介绍：大家好，我是芝士味的椒盐，一名在校大学生，热爱分享知识，很高兴在这里认识大家🌟
🌈擅长领域：Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话，🍭关注+👍🏻点赞+🗣评论+📦收藏，相应的有空了我也会回访，互助！！！
🤝另本人水平有限，旨在创作简单易懂的文章，在文章描述时如有错，恳请各位大佬指正，在此感谢！！！
@[TOC]
什么是队列
- 队列是一个有序的列表，可以用数组或是链表实现
队列遵循先入先出的原则。即将：先存入队列的数据要先取出，后存入的要后取出
- 若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
- 队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变
- 将尾指针往后移：rear+1 , 当front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
- rear 是队列最后[含]
- front 是队列最前元素[不含]
普通队列代码实现
数组模拟队列案例：
package icu.lookyousmileface.arrayqueue; import java.util.Scanner; /** * @author 芝士味的椒盐 * @title: ArrayQueueDemo * @projectName DataStructure_Algorithm * @date 2020/12/14 15:56 */ public class ArrayQueueDemo { public static void main(String[] args) { // ArrayQueue arrayQueue = new ArrayQueue(4); //// System.out.println(arrayQueue.getQueue()); // System.out.println(arrayQueue.isEmpty()); // arrayQueue.addQueue(5); // arrayQueue.addQueue(4); // arrayQueue.addQueue(3); // System.out.println(arrayQueue.isFull()); // arrayQueue.addQueue(2); // arrayQueue.showQueue(); // System.out.println(arrayQueue.isEmpty()); // System.out.println(arrayQueue.isFull()); // System.out.println(arrayQueue.getQueue()); // System.out.println(arrayQueue.getFirst()); // System.out.println(arrayQueue.getLast()); ArrayQueue arrayQueue = new ArrayQueue(4); char key = ' '; Scanner scanner = new Scanner(System.in); boolean loop = true, status = true; while (loop && status) { System.out.println("注意：使用add的是时候，添加的只能是数字，比如：先输入add回车，在输入要存的数字1024回车"); System.out.println("show(s):查看所有的队列元素"); System.out.println("add(a): 添加元素"); System.out.println("get(g)：取出数据"); System.out.println("head(h)：获取头部元素"); System.out.println("exit(e)：退出程序"); key = scanner.next().charAt(0); switch (key) { case 's': arrayQueue.showQueue(); break; case 'a': int value = new Scanner(System.in).nextInt(); arrayQueue.addQueue(value); break; case 'g': try { int queue = arrayQueue.getQueue(); System.out.println("取出数据" + queue); } catch (Exception e) { e.printStackTrace(); } break; case 'h': try { int first = arrayQueue.getFirst(); System.out.println("你取出了头部元素" + first); } catch (Exception e) { e.printStackTrace(); } break; case 'e': status = false; break; default: break; } } } } /** * @author 芝士味的椒盐 * @title: ArrayQueue * @date 2020/12/14 16:00 * 模拟队列 */ class ArrayQueue { private int maxSize; private int front; private int rear; private int[] arr; public ArrayQueue(int maxSize) { this.maxSize = maxSize; this.front = -1; this.rear = -1; this.arr = new int[maxSize]; } public boolean isEmpty() { return this.rear == this.front; } public boolean isFull() { return this.rear == this.maxSize - 1; } public void addQueue(int num) { if (isFull()) { System.out.println("Queue is Full！"); return; } this.arr[++this.rear] = num; } public int getQueue() { if (isEmpty()) { //抛出异常相当return的效果，后面代码无法执行 throw new RuntimeException("Queue is Empty not get value!"); } return this.arr[++this.front]; } public void showQueue() { if (isEmpty()) { System.out.println("Queue is Empty, not showQueue!"); return; } for (int i = 0; i < this.arr.length; i++) { System.out.printf("arr[%d] = %d\n", i, arr[i]); } } public int getFirst() { if (isEmpty()) { throw new RuntimeException("Queue is Empty,not getFirst element!"); } return this.arr[++this.front]; } public int getLast() { if (isEmpty()) { throw new RuntimeException("Queue is Empty,not getLast element!"); } return this.arr[this.arr.length - 1]; } }- 代码缺点：底层实现的数组无法重用，尾索引处于满的状态
什么是环形队列
- 环形数组模拟队列：
可以弥补上述队列尾索引处于满存在队列上限问题，这样队列就可以将队列无限次使用。
环形队列代码实现
package icu.lookyousmileface.circlearrayqueue;
import java.util.Scanner;
/**
* @author 芝士味的椒盐
* @title: CircleArrayQueueDemo
* @projectName DataStructure_Algorithm
* @date 2020/12/14 22:23
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);
Scanner scanner = new Scanner(System.in);
char key = ' ';
boolean loop = true;
boolean status = true;
while (loop&&status) {
System.out.println("注意：使用add的是时候，添加的只能是数字，比如：先输入add回车，在输入要存的数字1024回车");
System.out.println("show(s):查看所有的队列元素");
System.out.println("add(a): 添加元素");
System.out.println("get(g)：取出数据");
System.out.println("head(h)：获取头部元素");
System.out.println("exit(e)：退出程序");
key = scanner.next().charAt(0);
switch (key) {
case 's':
circleArrayQueue.showQueue();
break;
case 'a':
try{
int value = scanner.nextInt();
circleArrayQueue.addQueue(value);
}catch (Exception e){
System.out.println("队列已满，无法加入新元素");
}
break;
case 'g':
try {
int queue = circleArrayQueue.getQueue();
System.out.println("取出元素 :" + queue);
} catch (Exception e) {
System.out.println("无法取，队列为空");
}
break;
case 'h':
try {
int head = circleArrayQueue.getHead();
System.out.println("头部元素 :" + head);
}catch (Exception e){
System.out.println("无法获取，头部为Null");
}
break;
case 'e':
status = false;
break;
default:
break;
}
}
}
}
/**
* @author 芝士味的椒盐
* @title: CircleArrayQueue
* @date 2020/12/14 22:26
* 环形队列
*/
class CircleArrayQueue {
private int maxSize;
private int front;
private int rear;
private int[] arr;
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[this.maxSize];
}
public boolean isFull() {
return (this.rear + 1) % maxSize == front;
}
public boolean isEmpty() {
return this.rear == this.front;
}
public void addQueue(int num) {
if (isFull()) {
throw new RuntimeException("Queue is Full!");
}
this.arr[this.rear] = num;
//将rear后移，考虑取模
rear = (rear + 1) % maxSize;
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is Empty!");
}
// 这里需要分析出 front是指向队列的第一个元素
// 1. 先把 front 对应的值保留到一个临时变量
// 2. 将 front 后移, 考虑取模
// 3. 将临时保存的变量返回
int value = this.arr[this.front];
front = (front + 1) % maxSize;
return value;
}
/**
* @author 芝士味的椒盐
* @title: size
* @date 2020/12/14 22:48
* 环形链表有效个数
*/
public int size() {
return (this.rear + this.maxSize - this.front) % maxSize;
}
public void showQueue() {
if (isEmpty()) {
throw new RuntimeException("Queue is Empty!");
}
for (int i = this.front; i < this.front + size(); i++) {
System.out.printf("arr[%d] = %d\n", i % maxSize, this.arr[i % maxSize]);
}
}
public int getHead() {
if (isEmpty()) {
throw new RuntimeException("Queue is Empty!");
}
return arr[this.front];
}
}
思路如下:
1. front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
front 的初始值 = 0
2. rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
rear 的初始值 = 0
3. 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
4. 对队列为空的条件， rear == front 空
5. 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0 