1.队列

1.1队列的定义

队列是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

1.2队列的基本介绍

1）队列是一个有序列表，可以通过数组和链表来实现
2）队列遵循着先进先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。
3）队列的示意图

1.3用数组模拟实现队列

1.3.1数据模拟队列示意图

1.3.2数组模拟队列的思路

1）首先确定队列中的头指针(front)和尾指针(rear)，它们一开始都指向队头元素的前面-1的位置
2）当front == rear时，队列可以判断为空
3）当rear ==maxSize(队列的最大容量)时，队列可以判断满

1.4代码实现队列

package Queue队列;

import java.util.Scanner;

//使用数组模拟队列
public class ArrayQueue数组队列 {
    public static void main(String[] args) {
        ArrayQueue queue = 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':
                    queue.show();
                    break;
                case 'a':
                    System.out.println("请输入: ");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int value2 = queue.getQueue();
                        System.out.println(value2);
                    }catch (Exception e){
                        e.getMessage();
                    }
                    break;
                case 'h':
                    try {
                        int value3 = queue.getFirstQueue();
                        System.out.println(value3);
                    }catch (Exception e){
                        e.getMessage();
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}

class ArrayQueue{
    private int maxsize;          //队列最大容量
    private int front;          //头指针
    private int rear;           //尾指针
    private int[] arrQueue;     //数组

    public ArrayQueue(int arrMaxQueue){
        maxsize = arrMaxQueue;
        arrQueue = 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){
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        rear++;
        arrQueue[rear] = n;
    }

    public int getQueue(){
        if (rear == front){
            throw new RuntimeException("队列为空");
        }
        front++;
        return arrQueue[front];
    }

    //显示整个队列
    public void show(){
        if(rear == front){
            System.out.println("队列为空");
        }
        for (int i = 0; i < arrQueue.length; i++) {
            System.out.println(arrQueue[i]);
        }
    }

    //显示队列的头数据
    public int getFirstQueue(){
        if(rear == front){
            System.out.println("队列为空");
        }
        return arrQueue[front+1];
    }
}

2.循环队列

2.1循环队列的定义

队列的头尾相接的顺序存储结构称为循环队列。

2.2循环队列的基本介绍

从上图我们可以看出，如果进行一系列的入队出队的操作之后，我们可以发现下标为0和1的地方为空，如果再进行入队操作却会报队列已满。这种情况我们就可以成为假溢出。

解决假溢出的办法就是后面满了，就从头开始，也就是头尾相接的循环，我们把队列的这种头尾相接的顺序存储结构称为循环队列。

2.3用数组模拟实现循环队列

2.3.1数组模拟循环队列的思路

1）首先确定队列的front和rear指针，它们都指向了队列的头元素0。
2）确定队列的有效个数 (rear+maxSize-front)%maxSize
3）确定队列的判空条件 rear == front
4）确定队列的已满的情况 (rear + 1) % maxSize == front

2.4 代码实现

package Queue队列;

import java.util.Scanner;


//使用数组模拟队列
public class CircleQueue循环队列 {
    public static void main(String[] args) {
        CircleQueue queue = new CircleQueue(4);
        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':
                    queue.show();
                    break;
                case 'a':
                    System.out.println("请输入: ");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int value2 = queue.getQueue();
                        System.out.println(value2);
                    }catch (Exception e){
                        e.getMessage();
                    }
                    break;
                case 'h':
                    try {
                        int value3 = queue.getFirstQueue();
                        System.out.println(value3);
                    }catch (Exception e){
                        e.getMessage();
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}

class CircleQueue{
    private int maxsize;          //队列最大容量
    private int front;          //头指针
    private int rear;           //尾指针
    private int[] arrQueue;     //数组

    public CircleQueue(int arrMaxQueue){
        maxsize = arrMaxQueue;
        arrQueue = new int[maxsize];
        front = 0;//头指针一开始都指向队头元素0的位置a
        rear = 0;//尾指针一开始都指向队头元素0的位置
    }

    public boolean isFull(){
        return (rear + 1) % maxsize == front;       //循环队列判断队列是否已经满 (rear + 1) % maxsize == front
    }

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

    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        arrQueue[rear] = n;
        rear = (rear + 1) % maxsize;
    }

    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }

        //需要分析front是指向队列的第一个元素
        //1.先把front对应的值保存到一个临时变量
        //2.将front后移，需要考虑取%
        //3.将临时变量的值返回
        int value = arrQueue[front];
        front = (front + 1) % maxsize;
        return value;
    }

    public int total(){
        return (rear + maxsize - front) % maxsize;
    }

    //显示整个队列
    public void show(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        for (int i = front; i < front+total(); i++) {
            System.out.printf("arrQueue[%d]=%d\n",i%maxsize,arrQueue[i%maxsize]);
        }
    }

    //显示队列的头数据
    public int getFirstQueue(){
        if(rear == front){
            System.out.println("队列为空");
        }
        return arrQueue[front];
    }
}