看得见的数据结构Android版之队列篇

队列是一种线性的数据结构  
特性：尾部添加，头部取出 即先进先出FIFO  
操作：enqueue入队  dequeue出队  getFront查看队首元素

/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:15:57
 * 邮箱：1981462002@qq.com
 * 说明：队列接口
 */
public interface IQueue<T> {
    /**
     * 入队
     * @param el 元素
     */
    void enqueue(T el);

    /**
     * 出队
     * @return 元素
     */
    T dequeue();

    /**
     * 获取队首元素
     * @return 队首元素
     */
    T getFront();

    /**
     * 获取队列元素个数
     * @return 元素个数
     */
    int getSize();

    /**
     * 是否为空
     * @return 是否为空
     */
    boolean isEmpty();
}

/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:15:57
 * 邮箱：1981462002@qq.com
 * 说明：普通队列的数组实现----性能非常差,后面用数组实现循环队列来优化
 */
public class ArrayChartQueue<E> implements IQueue<E> {
    private ArrayChart<E> array;//成员变量

    public ArrayChartQueue(int capacity) {
        this.array = new ArrayChart<>(capacity);
    }

    public ArrayChartQueue() {
        this.array = new ArrayChart<>();
    }

    @Override
    public void enqueue(E el) {
        array.add(el);
    }

    @Override
    public E dequeue() {
        return array.remove(0);
    }

    @Override
    public E front() {
        return array.get(0);
    }

    @Override
    public int size() {
        return array.size();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
}

不就是想要知道队尾和队首是那个嘛，我标出来，维护一下给你不就行了吗  
注意：这里的优势在于维护了队尾和队首的标示，插入尾和删除头都是定点，而且数组整体不移动,而是标示在动
新加元素时，队尾表识后移，不够就扩容。删除头时队首标示  

循环队列特点：
为空时，`队尾标示==队首标示`,
队列满：`(队尾标示+1)%数组长度==队首标示`   
循环队列会使队首前一个位置不可用。

/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:16:03
 * 邮箱：1981462002@qq.com
 * 说明：数组实现循环队列
 */
public class ArrayLoopQueue<T> implements IQueue<T> {
    private T[] data;// 队列数据
    private int head;//队首标示
    private int tail;//队尾标示
    private int size;//元素个数
    public ArrayLoopQueue() {//无参构造：默认8个容量
        this(8);
    }
    public ArrayLoopQueue(int capacity) {
        // 因为会有一个浪费,所以+1
        data = (T[]) new Object[capacity + 1];
        head = 0;
        tail = 0;
        size = 0;
    }
    @Override
    public void enqueue(T el) {
        if (isFull()) {//加入时满了---扩容
            grow(capacity() * 2);
        }
        data[tail] = el;//在队尾插入
        //插入数据时对尾标示进行维护-----
        tail = (tail + 1) % data.length;
        size++;
    }
    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("MakeSure it's not an empty
        }
        T ret = data[head];
        data[head] = null;//让队首移除
        //队首移除时对首标示进行维护-----
        head = (head + 1) % data.length;
        size--;
        //闲置太多---缩容
        if (size == capacity() / 4 && capacity() / 2 != 0 && size > 4) {
            grow(capacity() / 2);
        }
        return ret;
    }
    @Override
    public T front() {
        if (isEmpty()) {
            throw new IllegalArgumentException("MakeSure it's not an empty
        }
        return data[head];
    }
    /**
     * 扩容/缩容
     *
     * @param newCapacity 新的容量
     */
    private void grow(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // 此时在newData中队首对齐回来，data中就得有一个front的偏移量
            newData[i] = data[(i + head) % data.length];
        }
        data = newData;
        head = 0;
        tail = size;
    }
    /**
     * 获取容量
     *
     * @return 容量
     */
    public int capacity() {
        return data.length - 1;
    }
    /**
     * 队列元素个数
     *
     * @return 元素个数
     */
    @Override
    public int size() {
        return size;
    }
    /**
     * 是否为空
     *
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }
    /**
     * 队列是否满了
     *
     * @return 队列是否满了
     */
    private boolean isFull() {
        // tail的下一个位置等于head时
        return (tail + 1) % data.length == head;
    }
}

/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:22:50
 * 邮箱：1981462002@qq.com
 * 说明：单链表实现队列
 */
public class SingleLinkedQueue<T> implements IQueue<T> {

    private Node head;//头节点
    private Node tail;//尾节点

    private int size;//元素个数

    public SingleLinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T el) {//入队
        // 如果队尾为空，说明队列是空的。因为tail一直指向最后一个非空节点。
        if (tail == null) {
            tail = new Node(null, el);//初始化
            head = tail;
        } else {
            tail.next = new Node(null, el); // 新来的排到后面去
            tail = tail.next; //更新队尾
        }
        size++;
    }

    @Override
    public T dequeue() {//出队
        if (isEmpty())
            throw new IllegalArgumentException("MakeSure it's not an empty queue");
        Node targetNode = head;//我是老大
        head = head.next; // 我是老二，但我要篡位了...以后哥就是老大
        targetNode.next = null; //前任老大走了....
        if (head == null) {// 如果头结点为空
            tail = null;
        }
        size--;
        return targetNode.el;
    }

    @Override
    public T front() {
        if (isEmpty())
            throw new IllegalArgumentException("MakeSure it's not an empty queue");
        return head.el;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private class Node {
        private T el;//改节点上的元素
        private Node next; //下一节点
        /**
         * 两参构造
         *
         * @param next //下一节点
         * @param el   生成节点的元素值
         */
        private Node(Node next, T el) {
            this.el = el;
            this.next = next;
        }
    }
}