# 队列

队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序集合。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列跟栈一样，也是一种操作受限的线性表数据结构。队列支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

# 顺序队列 & 链式队列

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

# 顺序队列实现

下面是基于数组的实现方法：

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items
  private String[] items;
  // 数组大小：n
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public ArrayQueue(int capacity) {
    this.items = new String[capacity];
    this.n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (this.tail == n) return false;
    this.items[this.tail] = item;
    ++this.tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (this.head == this.tail) return null;
    String ret = this.items[this.head];
    ++this.head;
    return ret;
  }
}

👆 上面代码中，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

改进方法是：如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据搬移操作。

// 入队操作，将item放入队尾
public boolean enqueue(String item) {
  // tail == n表示队列末尾没有空间了
  if (this.tail == n) {
    // this.tail ==n && head==0，表示整个队列都占满了
    if (this.head == 0) return false;
    // 数据搬移
    for (int i = this.head; i < this.tail; ++i) {
      this.items[i-this.head] = this.items[i];
    }
    // 搬移完之后重新更新 head 和 tail
    this.tail -= this.head;
    this.head = 0;
  }

  this.items[this.tail] = item;
  this.tail++;
  return true;
}

# 链表队列实现

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。

入队时，tail->next = new_node, tail = tail->next；
出队时，head = head->next；

# 循环队列

循环队列，长得像一个环。原本队列是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

在之前“顺序队列” 的实现中，我们用数组实现了一个队列。但是入队操作时，可能会涉及一个数据搬移操作。通过使用 “循环队列” 就避免了这个问题。

👇 下面是代码实现：


public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    this.items = new String[capacity];
    this.n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 当队满时，(tail + 1) % n = head
    if ((this.tail + 1) % this.n == this.head) return false;
    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果this.head == this.tail 表示队列为空
    if (this.head == this.tail) return null;
    String ret = this.items[this.head];
    this.head = (this.head + 1) % n;
    return ret;
  }
}