基础数据结构-队列 - 图1

1. 什么是队列

1.1 队列的基本概念

队列是一种特殊的线性表结构，特殊之处在于它只能在队头删除元素，在队尾插入元素，它是一种有操作限制的线性表结构，插入元素称之为入队，删除元素称之为出队，队列中的数据元素被称之为队列元素。队列这种结构非常类似于我们现实生活中，排队买票的场景。
基础数据结构-队列 - 图2

1.2 队列的特点

  • 先进先出（FIFO/First In First Out）。
  • 是一种具有操作限制的线性表。

2. 队列类别

2.1 顺序队列

顺序队列（单向队列），顾名思义就是插入删除都是有顺序的，按照先进先出的规则进行数据的插入与删除，只能在一端插入数据，另一段删除数据。
image.png

2.1.1 基于数组实现单向队列

  1. package com.muzili.queue;
  3. /**
  4.  *
  5.  * @author: muzili(李敷斌)
  6.  * @date: 2021/7/22
  7.  * @version: v0.0.1
  8.  * @description: 基于数组实现队列
  9.  */
  10. public class ArrayQueue<T> implements Queue<T>{
  12.     /**
  13.      * 保存数据的数组
  14.      */
  15.     private T[]data;
  17.     /**
  18.      * 头部索引值
  19.      */
  20.     private int head = 0;
  22.     /**
  23.      * 尾部索引值
  24.      */
  25.     private int tail = 0;
  27.     /**
  28.      * 容量
  29.      */
  30.     private int capcity = 10;
  32.     public ArrayQueue() {
  33.         data = (T[]) new Object[capcity];
  34.     }
  36.     public ArrayQueue(int capcity) {
  37.         this.capcity = capcity;
  38.         data = (T[]) new Object[capcity];
  39.     }
  41.     /**
  42.      * 入队
  43.      *
  44.      * @param item
  45.      */
  46.     public void put(T item) {
  47.         judgeSize();
  48.         data[tail] = item;
  49.         tail++;
  50.     }
  52.     /**
  53.      * 出队
  54.      *
  55.      * @return 元素
  56.      */
  57.     public T poll() {
  58.         if (isEmpty()){
  59.             return null;
  60.         }
  61.         T item = data[head];
  62.         data[head] = null;
  63.         head++;
  64.         return item;
  65.     }
  67.     /**
  68.      * 是否为空
  69.      *
  70.      * @return 是否为空
  71.      */
  72.     public boolean isEmpty() {
  73.         return tail == head;
  74.     }
  76.     /**
  77.      * 判断大小
  78.      * @return
  79.      */
  80.     public void judgeSize(){
  82.         if (tail == capcity){
  83.             if (head > 0){
  84.                 for (int i = 0; i < tail - 1; i++) {
  85.                     data[i] = data[i+head-tail];
  86.                 }
  87.                 if (tail==head){
  88.                     head = 0;
  89.                     tail = 0;
  90.                     return;
  91.                 }
  92.                 tail-=head;
  93.                 return;
  94.             }
  96.             throw new RuntimeException("队列满了~~~");
  97.         }
  98.     }
  100. }

从上述代码分析得出，当head与tail相等时队列为空，当tail与capcity相等并且head等于0时表示队列容量满了。
缺点：

  1. 当tail值与capcity时相等并且head大于0时需要对数组进行移动操作。这里的时间复杂度是O(n)，平均复杂度为O(2)==> (n*2)/n，因为如果数组容量是1000，那么前999次都是为O(1)，只有第1000次是O(n)

    2.1.2 基于链表实现单向队列

    ```java package com.muzili.queue;

import com.muzili.list.LinkedList;

/*

  • @author: muzili(李敷斌)
  • @date: 2021/7/22
  • @version: v0.0.1

  • @description: 基于链表实现队列 */ public class LinkedListQueue implements Queue{

    private LinkedList dataList = new LinkedList();

    /**

    • 入队 *

    • @param item */ public void put(T item) { dataList.addLast(item); }

      /**

    • 出队 *

    • @return 元素 */ public T poll() {

      if (isEmpty()){

      1.  return null;

      } LinkedList.Node first = dataList.getFirst(); dataList.removeFirst(); return first.getData(); }

      /**

    • 是否为空 *
    • @return 是否为空 */ public boolean isEmpty() { return dataList.getSize() == 0; } } ```

      2.2 循环队列

      循环队列，顾名思义就是每一端都可以插入元素。
      image.png ```java package com.muzili.queue;

/*

  • @author: muzili(李敷斌)
  • @date: 2021/7/22
  • @version: v0.0.1

  • @description: 循环队列 */ public class CircularQueue implements Queue{

    /**

    • 保存数据的数组 */ private T[]data;

      /**

    • 头部索引值 */ private int head = 0;

      /**

    • 尾部索引值 */ private int tail = 0;

      /**

    • 容量 */ private int capcity = 10;

      public CircularQueue() { data = (T[]) new Object[capcity]; }

      public CircularQueue(int capcity) { this.capcity = capcity; data = (T[]) new Object[capcity]; }

      /**

    • 入队 *

    • @param item */ public void put(T item) { judge(); data[tail] = item; tail = (tail + 1) % capcity; }

      private void judge() {

      if ((tail + 1) % capcity == head){

      1.  throw new RuntimeException("队列满了哦~~~");

      }

      }

      /**

    • 出队 *

    • @return 元素 */ public T poll() {

      if (isEmpty()){

      1.  return null;

      } T item = data[head]; head = (head + 1) % capcity; return item; }

      /**

    • 是否为空 *
    • @return 是否为空 */ public boolean isEmpty() { return tail == head; } } ``` 在循环队列中，tail等于head表示队列为空队列，当然tail等于head时也还可能是队列满了，但是为了避免这种情况，一般我们都会以MaxSize-1的大小作为队列的容量，当队列中的元素达到MaxSize-1时就表示队列满了，所以可以避免tail与head相等时即可以表示队列为空也可以表示队列满了的情况，当（tail+1）% capcity 等于head时表示队列满了。

      2.3 优先队列

      优先队列指的就是，允许后进的元素先出队，JDK中的优先队列实现为AsLIFOQueue。

      2.4 阻塞队列

      阻塞队列，指的就是在队列的基础上添加了阻塞的操作，比如当队列为空的时候，元素出队的操作就会被阻塞，在队列中有元素时会被唤起，当队列满了的时候，入队操作被阻塞。
      在阻塞队列中，一般会有消费者和生产者这样的概念，消费者消费队列中的元素，生产者向队列中产出元素。

      2.5 延时队列

      延时队列，就是在队列的基础上为元素添加了延时概念，延时队列可以被看做是一种优先队列，延时时间先过完的元素可以优先出队。