原文链接：https://wangwei.one/posts/jav...
前面，我们学习了 栈的实现及应用 ，本篇我们来学习一下最后一种线性表——队列。
队列是我们日常开发中经常会用到的一种数据结构，我们经常使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。例如，不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须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/col...