队列：先进者先出；操作受限的线性表数据结构
最基本的两个操作，入队和出队
image.png

顺序队列和链式队列

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

对于栈来说，只需要一个栈顶指针就可以了，但队列需要两个指针：一个是head指针，指向对头；一个tail指针，指向队尾。
image.png
用数组实现队列

  2. // 用数组实现的队列
  3. public class ArrayQueue {
  4.   // 数组：items，数组大小：n
  5.   private String[] items;
  6.   private int n = 0;
  7.   // head表示队头下标，tail表示队尾下标
  8.   private int head = 0;
  9.   private int tail = 0;
  11.   // 申请一个大小为capacity的数组
  12.   public ArrayQueue(int capacity) {
  13.     items = new String[capacity];
  14.     n = capacity;
  15.   }
  17.   // 入队
  18.   public boolean enqueue(String item) {
  19.     // 如果tail == n 表示队列已经满了
  20.     if (tail == n) return false;
  21.     items[tail] = item;
  22.     ++tail;
  23.     return true;
  24.   }
  26.   // 出队
  27.   public String dequeue() {
  28.     // 如果head == tail 表示队列为空
  29.     if (head == tail) return null;
  30.     // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
  31.     String ret = items[head];
  32.     ++head;
  33.     return ret;
  34.   }
  35. }

数据搬移
随着不停的进入队列，出队的操作，队列尾部会没有多余的空间，但之前出队的数据会空出空间。这就需要将剩余的数据搬到空闲的空间中。
但可以不用在每次出队时搬移数据。如果没有空闲空间，只需要在 入队时，集中出发一次数据搬移操作就行。

  2.    // 入队操作，将item放入队尾
  3.   public boolean enqueue(String item) {
  4.     // tail == n表示队列末尾没有空间了
  5.     if (tail == n) {
  6.       // tail ==n && head==0，表示整个队列都占满了
  7.       if (head == 0) return false;
  8.       // 数据搬移
  9.       for (int i = head; i < tail; ++i) {
  10.         items[i-head] = items[i];
  11.       }
  12.       // 搬移完之后重新更新head和tail
  13.       tail -= head;
  14.       head = 0;
  15.     }
  17.     items[tail] = item;
  18.     ++tail;
  19.     return true;
  20.   }

image.png
链表队列实现
image.png

循环队列

首尾相连，是一个环
image.png
确定好队空和队满的判定条件
队满的条件是tail == n，对空的条件是head==tail
公式：head=(tail+1)%n

  2. public class CircularQueue {
  3.   // 数组：items，数组大小：n
  4.   private String[] items;
  5.   private int n = 0;
  6.   // head表示队头下标，tail表示队尾下标
  7.   private int head = 0;
  8.   private int tail = 0;
  10.   // 申请一个大小为capacity的数组
  11.   public CircularQueue(int capacity) {
  12.     items = new String[capacity];
  13.     n = capacity;
  14.   }
  16.   // 入队
  17.   public boolean enqueue(String item) {
  18.     // 队列满了
  19.     if ((tail + 1) % n == head) return false;
  20.     items[tail] = item;
  21.     tail = (tail + 1) % n;
  22.     return true;
  23.   }
  25.   // 出队
  26.   public String dequeue() {
  27.     // 如果head == tail 表示队列为空
  28.     if (head == tail) return null;
  29.     String ret = items[head];
  30.     head = (head + 1) % n;
  31.     return ret;
  32.   }
  33. }

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。当没有数据时阻塞操作，当队列满了时阻塞操作。
image.png
生产者 - 消费者模型
可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。
多个线程同时操作队列，会存在线程安全问题。

线程安全的队列我们叫作并发队列。

对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

思考

1、除了线程池这种池结构会用到队列排队强求，你还知道哪些类似的池结构或者场景
消息队列