队列

什么是队列

队列和栈一样，是只用操作受限的线性数据结构。在栈中，只支持两种基本操作：入栈和出栈，而在队列中也有两个基本操作：入队 和 出队。

栈和队列.jpg
我们知道，栈最大的特点是后进先出，而顾名思义，队列的特点是先进先出，这就想你在商店前排队买东西，先来的先买，后来的只能后买。

队列在计算机中应用的非常广泛，特别是具有某些额外特性的队列。

队列的实现

和栈一样，队列可以由数组或链表实现，前者称为顺序队列，后者为链式队列。

对于队列来说，我们需要两个指针：一个头指针（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;
  }
}

注意：我们知道数组的空间是有限的，而队列的指针会随着操作不断后移，最终一定会到达数组的最后，这时上面的队列就无法使用了。为此，我们延续数组的思路：对数据进行搬移：

队列搬移.jpg

我们将入队操作的代码修改如下：

   // 入队操作，将item放入队尾
  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;
  }

这样，队列就可以长时间使用了。

链式队列

看下面的图片，你会有大致思路：

链表队列.jpg

循环队列

你会发现，在顺序队列中，在 tail==n 的时候，会进行数据搬移，这样就影响了队列的性能，如何避免这种问题呢？我们可以使用循环队列来解决：

循环队列1.jpg

不难看出，循环队列比线性队列更加复杂，在代码编写中特别要注意循环队列的判空 和 判满条件：
判空：head == tail
判满：(tail + 1)%n = head

循环判满.jpg
循环队列代码如下：

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) {
    items = new String[capacity];
    n = capacity;
  }

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

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

队列的应用

阻塞队列和并发队列

在日常开发中，并不需要我们实现一个单纯的队列，一方面语言库一定会有现成的库，另一面单纯的队列应用场景有限。而一些具有特殊特性的队列的应用却十分广泛，比如阻塞队列和并发队列。

阻塞队列在队列的基础上增加了阻塞操作：在队列为空时，取数据的操作就会被阻塞，直到数据被写入；在队列满时，入队操作也会被阻塞，直到队列元素被消耗。

阻塞队列.jpg

并发队列：在多线程并发的时候，我们要防止线程不同步而导致的错误，这就需要使用并发队列。简而言之，就是在队列的入队、出队操作中加锁，以保证线程安全。当然，你可以尝试在循环队列中使用CAS原子操作。

使用队列分配资源池资源

举个例子：我们的线程池有4个线程，且已经被占用，此时再申请线程就会被拒绝，并且我们可以将这个申请放入一个资源队列中，当线程池有空闲线程时再将其从队列中取出。实际上，对于大部分资源有限的场景，当没有空闲资源的时候，基本上都可以通过”队列“将请求排队。

当然，你对资源的调度可能不想采用FIFO（先进先出）的形式，这就需要你设计自己的数据结构了。

小结

• 队列最大的特点是先进先出，主要操作为入队和出队。
• 队列可以由数组或链表实现。
• 编写循环队列的重点在于对队列的判空和判满。
• 具有某些特性的队列常常有很多的应用场景。

---

以上就是关于队列的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间