数据结构与算法(三)：队列

定义

队列是一种操作受限的线性表数据结构，它的特点是只允许在表的前端进行删除操作，而在表的后端进行插入操作。即先进者先出。队列只支持两个基础操作，入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

顺序队列和链式队列

队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
用数组实现队列需要两个指针，head指针，指向队头；tail指针，指向队尾。在入队/出队时,通过调整head/tail指针的指向就可以实现一个先进先出的队列。代码实现如下：

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

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

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

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

但上段代码也存在一个问题，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。为了解决这个问题，我们可以在入队方法中，增加数据搬移的逻辑：

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

链表实现方式如下图：