1、队列  是一个有序列表   可以用 数组或是  链表来实现

2、遵循先入先出的原则  即 先存入 队列的数据  要先去除  后存入的要后取出

 队列 本身  是有序列表  若使用数组的结构来存储队列 的数据  则队列数组的生命  其中maxSize是 队列的最大容量

因为  队列的输出  输入  是分别从 前后端来来处理因此需要两个变量front 及rear分别标记 队列前后端的下标  front会随数据输出而改变  而rear 则是随着输入而改变

addqueue  需要两个不走  

将尾指针 后移  rear-1  当front == rear  【空】

若 尾指针  rear小于 队列的最大下标  maxSize -1 则将  数据存入rear所指的数组 元素中 否则  无法存入数据 rear  == maxSize-1

import java.util.Scanner;

public class ArrayQueDemo {
    public static void main(String[] args) {
        //测试一把
        //创建一个队列
       ArrayQueue arrayQueue = new ArrayQueue(3);
       char key = ' ';//接受用户输入数据
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        if (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):从队列头的数据");
            key = scanner.next().charAt(0);//接收第一个字符
            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try{
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());

                    }
                    break;
                case 'h': //查看队列的头部是数据
                  try{
                      int res = arrayQueue.headQueue();
                      System.out.printf("头部数据是%d\n",res);
                  }catch (Exception e){
                      System.out.println(e.getMessage());
                  }
                  break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;

            }
        }
    }
}
//使用数组模拟队列  编写一个arrayQueue类
class ArrayQueue{
    private int maxSize; //表示数组的最大容量
    private int front;   //队列头部
    private int rear;  //队列尾部
    private int[] arr; //该数据用于存放数据  模拟队列

    //创建队列构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; //只想队列头部，分析出front 是指向 队列头的前一个位置
        rear = -1; //指向队列尾  指向队列的尾部  的具体数据  即 就是队列最后一个数据
    }
    //判断队列是否满
    public boolean isFull(){
        return  rear == maxSize -1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }
    //添加数据到队列
    public void addQueue(int n){
        //判断数据是否满
        if (isFull()){
            System.out.println("队列满，不能加入数据~");
            return;
        }
        rear++;   //让rear后移
        arr[rear] = n;
    }
    //获取数据的队列   出队列
    public int getQueue(){

        //首先取   数据首先要判断数据是否为空
        if(isEmpty()){
           //通过抛出异常来进行处理
            throw  new RuntimeException("队列空  不能取数据");
        }
       front++; //front后移
        return arr[front];
    }
    //显示队列的所有数据
    public void showQueue(){
        //变量数列
        if (isEmpty()){
            System.out.println("队列空的  没有数据");
            return;
        }
        for (int i = 0; i < arr.length ; i++) {
            System.out.printf("arr[%d]= %d\n",i, arr[i]);
        }
    }
//    显示队列头数据  注意不是取数据
    public int headQueue(){
//        判断
        if (isEmpty()){
            throw new RuntimeException("队列没有空的 没有数据");
        }
        return arr[front+1];

    }
}

3.2  队列的使用场景  

比如-排队

1）  队列是一个有序列表 可以用数组或是 链表来实现

2）循环先入先出的原则    即  先存入  队列的数据  要先取出  后存入的要后取出

问题分析并优化

1）目前数组 使用  一次就不能用  没有 达到  复用的效果

2）将  这个数组 使用  算法   改进 一个 环形 队列    取模 ：%

使用数组  模拟  环形模拟

思路如下：

1、front 变量 的含义  做一个 调整  ：front 就指向  队列的第一个元素   也就是说 arr[front] 就是队列第一个元素

2、rear变量的含义做一个调整： rear指向队列的最后一个元素的后一个位置   因为希望空出一个空间做一个 约定

3、当队列满时条件是（rear +1）%maxSize  = front【满】

4、对队列为空条件   rear == front 空

5、当 我们 这分析 分析 队列中 有效的数据的个数 ( rear+maxSize-front)% maxSize //rear =1 font = 0

6、我们就可以在 原来的队列已修改得到，一个环形队列

链表 介绍

链表是有序列表  但是它  内存 中是存储 如下

小结：

1）链表 是以节点方式来存储

2）每个节点包含  data域  next 域  指向下一个节点

3）如图：发现链表的各个节点   一定是连续存储

4）链表分带头节点的链表和没有头节点的链表  根据实际需求来确定

单链表  的创建示意图  显示单链表的分析

创建节点  使用说明

head 节点  

1、不存放具体的数据   

2、作用就是表示单链

表头next

例子eg

class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next;
}

思路：

1）添加 （创建）

1、先创建一个head 头节点  作用就是表示单链表的头

2、后面我们每添加一个节点就直接加入到链表的最后

2）显示 （遍历）

1、通过一个 辅助变量遍历  帮助遍历整个链表  temp  

3）需要按照编号的顺序添加

1、首先找到新添加节点的位置  是通过 辅助变量指针  通过遍历来搞定

2、新的节点 next = temp.next;

3、将temp.next  = 新的节点

4）单链表删除节点思路   

1、 首先找到需要删除的这个节点的前一个节点temp

2、temp.next = temp.next,next

3、被删除的节点 将不会有其他引用指向  会被垃圾回收机制回收