数据结构与算法-队列

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

Java高级系列文章前言

本文章涉及到数据结构与算法的知识该知识属于Java高级阶段通常为学习的二阶段本系列文章涉及到的内容如下橙色框选内容
在这里插入图片描述
本文章核心是教学视频所以属于个人笔记非商用。

文章结构

标识

本系列文章中记录的数据结构与算法都会多多少少用到一些Java的API这些API只会一笔带过主要还是看逻辑思路。

大标题
	小标题
		文本内容和图片内容... 70%/30%
			图片说明加重
				逻辑思路和次要说明
			文本说明普通文本
				主要说明和补充

内容结构

大标题
	介绍
	英文单词关键字陈列(有时会省略)
		代码块...
	思路引入
	思路解析
	源码
		代码展示
		图文说明

队列

介绍

如果只是数组实现一个队列那么这个队列其实是一次性的当你全部取出队列数据后是无法再添加新数据的想要解决这个问题就需要使用环形队列环形队列会涉及到一些算法下个文章就是环形队列的说明和演示。

英文单词关键字陈列

书写习惯XxxYyyZzzJava类驼峰语法
格式英文单词 -> 中文翻译 -> 空耳个人习惯

Queue -> 队列 -> Q
front -> 前面/队列头 -> 佛让它
rear -> 后面/队列尾 -> 睿啊

思路引入

我们现实生活中出处都存在队列的数据结构比如说我们去医院挂号、购买东西、超市结算等这些事情可能会需要排队排队则是先进先出队列是一个有序列表如果用数组实现则称为顺序存储链表实现则是链式存储队列遵循先进先出原则队列添加数据时在队列尾添加取出数据时在队列头取出。
本次我们使用数组来实现队列也就是一个顺序存储。

思路解析

我们创建一个类该类是ArrayQueue本类有4个成员属性

int maxSize该属性表示队列的最大容量
int front该属性表示队列头队列头指针
int rear该属性表示队列尾队列尾指针
int []elementData该数组是该类底层存储数据的数组
我们根据这4个成员变量去写出队列类的必备方法本次队列类的方法有
构造方法-ArrayQueue(int size)该方法用于初始化底层数组将传入的size指定为数组的初始化大小并且让front和rear等于-1当第一次添加数据时rear++将数据保存在索引0上front不变当取出数据时因为front是指向头数据的前一个位置所以让front后移一次front++就指向了队列头数据。
成员方法-boolean isFull()该方法判断队列是否已满判断条件为队列尾是否等于最大容量的值但是因为数组索引是从0开始的所以最大容量应该是maxSize-1。
成员方法-boolean isEmpty()该方法判断队列是否为空判断条件为队列头和队列尾是否在同一个位置该情况只有队列没有数据时才会发生因为两个值默认都是-1。
成员方法-void addQueue(int n)该方法将会添加一个数到队列中n是要添加的数据该方法会判断队列是否是满的不为满就让队列尾自增1然后添加到数组中索引为队列尾。
成员方法-int getQueue()该方法表示取出队列数据也就是出队列该方法首先判断队列是否为空不为空则让队列头后移一次自增1然后直接return处于队列头索引的数据该操作会让front+1此时再次取出队列头数据就发生了变化。
成员方法-void showQueue()该方法就是遍历数组输出数组里所有的元素方法先判断了是否为空不为空就遍历输出。
成员方法-int headQueue()该方法是显示队列头数据注意是显示不是取出该方法和出队列方法的区别就是retrun的不是front++而是直接front+1的结果而不是执行front++再取出也就是说执行了该方法后front的值并没有改变只是用front的值作为表达式的值来计算而已。

源码

代码展示

主方法的类测试后面不会有详细的讲解看代码的注释即可本质上就是while循环+scanner和switch语句等组成的简单流程控制

package Queue;


import java.util.Scanner;

//使用数组来模拟队列
public class QueueArrayDemo {
    public static void main(String[] args) {
        //测试
        //创建一个队列
        QueueArray queueArray = new ArrayQueue(3);//队列最大值为3也就是最大索引为2
        char key = ' ';//接收用户输入
        Scanner sc = 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 = sc.next().charAt(0);//接收接收一个字符
            switch (key){
                case 's'://显示数据
                    queueArray.showQueue();
                    break;
                case 'a'://添加数据
                    System.out.println("请输入一个数字");
                    int value = sc.nextInt();
                    queueArray.addQueue(value);
                    break;
                case 'g'://取出数据
                    try{
                        int res = queueArray.getQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h'://查看队列头数据
                    try{
                        int res = queueArray.headQueue();
                        System.out.printf("队列头的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    sc.close();
                    loop = false;//将循环标记变量设置为假假代表退出
                    System.out.println("程序已退出");
                    break;
                default:
                    break;
            }
        }
    }
}
//使用数组模拟队列-编写一个ArrayQueue类
class QueueArray{
    private int maxSize;//表示数组的最大容量
    private int front;//队列头 指向队列头的指针
    private int rear;//队列尾 指向队列尾的指针
    private int[]elementData;//实际存放数据的底层数据参考ArrayList底层的elementData
    //创建队列的构造器
    public QueueArray(int size){
        maxSize = size;
        elementData = new int[maxSize];
        front = -1;//指向队列头部的前一个位置 初始化为-1
        rear = -1;//指向队列尾部的具体位置 初始化为-1
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize -1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;//只有没有数据的时候前端和后端才会相等
    }
    //添加数据到队列
    public void addQueue(int n){//n表示添加的数据也可以理解为一个Object
        //判断队列是否满
        if(isFull()){
            System.out.println("队列满不能加入数据...");
            return;
        }
        rear++;//让rear后移第一次添加数据rear是-1后移一次则是0那么此时第一次添加的数据则在数组的0索引位置
        elementData[rear] = n;//elementData[++rear] = n

    }
    //获取队列的数据出队列
    public int getQueue(){
        //判断队列是否空
        if(isEmpty()){
            //通过抛出异常来处理
            throw new RuntimeException("队列为空");
            //throw本身就相等于返回所以不需要写return关键字以及和其他代码
        }
        front++;//front后移 front的含义是头数据的前面所以想要取到第一个数据就让front后移一次即可
        return elementData[front];
    }
    //显示队列的所有数据
    public void showQueue(){
        //遍历elementData
        if(isEmpty()){
            System.out.println("队列为空");
            return;
        }
        int itemIndex = 0;
        for (int item:elementData) {
            System.out.printf("arr[%d]=%d\n",itemIndex++,item);
        }
    }
    //显示队列的头数据注意不是取出数据
    public int headQueue(){
        //判断
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return elementData[front+1];
    }
}