文章目录
定义
定义:队列,又称为伫列(queue),是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
数组队列
package com.coderzpw.数据结构.队列相关;
import com.sun.org.apache.xpath.internal.operations.Bool;
import java.util.Scanner;
public class 环形数组队列 {
public static void main(String[] args) {
// 测试
System.out.println("测试环形数组队列的案例----");
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4); //实际上只能放入3个数据,因为我们约定要空一个位置
char key = ' '; // 接收用户输入
Scanner scanner = new Scanner(System.in);
Boolean loop = true;
while (loop) {
// 输出菜单
System.out.println("s(show):显示队列");
System.out.println("e(show):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("p(pull):取出队列头数据");
System.out.println("g(get):显示队列头数据");
key = scanner.next().charAt(0); // 接收用户输入的字符
switch (key) {
case 's':
circleArrayQueue.showQueue();
break;
case 'a':
System.out.println("请输入一个数");
int value = scanner.nextInt();
circleArrayQueue.addQueue(value);
break;
case 'p':
try {
int res = circleArrayQueue.pullQueue();
System.out.println("取出的数据是:"+res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'g':
try {
int res = circleArrayQueue.getHeadQueue();
System.out.println("队列头的数据为:"+res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
default:
break;
}
}
System.out.println("程序退出!!");
}
}
class CircleArrayQueue {
private int[] arr; // 存放数据的数组
// front 指向队列的第一个元素arr[front],front的初始值 = 0
private int front; // 队列头
// rear 指向队列的最后一个元素的后一个位置, 也就是说留一个空位置 ,这样做是为了区分 队列空和满的情况。 初始值仍然为0
private int rear;
// maxSize 表示数组的最大容量
private int maxSize;
/**
* 构造方法
* @param maxSize
*/
public CircleArrayQueue(int maxSize) {
this.front = 0;
this.rear = 0;
this.maxSize = maxSize;
this.arr = new int[maxSize];
}
/**
* 判断队列是否已满
*/
public Boolean isFull() {
return (rear+1) % maxSize == front; // 这里因为队尾有个位置是空, 因此需要rear+1
}
/**
* 判断队列是否为空
*/
public Boolean isEmpty() {
return rear == front;
}
/**
* @Description: 添加元素
* @author: coderzpw
* @date: 2021/8/1 17:57
* @param n:
* @Return: void
*/
public void addQueue(int n) {
// 判断队列是否满
if (isFull()){
System.out.println("队列已满,不能添加数据");
return;
}
// 直接添加数据
arr[rear] = n;
// 将rear后移,这里必须考虑取模
rear = (rear+1)%maxSize;
}
/**
* @Description: 取出数据
* @author: coderzpw
* @date: 2021/8/1 17:56
* @Return: int
*/
public int pullQueue() {
// 判断队列是否为空
if (isEmpty()) {
// 这里不做返回,不返回任何值。直接抛出异常
throw new RuntimeException("队列为空,不能取数据");
}
int tempValue = arr[front]; // 先取出这个值
front = (front+1)%maxSize; // 再让front++取模
return tempValue;
}
/**
* @Description: 显示头元素,注意不是取出数据
* @author: coderzpw
* @date: 2021/8/1 17:53
* @Return:
*/
public int getHeadQueue() {
if (isEmpty()) {
// 这里不做返回,不返回任何值。直接抛出异常
throw new RuntimeException("队列为空,不能获取数据");
}
return arr[front];
}
/**
* @Description: 求出当前队列有效的数据长度
* @author: coderzpw
* @date: 2021/8/1 17:45
* @Return:
*/
public int size() {
return (rear-front+maxSize)%maxSize; // 这里认真思考
}
/**
* @Description: 显示队列的所有数据
* @author: coderzpw
* @date: 2021/8/1 17:40
* @Return:
*/
public void showQueue() {
// 遍历
if(isEmpty()) {
System.out.println("队列为空,没有数据---");
}
for (int i=0; i<front+size(); i++) { // 从front开始,向后去除size()长度的数据
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
}