队列

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

如下图所示，我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

队列常用操作

队列的常见操作如下表（队列操作效率）所示。需要注意的是，不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。

方法名	描述	时间复杂度
push()	元素入队，即将元素添加至队尾	𝑂(1)
pop()	队首元素出队	𝑂(1)
peek()	访问队首元素	𝑂(1)

我们可以直接使用编程语言中现成的队列类：

/* 初始化队列 */
Queue<Integer> queue = new LinkedList<>();

/* 元素入队 */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);

/* 访问队首元素 */
int peek = queue.peek();

/* 元素出队 */
int pop = queue.poll();

/* 获取队列的长度 */
int size = queue.size();

/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();

队列实现

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

基于链表的实现

如下图所示，我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

以下是用链表实现队列的代码：

代码实现

public class LinkedListQueue<E> {
  /**
   * 队列的长度
   */
  private int size = 0;
  /**
   * 头指针，指向队列的第一个元素
   */
  private ListNode<E> front;
  /**
   * 尾指针，指向队列的最后一个元素
   */
  private ListNode<E> rear;

  /**
   * 获取队列的长度
   *
   * @return 队列的长度
   */
  public int size() {
    return size;
  }

  /**
   * 判断队列是否为空
   *
   * @return true 队列为空，false 队列不为空
   */
  public boolean isEmpty() {
    return size() == 0;
  }

  /**
   * 入队操作，将元素e添加到队列的尾部
   *
   * @param e 入队元素
   */
  public void push(E e) {
    ListNode<E> newNode = new ListNode<>(e);
    if (front == null) {
      front = newNode;
    } else {
      rear.next = newNode;
    }
    rear = newNode;
    size++;
  }

  /**
   * 出队操作，删除队首元素并返回
   *
   * @return 队首元素
   */
  public E pop() {
    // 获取队首元素
    E top = peek();
    // 将头指针指向队首元素的下一个节点
    front = front.next;
    // 队列长度减一
    size--;
    // 返回队首元素
    return top;
  }

  /**
   * 获取队首元素
   *
   * @return 队首元素
   */
  public E peek() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return front.value;
  }

  /**
   * 将队列中的元素转化为数组
   *
   * @return 队列中的元素组成的数组
   */
  public Object[] toArray() {
    ListNode<E> curr = front;
    Object[] res = new Object[size()];
    for (int i = 0; i < size(); i++) {
      res[i] = curr.value;
      curr = curr.next;
    }
    return res;
  }

  private static class ListNode<E> {
    /**
     * 节点值
     */
    E value;
    /**
     * 指向下一个节点的指针
     */
    ListNode<E> next;

    /**
     * 构造函数
     *
     * @param value 节点值
     */
    public ListNode(E value) {
      this.value = value;
    }
  }
}

测试

class LinkedListQueueTest {
  @Test
  public void test() {
    LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    queue.push(1);
    queue.push(3);
    queue.push(2);
    queue.push(5);
    queue.push(4);
    Assertions.assertArrayEquals(new Integer[]{1, 3, 2, 5, 4}, queue.toArray());
    Assertions.assertEquals(1, queue.peek());
    Assertions.assertEquals(1, queue.pop());
    Assertions.assertEquals(3, queue.peek());
    Assertions.assertEquals(4, queue.size());
    queue.pop();
    queue.pop();
    queue.pop();
    queue.pop();
    Assertions.assertTrue(queue.isEmpty());
  }
}

基于数组的实现

在数组中删除首元素的时间复杂度为 𝑂(𝑛) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如下图所示。

• 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
• 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 𝑂(1) 。

你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现，代码如下所示：

代码实现

public class ArrayQueue<E> {
  /**
   * 用于存储队列元素的数组
   */
  private final Object[] elementData;
  /**
   * 队头指针，指向队首元素
   */
  private int front;
  /**
   * 队列的长度
   */
  private int size;

  public ArrayQueue() {
    this(10);
  }

  public ArrayQueue(int capacity) {
    elementData = new Object[capacity];
    front = size = 0;
  }

  /**
   * 获取队列的容量
   *
   * @return 队列的容量
   */
  public int capacity() {
    return elementData.length;
  }

  /**
   * 获取队列的长度
   *
   * @return 队列的长度
   */
  public int size() {
    return size;
  }

  /**
   * 判断队列是否为空
   *
   * @return true：队列为空；false：队列不为空
   */
  public boolean isEmpty() {
    return size() == 0;
  }

  /**
   * 入队操作，将元素e添加到队列的尾部
   *
   * @param e 入队元素
   */
  public void push(E e) {
    if (size() == capacity()) {
      throw new IllegalStateException("队列已满");
    }
    // 计算队尾指针，指向队尾元素的下一个位置
    // 通过取余操作实现 rear 越过数组尾部后回到头部
    int rear = (front + size) % capacity();
    // 将元素放入队尾
    elementData[rear] = e;
    // 队列长度加 1
    size++;
  }

  /**
   * 出队操作，返回队首元素
   *
   * @return 队首元素
   */
  public E pop() {
    // 获取队首元素
    E top = peek();
    // 队首指针向后移动一位，若越过尾部，则返回到数组头部
    front = (front + 1) % capacity();
    // 队列长度减 1
    size--;
    // 返回队首元素
    return top;
  }

  /**
   * 获取队首元素
   *
   * @return 队首元素
   */
  public E peek() {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    return elementData(front);
  }

  /**
   * 将队列中的元素转化为数组
   *
   * @return 队列中的元素组成的数组
   */
  public Object[] toArray() {
    // 仅转换有效长度范围内的列表元素
    Object[] res = new Object[size()];
    // 将有效长度范围内的元素复制到新数组中
    for (int i = 0, j = front; i < size(); i++, j++) {
      res[i] = elementData(j % capacity());
    }
    return res;
  }

  @SuppressWarnings("unchecked")
  E elementData(int index) {
    return (E) elementData[index];
  }
}

测试

class ArrayQueueTest {
  @Test
  public void test() {
    ArrayQueue<Integer> queue = new ArrayQueue<>();
    queue.push(1);
    queue.push(3);
    queue.push(2);
    queue.push(5);
    queue.push(4);
    Assertions.assertArrayEquals(new Integer[]{1, 3, 2, 5, 4}, queue.toArray());
    Assertions.assertEquals(1, queue.peek());
    Assertions.assertEquals(1, queue.pop());
    Assertions.assertEquals(3, queue.peek());
    Assertions.assertEquals(4, queue.size());
    queue.pop();
    queue.pop();
    queue.pop();
    queue.pop();
    Assertions.assertTrue(queue.isEmpty());
  }
}

以上实现的队列仍然具有局限性：其长度不可变。然而，这个问题不难解决，我们可以将数组替换为动态数组，从而引入扩容机制。有兴趣的读者可以尝试自行实现。

两种实现的对比结论与栈一致，在此不再赘述。

队列典型应用

• 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。