队列

遇到排队问题，经常会使用到队列。先到的先服务，后到的从队伍后面排队，等待服务。

1. 定义

一种可以实现“先进先出”的存储结构

栈只允许在一端进行操作，而队列在两端操作，队尾进行存入，队头进行删除

2. 分类

• 静态队列(连续队列)

  静态队列通常必须是循环队列

• 动态队列(链式队列)

3.静态队列

1) 静态非循环队列

（1）使用数组模拟队列的思路

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，maxSize 是该队列的最大容量，即数组长度。

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

注意：front指向队列第一个数据的前一个位置，rear指向最后一个数据的位置。

初始化时front和rear都为-1。

（2）判断队列满和空的条件

满：rear+1 == maxSize;

空：front == rear；

（3）存在的问题

数组使用一次就不能再次使用，不能达到复用的效果（这时就需要使用循环队列）

（4）代码实现：

package datastructure;

import java.util.Scanner;

/**
 * 使用数组模拟队列
 * 存在的问题：
 * 数组只能利用一次，不能重复利用（应该使用循环数组解决）
 * Created by qjq on 2020/1/18 19:57
 */
public class ArrayQueueDemo {
    //测试
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key;//用于接收用户输入
        Scanner scanner = 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):显示队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符串
            switch (key){
                case 's':
                    try{
                        arrayQueue.showQueue();
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入需要插入的数据：");
                    int value = scanner.nextInt();
                    try{
                        arrayQueue.addQueue(value);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try{
                        int val = arrayQueue.getQueue();
                        System.out.printf("取出的数据是%d\n",val);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try{
                        int val = arrayQueue.headQueue();
                        System.out.printf("取出的队列头的数据是%d\n",val);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class ArrayQueue {
    private int maxSize;//表示数组的最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//该数组用于模拟队列存放数据

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];//初始化队列
        front = -1;//指向队列头部，指向队列头的前一个位置
        rear = -1;//指向队列的尾部，指向队列的最后一个数据（即就是队列最后一个数据）
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize-1;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return front == rear;
    }

    //添加数据到队列
    public void addQueue(int info){
        if(isFull()){
            throw new RuntimeException("列表已满，不能插入数据");
        }
        rear++;
        arr[rear]=info;
    }

    //获取队列数据，出队
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取数据");
        }
        front++;
        return arr[front];
    }

    //显示队列所有数据
    public void showQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取数据");
        }
        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];
    }
}

2) 静态循环队列

（1）静态队列为什么必须是循环队列

防止浪费空间

（2）循环队列需要几个参数来确定

需要2个参数来确定: 队头指针front和队尾指针rear。队头删除，队尾存入

注意: 两个参数不同场合有不同的含义，这个先记住，慢慢体会

场合1 队列初始化 front和rear的值都是零

场合2 队列非空

front代表的是队列的第一个元素，

rear代表的是队列的最后一个有效元素的下一个元素，是下一个！！！

场合3 队列空 front和rear的值相等，但不一定是零

（3）循环队列入队伪算法讲解

第一步: 将值存入rear所代表的位置

第二步: 错误写法 rear=rear+1; (＞﹏＜)

正确写法 rear=（rear+1）%数组的长度

（4）循环队列出队伪算法讲解

front=（front+1）%数组的长度

（5）队列的长度(有效数据的个数)

将未进入循环和进入循环综合之后：

length = （rear + maxSize - front）%maxSize

（6）如何判断循环队列是否为空(后面有图解)

如果front与rear的值相等，则该队列就一定为空

（7）如何判断循环队列是否已满(后面有图解)

预备知识1: 当front = rear时，这个循环队列是满的还是空的？这个没有办法判断。为了区分空和满，规定front指向队头元素的位置，rear指向队尾元素的下一个位置(rear指向的必须为空)，所以满队元素个数比数组元素个数少一个，也就是说牺牲一个存储位置，换来了不再纠结空和满的判断(∩_∩)

预备知识2: front的值可能比rear大，也可能比rear小，也可能两者相等

那么如何判断队列已满？就是如果f和r的值紧挨着，则队列已满

用C语言伪算法表示就是:

if（（rear+1）%数组长度== front）

​ 已满

else

​ 不满

（8）图解

（8）代码实现

package datastructure;

import java.util.Scanner;

/**
 * 循环数组队列
 * Created by qjq on 2020/1/19 12:12
 */
public class CircleArrayQueueDemo {
    //测试
    public static void main(String[] args) {
        //创建一个队列
        CircleArrayQueue arrayQueue = new CircleArrayQueue(3);
        char key;//用于接收用户输入
        Scanner scanner = 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):显示队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符串
            switch (key){
                case 's':
                    try{
                        arrayQueue.showQueue();
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入需要插入的数据：");
                    int value = scanner.nextInt();
                    try{
                        arrayQueue.addQueue(value);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try{
                        int val = arrayQueue.getQueue();
                        System.out.printf("取出的数据是%d\n",val);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try{
                        int val = arrayQueue.headQueue();
                        System.out.printf("取出的队列头的数据是%d\n",val);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop=false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class CircleArrayQueue {
    private int maxSize;//表示数组的最大容量
    private int front;//队列头  指向队列第一个元素
    private int rear;//队列尾 队列的最后一个有效元素的下一个元素
    private int[] arr;//该数组用于模拟队列存放数据

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];//初始化队列
        front = 0;//指向队列头部，指向队列第一个元素
        rear = 0;//指向队列的尾部，队列的最后一个有效元素的下一个元素
    }
    //判断队列是否满
    public boolean isFull(){
        return (rear+1)%maxSize == front;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return front == rear;
    }

    //添加数据到队列
    public void addQueue(int info){
        if(isFull()){
            throw new RuntimeException("列表已满，不能插入数据");
        }
        arr[rear]=info;//和非循环队列不同
        rear = (rear+1)%maxSize;
    }

    //获取队列数据，出队
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取数据");
        }
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }

    //显示队列所有数据
    public void showQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取数据");
        }
        //从front开始遍历，直到rear的前一个位置
        for (int i = front; i < front+size(); i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

    //计算队列有效数据的个数
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //显示队列头部信息，只是显示，不是出队
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无法获取数据");
        }
        return arr[front];
    }
}

3）非循环队列与循环队列的区别

	front	rear	判空	判满	入队	出队
非循环队列	指向第一个有效数据的前一个位置（初始值为-1）	指向最后一个有效数据的位置（初始值为-1）	rear==front	rear+1==maxSize	1.判断是否满; 2.rear++; 3. 将值赋给rear所在位置的队列	1.判断是否为空；2.front++；3. 返回front所在位置的值
循环队列	指向第一个有效数据的位置（初始值为0）	指向最后一个有效数据的后一个位置（初始值为0）	rear==front	(rear+1)%maxSize == front	1. 判断是否满；2. 将值赋给rear所在位置的队列；3. rear=(rear+1)%maxSize	1. 判断是否为空；2. 将font所在位置的值传给中间变量temp；3. front=(front+1)%maxSize；4. 返回temp

4.动态队列(待完成)