队列

队列,是一个先进后出的数据结构。它是一个操作受限的线性表,只能在队尾插入元素,在队头移出元素。

可以由数组或链表实现。

数组实现简单队列

这个队列是一个最简单的队列,使用front指针指向队头,rear指向队尾。

每当插入元素时,rear指针后移;每当移出元素时,front指针前移。

front == rear时,队列为空;当rear == maxSize - 1时,队列为满。

这个实现起来挺容易的,但是不会用它,因为它有“假溢出”的问题。即当rear和front后移时,底层数组前面的元素就被空置,而且不会再使用。当rear到最后一个下标,且front也指向最后一个下标时,再往里添加元素,则发现队列已满。但事实上,底层的数组全是空的,空间极其浪费,究其原因,是因为这两个指针“不会回头”。

作为优化,此后会介绍循环队列的实现,下面先展示简单队列的实现。

public class ArrayQueue {
    /**
     * 存放数据
     */
    private int[] arr;
    /**
     * 指向队头的前一个元素
     */
    private int front;
    /**
     * 指向队尾的前一个元素
     */
    private int rear;
    /**
     * 最大长度
     */
    private int maxSize;


    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.front = -1;
        this.rear = -1;
        this.arr = new int[maxSize];
    }

    public boolean offer(int x) {
        if (isFull()) {
            System.out.println("queue is full.");
            return false;
        }
        arr[++rear] = x;
        return true;
    }

    public int poll() {
        if (isEmpty()) {
            System.out.println("queue is empty.");
            return -1;
        }
        return arr[++front];
    }

    public int peek(){
        if (isEmpty()){
            System.out.println("queue is empty.");
            return -1;
        }
        // front指向队头的前一个
        return arr[front + 1];
    }

    public boolean isFull() {
        return rear == maxSize - 1;
    }

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

    public void showQueue(){
        System.out.println(Arrays.toString(arr));
    }
}

数组实现循环队列

同样地,循环队列还是只有四个成员变量:arr、front、rear、maxSize。

但是呢,我们要怎么让走到结尾的指针又往前呢?

一个重要的操作——取余,也是操作符%。

笼统地讲,当rear指针走到最后,并且还要继续往里添加元素时,会先判断此时队列是否为满,如果不满,则说明能添加元素,然后让rear加一,再对该下标进行取余操作。因为它已经超出范围了,所以取余之后,rear会重新变为0,也就达到重新利用之前空间的目的。

相关定义

front:指向队列的第一个元素。

rear:指向队尾最后一个元素的下一个元素。

因此,它们的初始值都是0,这也表示,我们使用了一个空间来对循环队列的操作进行处理。具体有不同的算法,但是此处就是利用了一个空间,更好理解。下面会解释。

判断队列是否为空:front == rear。同普通队列。看看它的初值,都是0,那队列就为空了,也符合这个公式。

判断队列是否为满:(rear + 1) % maxSize == front。回忆一下普通队列的实现,这里只是多了一个取余,而它解决的是rear回头的问题。因为从上面的定义来说,rear是指向最后一个元素的下一个元素,如果这个下一个元素是队头,是不是就说明这个队列已经满了。

判断队列中元素个数:(rear - front + maxSize) % maxSize。这其实也很好理解,如果没有出现rear和front回头循环的情况,队列中的元素就是rear - front,这个取余就是为了看看它有没有突破这个数组的范围,突破了就重新计算一下。

public class CircleQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int maxSize;

    public CircleQueue(int maxSize) {
        // 空出一个元素,我们内部给它加上。。
        // PS:这个不应该,可以与ArrayDeque源码比对
        // 就是因为我们是先判断空/满,才导致当用一位?
        this.maxSize = maxSize + 1;
        this.arr = new int[maxSize + 1];
        this.front = 0;
        this.rear = 0;
    }

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

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

    /**
     * 先判断队列是否为满,如果是,则添加失败;
     * 如果不是,则直接往队尾添加(因为rear指向队尾的下一个元素)
     * 然后再让rear指针后移。
     * @param x 要添加的元素
     * @return true,添加成功
     */
    public boolean offer(int x) {
        if (isFull()) {
            return false;
        }
        arr[rear] = x;
        rear = (rear + 1) % maxSize;
        return true;
    }

    /**
     * 先判断队列是否为空,如果为空,则弹出失败
     * 如果不为空,先取出队头的值,然后再移动front指针,最后返回
     * @return 弹出的队头的元素
     */
    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int val = arr[front];
        arr[front] = 0;// clear
        front = (front + 1) % maxSize;
        return val;
    }

    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }

    public int size(){
        return (rear - front + maxSize) % maxSize;
    }

    public void show() {
        for (int i = front; i < size(); i++) {
            System.out.printf("index=%d, value=%d ", i % maxSize, arr[i % maxSize]);
        }
        System.out.println();
    }
}

ArrayDeque的扩展

在Java中,有一个双端队列叫做ArrayDeque,它的底层也是使用循环队列实现,比Stack、Queue这些更高效?下面简单看一看它的底层实现,其实和我们自己写的差不多!

首先看看它的定义:

// 指向队头的指针
transient int head;
// 指向队尾的下一个元素的指针
transient int tail;

addLast()

这个方法是把元素加到队列。

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

同样的,都是先赋值,然后再移动队尾指针。

移动的方式,使用了一种高级的位运算。它的底层数组的大小被限制在2的n次方,(tail + 1) & (elements.length - 1)语句同(tail + 1) % element.length,只是效率会更高。

pollFirst()

这个方法是把队头元素移出

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

它同样是先把值取出来,然后把该位置的变量赋空(for GC),调整头指针的指向,最后再返回该值。

与我们自己写的代码没啥不同嘛。

为什么ArrayDeque没有空一个元素

因为上述写的CricleQueue的offer()和poll()方法,是先判断容量再进行操作的。

假设CricleQueue的初始容量为8,当现在已经插入了7个元素后,rear指针确实是指向了空位。

但是!offer方法它会一开始判断容量isFull(),(rear + 1) % maxSize == front会为真,然后直接跳出添加方法。

而ArrayDeque则是直接进行添加或移出操作,但是它们在操作后,会判断一下容量,如果加完之后满了,就马上执行扩容操作。

同样的场景,对于ArrayDeque来说,rear指向空位,它先添加元素,然后判断一下容量是否为满 。

判断在后,自然那个空位就能添加成功。所以也就不会浪费一个空间。

至于它的容量,确实是满了,但是它有扩容操作,这是另说。