有限资源池中如何应用队列？

1. 什么是队列？

队列的特点是先进先出，有两个基本操作：入队（enqueue），放一个数据到队列尾部；出队（dequeue），从队列头部取一个元素。。它和栈一样，也是一种操作受限的线形表数据结构。

队列的应用非常广泛，特别是少量具备某些额外特性的队列，比方循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

2. 如何实现队列？

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

使用数组实现的队列：

public class QueueByArray<E> {    private int size;    private E[] data;    private int head;    private int tail;    public QueueByArray() {        this(8);    }    public QueueByArray(int size) {        data = (E[]) new Object[size];        this.size = size;    }    /**     * 入队     *     * @param element     * @return     */    public boolean enqueue(E element) {        // 队尾没有空间        if (tail == size) {            // 队列已满            if (head == 0) {                return false;            }            System.out.println("move element, head " + head + ", tail " + tail);            // 移动元素，从尾部向首部搬移            for (int i = head; i < tail; i++) {                data[i - head] = data[i];            }            tail -= head;            head = 0;        }        data[tail++] = element;        return true;    }    /**     * 出队     *     * @return     */    public E dequeue() {        // 队列为空        if (head == tail) {            return null;        }        return data[head++];    }}

使用链表实现的队列：

public class QueueByLink<E> {    private int size;    private Node head;    private Node tail;    /**     * 入队     *     * @param element     */    public void enqueue(E element) {        if (head == null) {            head = new Node();            head.element = element;            tail = head;        } else {            Node node = new Node();            node.element = element;            tail.next = node;            tail = node;        }        size++;    }    /**     * 出队     *     * @return     */    public E dequeue() {        if (head == null) {            return null;        }        E element = head.element;        head = head.next;        size--;        return element;    }    private class Node {        private E element;        private Node next;    }}

3. 循环队列

循环队列像一个环，首尾相连，避免了数据移动。实现循环队列的关键是，确定好队空和队满的判定条件。当队满时，(tail+1)%n=head。

下面是使用数组实现循环队列：

public class CircularQueue<E> {    // 容量    private int size;    private E[] data;    private int head;    private int tail;    public CircularQueue() {        this(8);    }    public CircularQueue(int size) {        data = (E[]) new Object[size];        this.size = size;    }    /**     * 入队     *     * @param element     * @return     */    public boolean enqueue(E element) {        // 队列已满        if ((tail + 1) % size == head) {            return false;        }        data[tail] = element;        tail = (tail + 1) % size;        return true;    }    /**     * 出队     *     * @return     */    public E dequeue() {        // 队列为空        if (head == tail) {            return null;        }        E ele = data[head];        head = (head + 1) % size;        return ele;    }}

4. 阻塞队列和并发队列

阻塞队列就是在队列基础上添加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。直到队列中有了数据才能返回；假如队列已经满了，那么插入数据就会被阻塞，直到队列中有空闲位置后再插入数据，而后再返回。这种基于阻塞队列实现的“生产者 – 消费者模型”，可以有效地协调生产和消费的速度。

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的起因。

线程池的阻塞队列分为两种：基于链表的实现方式，可以实现一个支持无限排队的无界队列，但是可能会导致过多的请求排队等待，请求解决的响应时间过长。而基于数组实现的有界队列，队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，设置一个正当的队列大小非常有讲究。

课后思考

还有哪些相似线程池结构或者者场景中会用到队列的排队请求呢？

自己是从事了七年开发的Android工程师，不少人私下问我，2019年Android进阶该怎样学，方法有没有？

没错，年初我花了一个多月的时间整理出来的学习资料，希望能帮助那些想进阶提升Android开发，却又不知道怎样进阶学习的朋友。【包括高级UI、性能优化、架构师课程、NDK、Kotlin、混合式开发（ReactNative+Weex）、Flutter等架构技术资料】，希望能帮助到您面试前的复习且找到一个好的工作，也节省大家在网上搜索资料的时间来学习。

资料获取方式：加入Android架构交流QQ群聊：513088520 ，进群即领取资料！！！

点击链接加入群聊【Android移动架构总群】：加入群聊

资料大全