第七章 队列（Queue）

什么是队列

队列是一种特殊的线性表，只能在头尾两端进行操作。

• 队尾（rear）：只能在队尾添加元素，一般叫enQueue，入队
• 队头（front）：只能在队头移除元素，一般叫deQueue，出队
• 先进先出的原则，First in First out。

队列的接口设计

• int size();// 元素的数量
• boolean isEmpty();//是否是空
• void enQueue(E element);//入队
• E deQueue();//出队
• E front();//查看队头元素
• void clear();//清空元素

队列可以使用动态数组或链表实现，优先使用**双向链表实现，队列主要是在头尾**进行操作元素

双端队列（Deque，double ended queue）

双端队列能在头尾两端添加、删除元素

双端队列接口设计

• int size();// 元素的数量
• boolean isEmpty();//是否是空
• void clear();//清空元素
• void enQueueFront(E element);//从队头入队
• void enQueueRear(E element);//从队尾入队
• E deQueueFront();//从队头出队
• E deQueueRear();//从队尾出队
• E front();//查看队头元素
• E rear();//查看队尾元素

java.util.LinkedList 是双端队列

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
public interface Deque<E> extends Queue<E> {}

循环队列

其实队列的底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个数组实现并且优化后的队列叫做循环队列。

成员设计

public class CircleQueue<E> extends CustQueue<E> {
    private E[] array;
    /**
     * 队列的元素个数
     */
    private int size;
    /**
     * 队头元素的位置index
     */
    private int front;
}

入队（从队尾入队）

/**
     * 入队(从队尾位置入队)
     */
    @Override
    public void enQueue(E element) {
        //保证容量
        ensureCapacity(size + 1);
        array[realIndex(size)] = element;
        size++;
    }

出队（从队头出队）

 /**
     * 出队(从队头位置出队)
     *
     * @return
     */
    @Override
    public E deQueue() {
        E e = array[front];
        array[front] = null;
        front = realIndex(1);
        size--;
        return e;
    }

获取 index 对应的真实索引

    /**
     * 获取 index 对应的真实索引
     *
     * @param index
     * @return
     */
    private int realIndex(int index) {
        //return (front + index) % array.length;
        //(n%m) = (n>m)?(n-m):n;
        index += front;
        return index >= array.length ? (index - array.length) : index;
    }

扩容

    /**
     * 保证有capacity个容量
     *
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = array.length;
        if (capacity <= oldCapacity) {
            return;
        }
        //扩1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newArray = (E[]) new Object[newCapacity];
        int count = size;
        for (int i = 0; i < count; i++) {
            newArray[i] = array[realIndex(i)];
        }
        array = newArray;
        front = 0;
    }

%模运算优化

   //(front + index) % array.length;
        // n>=0,m>0,n<2m
        // front = 9 , index =9
        int n = 18;
        //m = array.length =10
        int m = 10;
        System.out.println(n % m);// 结果是8，n-m
       //front=2 ,index =3,m = array.length =7
        n = 5;
        m = 7;
        System.out.println(n % m);//结果是5，n
        (n%m) = (n>m)?(n-m):n;

循环双端队列

可以在两端进行添加、删除操作的循环队列。