第五讲-队列

队列：先进先出

基本操作：出队（enqueue）or入队（dequeue）

顺序队列和链式队列

用数组实现的队列叫做顺序队列，用链表实现的队列叫做链式队列。

顺序队列：

// 用数组实现的队列
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指针指向队尾。

然而呢，随着不停地出队入队操作，head和tail都会持续的往后移动，当tail移到最后时，即使数组中还有空闲空间，也无法继续入队了，为了解决这个问题，可以当tail==n时进行数据迁移，另一个更好的办法是使用循环队列。

1545227147333.png

实现循环队列最重要的是确定好队空和队满的判定条件。

在用数组实现的非循环队列中，队满tail == n，队空是 head == tail。

循环队列队满tail==n，队空(tail+1)%n=head

可以发现：当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

队列的应用

阻塞队列：在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。