队列

1、队列的定义及基本概念

“队列”（Queue）这个单词时英国人说的 “排”（line）（一种等待服务的方式），在生活中，队列在我们日常生活中经常碰到，例如，排队买东西。

在计算机科学中，队列是一种数据结构，是一种特殊的线性表。和栈类似。但相差很大。

队的操作是在两端进行，其中一端只能进行插入，该端称为队列的队尾，而另一端只能进行删除，该端称为队列的队首。队列的运算规则时FIFO（First In First Out）

队列的基本运算：

• 置空队：建立一个空队列

• 判断队空：队列是否为空

• 判断队满：队列是否满

• 入队：在队列非满时，从队尾插入元素

• 出队：在队列非空时，从队首删除元素

• 取队首元素：不删除元素，返回队首元素

• 遍历队列：打印出数组中的有效数据

队列的存储具有顺序存储和链式存储两种。顺序存储通过数组存储，链式存储通过链表存储。

2、单向队列

我们通过数组来模拟单向队列。

由于队列的对头和队尾的位置是变化的，因而要设置两个指针front和rear来分别指示队头元素和队尾元素在空间中的位置。

在构造顺序队列时，两个指针初始化置为0，入队时将新元素插入rear所指的位置，然后将rear加1，出队时，删除front所指的元素，然后将front加1并返回被删元素。

在入队和出队时，我们需要判断队空和队满。

图解：

初始化：创建一个maxSize的数组 。 front 和 rear 为-1 。

添加数据：先将rear加1，然后将rear指向的数组赋值

删除数据：先front加1，然后取出front指向的数据，因为front指向的是队列头的前一个位置。

判断为满：可以看出。当rear 等于 maxSize-1时，队列满。

判断为空：当font和rear相等时，为空

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

    //队列构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        //创建一个长度为maxSize的数据
        arr = new int[maxSize];

        //指向队列的头部，分析出front时指向队列头的前一个位置
        front = -1;
        //指向队列的尾部，指向队列尾部的数据
        rear = -1;
    }

    //判断队列是否为满
    public boolean isFull(){
        return rear == maxSize - 1;
    }

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

    //添加数据到队列中
    public void AddQueue(int n){
        if(!isFull()){
            rear++;
            arr[rear] = n;
        }
        else {
            System.out.println("队列已满，无法添加数据");
        }
    }

    //出队列，并返回数据
    public int GetQueue(){
        if(iSEmpty()){
            System.out.println("队列为空，无法返回数据");
            throw new RuntimeException("队列空，不能取数据");
        }

        front++;
        return arr[front];
    }

    //遍历队列
    public void ShowQueue(){
        if(iSEmpty()){
            System.out.println("队列为空");
            return;
        }

        for (int i = front; i < rear; i++) {
            System.out.print(arr[i + 1] + "\t");
        }

        System.out.println();
    }

    //显示头数据
    public int GethandQueue(){
        if(iSEmpty()){
            System.out.println("队列为空，无法返回数据");
            throw new RuntimeException("队列空，不能取数据");
        }

        return arr[front + 1];
    }

}

测试：

public static void main(String[] args) {
    ArrayQueue arrayQueue = new ArrayQueue(3);
    System.out.println(arrayQueue.iSEmpty());

    arrayQueue.AddQueue(1);
    arrayQueue.AddQueue(2);
    arrayQueue.ShowQueue();

    arrayQueue.GetQueue();
    arrayQueue.ShowQueue();

    System.out.println(arrayQueue.GethandQueue());

}

问题：
我们添加三次数据，然后删除3次数据。 显示为满，但实际上队列中没有数据

public static void main(String[] args) {
    ArrayQueue arrayQueue = new ArrayQueue(3);

    arrayQueue.AddQueue(1);
    arrayQueue.AddQueue(2);
    arrayQueue.AddQueue(3);

    arrayQueue.GetQueue();
    arrayQueue.GetQueue();
    arrayQueue.GetQueue();

    System.out.println(arrayQueue.isFull());  //true
}

此时数组为空，但无法存储数据；

为了解决这个问题，我们引入循环队列，消除假溢出；

3、循环队列

我们通过取模来实现循环队列，将数组看成一个环形。也就是当队尾到最大值maxSize时，取模，使队尾等于0。
在循环队列中，判空的条件使rear == front ，判满的条件也是rear == front，为了避免二义性。所以人为的浪费一个空间，这样判满的条件为 front == （rear + 1）% maxSize；

图解：

初始化：front和rear都等于0。

此时的front和rear的含义与单向队列中的含义不同了；

front是指向队头

rear是指向队尾的下一个数据

添加一个数据：先存入数据，然后：rear = (rear + 1）% maxSize

删除一个数据： 因为front指向的是当前数据，只能用一个临时变量将当前的数据存上，然后 front = （front + 1）% maxSize，最后返回临 时变量

判空：rear == front

判满：front == （rear + 1）% maxSize

class ArrayCircularQueue{

    //表示数组的最大容量
    private int maxSize;

    //队列头  此处的front指向队列的第一个数据
    private int front;

    //队列尾   此处的rear最后一个数据的下一个数据
    private int rear;

    //该数据用于存放数据，模拟队列
    private int[] arr;

    //初始化队列
    public ArrayCircularQueue(int Size){
        maxSize = Size;

        front = 0;
        rear = 0;

        arr  = new int[maxSize];
    }

    //判空
    public boolean isEmpty(){
        return rear == front;
    }

    //判满
    public boolean isFull(){
        return front == (rear + 1) % maxSize;
    }

    //添加数据
    public void AddQueue(int n){
        if (isFull()){
            System.out.println("队列已满");
        }

        arr[rear] = n;
        rear = (rear + 1) % maxSize;

    }

    //出队列，返回队头数据
    public int GetQueue(){
        if(isEmpty()){
            System.out.println("队列为空，无法返回数据");
            throw new RuntimeException("队列空，不能取数据");
        }

        int value = arr[front];
        front = (front + 1) % maxSize;

        return value;
    }

    //遍历队列
    public void ShowQueue(){
        if (isEmpty()){
            System.out.println("队列为空");
            return;
        }

        int i = front;

        while(i != rear)
        {
            System.out.print(arr[i] + "\t");

            i = (i + 1) % maxSize;
        }
        System.out.println();
    }

    //得到队列的有效数据个数
    public int Size(){
        return (rear - front + maxSize) % maxSize;
    }

    //得到队列的队首数据
    public int getHandQueue(){
        if (isEmpty()){
            System.out.println("队列为空，无法返回数据");
            throw new RuntimeException("队列空，不能取数据");
        }

        return arr[front];
    }

}

测试：

public static void main(String[] args) {
    //实际上只能存储2个数据
    ArrayCircularQueue arrayCircularQueue = new ArrayCircularQueue(3);

    System.out.println(arrayCircularQueue.isEmpty());

    arrayCircularQueue.AddQueue(1);
    arrayCircularQueue.AddQueue(2);

    arrayCircularQueue.ShowQueue();

    arrayCircularQueue.GetQueue();

    arrayCircularQueue.ShowQueue();

    System.out.println(arrayCircularQueue.getHandQueue());

    System.out.println(arrayCircularQueue.Size());


}

这样就解决了假溢出问题，队列也可以重复使用：

ArrayCircularQueue arrayCircularQueue = new ArrayCircularQueue(3);

arrayCircularQueue.AddQueue(1);
arrayCircularQueue.AddQueue(2);

arrayCircularQueue.GetQueue();
arrayCircularQueue.GetQueue();

System.out.println(arrayCircularQueue.isFull());   //false