数据结构与算法 | 队列的实现及其应用

前面，我们学习了 [栈的实现及应用](https://wangwei.one/posts/java-data-structures-and-algorithms-stack.html) ，本篇我们来学习一下最后一种线性表——队列。

队列是我们日常开发中经常会用到的一种数据结构，我们经常使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。例如，不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须100%处理成功、不知道谁依赖“我”的处理结果、不关心其他系统如何处理后续业务、不需要强一致性，只需保证最终一致性即可、想要保证数据处理的有序性等等，这些问题都考虑使用队列来解决。

队列

定义

队列与 栈 一样，都是操作受限的线性表数据结构。队列从一端插入数据，然后从另一端取出数据。插入数据的一端称为”队尾“，取出数据的一端称为”队头“，如图所示：

特点

• FIFO（First In First Out）：先进先出原则

分类

与 栈 一样，队列也分为顺序队列与链式队列，分别使用数组与链表来实现。

链式队列

链式队列实现比较简单，使用单链表即可实现，如果所示：

### 代码实现

package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 * 链表队列
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2019/03/27
 */
public class LinkedQueue<T> implements IQueue<T> {

    private int size = 0;
    private Node<T> head;
    private Node<T> tail;

    public LinkedQueue() {
    }

    /**
     * 添加元素到队列头部
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(value, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * 移除队列尾部元素
     *
     * @return
     */
    @Override
    public T poll() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node<T> tmpHead = head;
        head = head.next;
        tmpHead.next = null;
        size--;
        if (head == null) {
            tail = null;
        }
        return tmpHead.element;
    }

    /**
     * 查看队列尾部元素值
     *
     * @return
     */
    @Override
    public T peek() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return head.element;
    }

    /**
     * 清除队列元素
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * 队列大小
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private static class Node<T> {
        private T element;
        private Node<T> next;

        private Node(T element) {
            this.element = element;
        }

        private Node(T element, Node<T> next) {
            this.element = element;
            this.next = next;
        }
    }
}

源码

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

顺序队列

顺序队列采用数组实现，数组的实现有两种方式，一种是顺序式的，一种是循环数组实现。

顺序队列

当队列尾部没有剩余空间后，需要集中进行一次数据搬迁腾出空间，才能继续进行入队操作。如图所示：

循环队列

顺序队列会存在数据搬迁的问题，对入队操作有性能方面的影响。我们可以采用循环数组的方式来解决这一问题，如图所示：

当队尾无存储空间且队列未满时，我们可以将其存储到数组的前半部分剩余的空间去。

代码实现

循环队列的实现关键在于队列为空和为满时的状态判断：

• 当队列为空时：rear == front
• 当队列为满时：front == (rear + 1) % array.length，队满时，会浪费一个数组的存储空间。

代码如下：

package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 * 数组队列
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2019/02/04
 */
public class ArrayQueue<T> implements IQueue<T> {

    /**
     * default array size
     */
    private static final int DEFAULT_SIZE = 1024;
    /**
     * 元素数组
     */
    private T[] array;
    /**
     * 队头指针下标
     */
    private int front = 0;
    /**
     * 队尾指针下标
     */
    private int rear = 0;

    public ArrayQueue() {
        this(DEFAULT_SIZE);
    }

    public ArrayQueue(int capacity) {
        array = (T[]) new Object[capacity];
    }

    /**
     * 添加队尾元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        if (isFull()) {
            grow();
        }
        array[rear % array.length] = value;
        rear++;
        return true;
    }

    /**
     * grow queue size doubly
     */
    private void grow() {
        int growSize = array.length << 1;
        T[] tmpArray = (T[]) new Object[growSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear < front) {
            System.arraycopy(array, 0, tmpArray, array.length - adjRear, adjRear + 1);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = tmpArray;
        rear = (rear - front);
        front = 0;
    }

    /**
     * 移除队头元素
     *
     * @return
     */
    @Override
    public T poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        T element = array[front % array.length];
        array[front % array.length] = null;
        front++;
        if (isEmpty()) {
            // remove last element
            front = rear = 0;
        }

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && size() < shrinkSize) {
            shrink();
        }
        return element;
    }

    /**
     * 压缩
     */
    private void shrink() {
        int shrinkSize = array.length >> 1;
        T[] tmpArray = (T[]) new Object[shrinkSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear <= front) {
            System.arraycopy(array, 0, tmpArray, array.length - front, adjRear);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = null;
        array = tmpArray;
        rear = rear - front;
        front = 0;
    }

    /**
     * 查看队头元素
     *
     * @return
     */
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }
        return array[front % array.length];
    }

    /**
     * 清除队列元素
     */
    @Override
    public void clear() {
        array = null;
        front = rear = 0;
    }

    /**
     * 队列大小
     */
    @Override
    public int size() {
        return rear - front;
    }

    /**
     * 判断队列是否满
     *
     * @return
     */
    private boolean isFull() {
        return !isEmpty() && (front == (rear + 1) % array.length);
    }

    /**
     * 判断队是否为空
     *
     * @return
     */
    private boolean isEmpty() {
        return size() <= 0;
    }

}

源码

基于数组实现的有界队列（bounded queue），队列的大小有限，当请求数量超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

参考资料

• 《数据结构与算法之美》
• https://time.geekbang.org/column/article/41330