队列在有限资源池中的应用

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 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

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

课后思考

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