目录

数据结构与算法目录(https://www.cnblogs.com/binarylei/p/10115867.html)

我们今天要讲的数据结构是队列，比如 Java 线程池任务就是队列实现的。

和栈一样，队列也是一种操作受限的线性结构。使用队列时，在一端插入元素，而在另一端删除元素。

  • 队列中的数据元素遵守 “先进先出”（First In First Out）的原则，简称 FIFO 结构。
  • 限定只能在队列一端插入，而在另一端进行删除操作。
  • 入队（enqueue）：队列的插入操作。
  • 出队（dequeue）：队列的删除操作。

和栈一样，队列也有两种实现方案，我们简单分析一下这两种队列的复杂度：

  • 动态队列（链表）：也叫链式队列。其插入、删除时间复杂度都是 O(1)。
  • 静态队列（数组）：也叫顺序队列。当队列队尾指针移到最后时，此时有两种操作：一是进行简单的数据搬移，二是进行队列循环。

关于队列的实现，我们只实现如下的基本操作。

  1. public interface Queue {
  2.     Queue enqueue(Object obj);   // 入队
  3.     Object dequeue();            // 出队
  4.     int size();                  // 元素个数
  5. }

链式队列的实现非常简单，其插入和删除的时间复杂度都是 O(1)。为了简化代码的实现，我们引入哨兵结点。如下图所示，head 头结点是哨兵结点，不保存任何数据，从 head.next 开始保存数据，tail 结点指向最后一个元素结点。链表队列头结点和尾结点说明：

  • 头结点：head 结点为哨兵结点，不保存任何数据，数据从第二个结点开始。
  • 尾结点：tail 结点指向最后一个数据结点。

根据上图，我们可以轻松实现一个链表组成的队列，代码也很简单。

  1. public class LinkedQueue implements Queue {
  3.     private Node head;
  4.     private Node tail;
  5.     private int size;
  7.     public LinkedQueue() {
  8.         head = new Node(null, null);
  9.         tail = head;
  10.     }
  12.     @Override
  13.     public Queue enqueue(Object obj) {
  14.         tail.next = new Node(obj, null);
  15.         tail = tail.next;
  16.         size++;
  17.         return this;
  18.     }
  20.     @Override
  21.     public Object dequeue() {
  22.         Node next = head.next;
  23.         if (next == null) {
  24.             return null;
  25.         }
  26.         head = head.next;
  27.         size--;
  28.         return next.item;
  29.     }
  31.     @Override
  32.     public int size() {
  33.         return size;
  34.     }
  36.     public static class Node {
  37.         private Object item;
  38.         private Node next;
  40.         public Node(Object item, Node next) {
  41.             this.item = item;
  42.             this.next = next;
  43.         }
  44.     }
  45. }

如果是数组实现的队列，则比链表要复杂一些，当尾结点指向数组的最后一个位置时，没有剩余的空间存放数据时，此时该如何处理？通过我们有两种解决方案：

  • 数据搬移：将 head ~ tail 结点的数据搬移到从 0 结点开始。
  • 循环队列：tail 结点从 0 开始循环使用，不用搬移数据。

我们先看一下循环队列

如上图所示，当尾结点指向数组最后一个位置，当 tail 指向数组最后位置时，触发数据搬移，将 head ~ tail 结点的数据搬移到从 0 结点开始。数组队列头结点和尾结点说明：

  • 头结点：head 结点指向第一个数据结点。当 head == tail 时说明队列处于队空状态，直接返回 null。
  • 尾结点：tail 结点指向最后一个数据之后的空结点。当 tail == capcity 时说明队列处于队满状态，需要扩容或进行数据搬移。

根据上述理论代码实现如下：

  1. public class ArrayQueue implements Queue {
  3.     private Object[] array;
  4.     private int capcity;
  5.     // head指向第一个数据结点的位置，tail指向最后一个数据结点之后的位置
  6.     private int head;
  7.     private int tail;
  9.     public ArrayQueue() {
  10.         this.capcity = 1024;
  11.         this.array = new Object[this.capcity];
  12.     }
  14.     public ArrayQueue(int capcity) {
  15.         this.capcity = capcity;
  16.         this.array = new Object[capcity];
  17.     }
  18.     
  19.     /**
  20.      * tail 指向数组最后位置时，需要触发扩容或数组搬移
  21.      * 1. head!=0 说明数组还有剩余的空间，将 head 搬运到队列 array[0]
  22.      * 2. head==0  说明数组没有剩余的空间，扩容
  23.      */
  24.     @Override
  25.     public Queue enqueue(Object obj) {
  26.         if (tail == capcity) {
  27.             if (head == 0) {
  28.                 resize();
  29.             } else {
  30.                 rewind();
  31.             }
  32.         }
  33.         array[tail++] = obj;
  34.         return this;
  35.     }
  37.     @Override
  38.     public Object dequeue() {
  39.         if (head == tail) {
  40.             return null;
  41.         }
  42.         Object obj = array[head];
  43.         array[head] = null;
  44.         head++;
  45.         return obj;
  46.     }
  47.     
  48.     // 将 head 搬运到队列 array[0]
  49.     private void rewind() {
  50.         for (int i = head; i < tail; i++) {
  51.             array[i - head] = array[i];
  52.             array[i] = null;
  53.         }
  54.         tail -=  head;
  55.         head = 0;
  56.     }
  58.     // 扩容
  59.     private void resize() {
  60.         int oldCapcity = this.capcity;
  61.         int newCapcity = this.capcity * 2;
  62.         Object[] newArray = new Object[newCapcity];
  63.         for (int i = 0; i < oldCapcity; i++) {
  64.             newArray[i] = array[i];
  65.         }
  66.         this.capcity = newCapcity;
  67.         this.array = newArray;
  68.     }
  69.     
  70.     @Override
  71.     public int size() {
  72.         return tail - head;
  73.     }
  74. }

说明： 数组队列出队的时间复杂度始终是 O(1)。但入队时要分为三种情况：

  • 有空间：大多数情况，也是最好时间复杂度 O(1)。
  • 没有空间需要数据搬移：执行 n 后触发一次数据搬移，最坏时间复杂度 O(n)。
  • 没有空间需要扩容：执行 n 后触发一次数据搬移，最坏时间复杂度 O(n)。

如果采用摊还分析法，最好时间复杂度 O(1)，最坏时间复杂度 O(n)，摊还时间复杂度为 O(1)。虽然，平均时间复杂度还是 O(1)，但我们能不能不进行数据搬移，直接循环使用数组呢？

循环队列是一种非常高效的队列，我们需要重点掌握它，要能轻松写出无 BUG 的循环队列。

数组队列头结点和尾结点说明：

  • 头结点：head 结点指向第一个数据结点。当 head == tail 时说明队列处于队空状态，直接返回 null。否则在元素出队后，需要重新计算 head 值。
  • 尾结点：tail 结点指向最后一个数据之后的空结点。每次插入元素后重新计算 tail 值，当 tail == head 时说明队列处于队满状态，需要扩容。
  • 元素位置：对数组长度取模 (tail + 1) % length ，所以这种数据为了提高效率，都要求数组长度为 2^n，通过位运算取模 (tail + 1) & (length - 1)。
  1. public class ArrayCircularQueue implements Queue {
  3.     private Object[] array;
  4.     private int capcity;
  5.     // 头结点指向
  6.     private int head;
  7.     private int tail;
  9.     public ArrayCircularQueue() {
  10.         this.capcity = 1024;
  11.         this.array = new Object[this.capcity];
  12.     }
  14.     public ArrayCircularQueue(int capcity) {
  15.         this.capcity = capcity;
  16.         this.array = new Object[capcity];
  17.     }
  19.     @Override
  20.     public Queue enqueue(Object obj) {
  21.         array[tail] = obj;
  22.         if ((tail = (tail + 1) % capcity) == head) {
  23.             resize();
  24.         }
  25.         return this;
  26.     }
  28.     @Override
  29.     public Object dequeue() {
  30.         if (head == tail) {
  31.             return null;
  32.         }
  33.         Object obj = array[head];
  34.         array[head] = null;
  35.         head = (head + 1) % capcity;
  36.         return obj;
  37.     }
  39.     // 不扩容，要先判断能否往数组中添加元素
  40.     public Queue enqueue2(Object obj) {
  41.         if ((tail + 1) % capcity == head) return this;
  42.         array[tail] = obj;
  43.         tail = (tail + 1) % capcity;
  44.         return this;
  45.     }
  47.     // 扩容
  48.     private void resize() {
  49.         // 说明还有空间
  50.         if (head != tail) {
  51.             return;
  52.         }
  53.         int oldCapcity = this.capcity;
  54.         int newCapcity = this.capcity * 2;
  55.         Object[] newArray = new Object[newCapcity];
  56.         for (int i = head; i < oldCapcity; i++) {
  57.             newArray[i - head] = array[i];
  58.         }
  59.         for (int i = 0; i < head; i++) {
  60.             newArray[capcity - head + i] = array[i];
  61.         }
  62.         this.capcity = newCapcity;
  63.         this.array = newArray;
  64.         this.head = 0;
  65.         this.tail = oldCapcity;
  66.     }
  69.     @Override
  70.     public int size() {
  71.         return tail - head;
  72.     }
  73. }

说明： 循环队列关键是判断队空和空满的状态分别进行处理。除开扩容操作，循环队列的入队和出队的时间复杂度都是 O(1)，同时也可以充分利用 CPU 缓存，所以说一种高效的数据结构。

如 JDK 线程池，当线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？我们一般有两种处理策略。

  1. 非阻塞的处理方式，直接拒绝任务请求；
  2. 阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。

每天用心记录一点点。内容也许不重要，但习惯很重要！

版权声明：本文为binarylei原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/binarylei/p/12403643.html