04-队列

队列

• 队列对应的操作，属于是数组的子集，因为只能从一端添加元素（队尾），从另一端取出元素（队头）
• 队列是一种先进先出的数据结构（FIFO），用户无法获取中间的元素
• 由于栈的实现方式不仅是一种，所以写成接口的形式，方便多种实现

/**
 * @InterfaceName: Queue
 * @Description: 自定义队列接口
 */
public interface Queue<E> {
  /**
   * @MethodName: enqueue
   * @Description: 将元素从队尾入队
   * @Param element: 入队元素
   * @Return void
   */
  Void enqueue (E element);

  /**
   * @MethodName: dequeue
   * @Description: 将元素从队头出队
   * @Return E
   */
  E dequeue ();

  /**
   * @MethodName: getFront
   * @Description: 获取队头元素
   * @Return E
   */
  E getFront ();

  /**
   * @MethodName: getSize
   * @Description: 获取队列中的元素个数
   * @Return int
   */
  Int getSize ();

  /**
   * @MethodName: isEmpty
   * @Description: 判断栈是否为空
   * @Return boolean
   */
  Boolean isEmpty ();
}

基于动态数组的队列

/**
 * @ClassName: ArrayQueue
 * @Description: 基于自定义数组实现的自定义队列
 */
public class ArrayQueue<E> implements Queue<E> {
  private Array<E> array;

  /**
   * @MethodName: ArrayQueue
   * @Description: 根据用户需求创建指定大小容量的队列
   * @Param capacity: 用户指定的容量
   */
  Public ArrayQueue (int capacity) {
    this. Array = new Array<>(capacity);
  }

  /**
   * @MethodName: ArrayQueue
   * @Description: 为用户设置默认的容量大小，为 10
   */
  Public ArrayQueue () {
    this. Array = new Array<>(10);
  }

  /**
   * @MethodName: enqueue
   * @Description: 入队操作实现
   * @Param element: 入队元素
   * @Return void
   */
  @Override
  Public void enqueue (E element) {
    This.Array.Add (this.GetSize (), element);  //直接向数组尾部添加元素
  }

  /**
   * @MethodName: dequeue
   * @Description: 出队操作实现
   * @Return E
   */
  @Override
  Public E dequeue () {
    Return this.Array.Remove (0);  //直接删除数组头部元素
  }

  /**
   * @MethodName: getFront
   * @Description: 查看队头元素操作实现
   * @Return E
   */
  @Override
  Public E getFront () {
    Return this.Array.Get (0); //直接返回数组第一个元素
  }

  /**
   * @MethodName: getSize
   * @Description: 查看队列中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this.Array.GetSize ();  //返回当前数组中元素的个数
  }

  /**
   * @MethodName: isEmpty
   * @Description: 查看队列是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this.Array.IsEmpty ();  //返回当前数组是否为空
  }

  @Override
  Public String toString () {
    StringBuilder sb = new StringBuilder ();
    For (int i = 0; i < this.Array.GetSize (); i++) {
      Sb.Append (array.Get (i));
      If (i != this.Array.GetSize () - 1) {
        Sb.Append (",");
      }
    }
    Return "ArrayQueue{" +
        "Queue= front [" + sb.ToString () +
        "] tail}";
  }
}

基于静态数组的循环队列

循环机制：在添加元素时将循环增量的值与数组长度取余就会自动循环，比如：

String[] arr = new String[3]; //只能承载三个元素的数组
For (int i = 2; i < 4; i++) {
  Arr[i % arr. Length] = "i=" + i;  //将循环增量与数组长度取余
}
System.Out.Println (Arrays.ToString (arr)); //[i=3, null, i=2]
//或，这两种方式的区别在于循环增量一个是一直递增，和一个是永远在一定范围内
String[] arr = new String[3]; //只能承载三个元素的数组
For (int i = 2; i != 1; i = (i + 1) % arr. Length) {  //将循环增量与数组长度取余
  Arr[i] = "i=" + i;
}
System.Out.Println (Arrays.ToString (arr)); //[i=0, null, i=2]

要知道基于数组的普通队列中出队操作是从数组头部删除元素，就需要遍历所有元素将元素向前移动，导致出队效率极低，若在删除队头元素不进行所有元素的移动，其实数组中元素的位置的前后关系还是那样，根本没有必要移动所有元素的位置也可以，这时只需要将当前队头和队尾是谁告诉用户即可（当队头和队尾指向相同时说明队列为空），此时前面元素出队会导致空间浪费，所以采用循环插入机制来避免，这就是循环队列

循环队列又出现了新问题，就是当队列满时首位指向相同，同时当队列为空时首位指向也相同，所以需要让队列永远不要填满整个数组，而是预留出一个位置，当还有一个位置时，就认为队列已经满了，这样就可以避免队满和队空判断条件一致，这时由于基于的是静态数组，所以扩容缩容操作要自己实现（记着改变头尾指针和修改指针的顺序）

• 若队头和队尾指向相同时，队列为空
• 若队尾加 1 和队尾指向相同时，队列为满，但是要注意若此时队尾加 1 需要循环带到队头，所以需要与数组长度取余在进行等值判断

/**
 * @ClassName: LoopQueue
 * @Description: 基于自定义数组实现的自定义队列
 */
public class LoopQueue<E> implements Queue<E> {
  Private E[] data; //存储队列元素的数组，和数组的容量使用 data. Length-1 表示，因为要空一个位置
  Private int front, tail; //队头指针和队尾指针

  /**
   * @MethodName: LoopQueue
   * @Description: 根据用户需求创建指定大小容量的队列
   * @Param capacity: 用户指定的容量
   */
  Public LoopQueue (int capacity) {
    This. Data = (E[]) new Object[capacity + 1]; //由于要预留一个空间，所以此操作需要对用户屏蔽
    This. Front = 0;  //初始头指针指向 0
    This. Tail = 0;  //初始尾指针指向 0
  }

  /**
   * @MethodName: LoopQueue
   * @Description: 为用户设置默认的容量大小，为 10
   */
  Public LoopQueue () {
    This (10);
  }

  /**
   * @MethodName: enqueue
   * @Description: 入队操作实现
   * @Param element: 入队元素
   * @Return void
   */
  @Override
  Public void enqueue (E element) {
    If ((this. Tail + 1) % this. Data. Length == this. Front) {
      //若队列为满（有可能尾指针要循环所以要取余），则扩容 2 倍
      Resize ((this. Data. Length - 1) * 2);
    }
    This. Data[this. Tail] = element; //将元素入队
    This. Tail = (this. Tail + 1) % this. Data. Length; //头指针向后循环移动
  }

  /**
   * @MethodName: dequeue
   * @Description: 出队操作实现
   * @Return E
   */
  @Override
  Public E dequeue () {
    If (this.IsEmpty ()) { //若队列为空则抛出异常
      Throw new IllegalArgumentException ("Dequeue failed, Queue is empty");
    }
    E element = this. Data[this. Front]; //将出队元素暂存
    This. Data[this. Front] = null;  //同样需要将位置职位空，这样垃圾回收机制会更快回收
    This. Front = (this. Front + 1) % this. Data. Length; //头指针循环移动
    If ((this. Data. Length - 1) / 2 == this.GetSize () && (this. Data. Length - 1) / 2 != 0) {
      //若当前数组容量过大就缩容一半
      This.Resize ((this. Data. Length - 1) / 2);
    }
    Return element; //返回出队元素
  }

  /**
   * @MethodName: getFront
   * @Description: 查看队头元素操作实现
   * @Return E
   */
  @Override
  Public E getFront () {
    Return this. Data[this. Front];  //返回队头元素
  }

  /**
   * @MethodName: getSize
   * @Description: 查看队列中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this. Tail >= this. Front ? //如果头指针在前，尾指针在后
        This. Tail - this. Front : //这之间的元素是队列中元素
        This. Data. Length - (this. Front - this. Tail); //否则两边元素是队列元素
  }

  /**
   * @MethodName: isEmpty
   * @Description: 查看队列是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this. Front == this. Tail;
  }

  /**
   * @MethodName: resize
   * @Description: 将 data 扩容指定大小
   * @Param capacity: 指定的大小
   * @Return void
   */
  Private void resize (int capacity) {
    E[] newData = (E[]) new Object[capacity + 1]; //创建新数组，需要让该数组容量多一个，因为要留出空位
    For (int i = 0; i < this.GetSize (); i++) {
      //为了从 0 开始遍历整个队列，所以采用第一种循环机制的方式
      //这样整个队列元素就会靠数组头部对齐
      NewData[i] = this. Data[(this. Front + i) % this. Data. Length];
    }
    This. Tail = this.GetSize (); //修改尾指针
    This. Front = 0;  //修改头指针
    // 注意这两个的顺序，由于 getSize () 方法中要使用头指针进行计算，若提前修改头指针会导致错误
    This. Data = newData;  //更换容器数组
  }

  @Override
  Public String toString () {
    StringBuilder sb = new StringBuilder ();
    For (int i = this. Front; i != this. Tail; i = (i + 1) % this. Data. Length) {
      //从队列头遍历到尾部，采用第一种循环机制
      Sb.Append (this. Data[i]);
      If (i != this. Tail - 1) { //若当前尾指针的前一次与当前头指针的 i 重合时为最后一个元素
        Sb.Append (",");
      }
    }
    Return "LoopQueue{" +
        "capacity=" + (this. Data. Length - 1) +
        ", Queue= front [" + sb +
        "] tail}";
  }
}

基于单向链表的队列

由于队列是对头部删除和对尾部删除的操作，而链表仅对头部操作效率较高，若也为尾部也增加一个指针，此时对尾部操作也就不再需要遍历整个链表了，但是就不能在复用之前的链表了，要从新实现一个带有尾指针的链表，新实现的链表能完成队列的操作即可，无需多余的实现其他功能

但是要注意的是，只是添加尾部指针仅仅针对添加操作，因为删除操作是要找到要删除的节点的前一个节点，由于单向链表中并没有记录前一个节点的指针，所以无法达到删除尾节点的目的；对于队列来说，能够添加节点就足够了，因为只是一侧添加（入队）一侧删除（出队），将链表尾部当做队列头部即可

/**
 * @ClassName: LinkedListQueue
 * @Description: 基于单向链表的自定义队列，由于在单向链表中增加了一个尾指针，所以要从新实现一下链表
 */
public class LinkedListQueue<E> implements Queue<E> {
  Private class Node { //私有的内部类，不希望暴漏给外部使用，使用该类创建节点对象并进行链表的组装
    Private E data; //存储节点数据
    Private Node next;  //存储下一个节点

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，指定数据和下一个节点
     * @Param data: 数据
     * @Param next: 下一个节点
     */
    Public Node (E data, Node next) {
      This. Data = data;
      This. Next = next;
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，只指定数据，下一个节点为 null，即最后一个节点
     * @Param data:
     */
    Public Node (E data) {
      This (data, null);
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，此时数据和下一个节点都是 null，即最后一个节点并且数据也是 null
     */
    Public Node () {
      This (null, null);
    }

    @Override
    Public String toString () {
      Return data.ToString (); //只打印数据，屏蔽掉节点指针
    }
  }

  Private Node head, tail;  //头尾节点指针
  // 队头指针是 tail，队尾指针是 head，是反的
  // 队头指针指向链表尾部，而队尾指针指向链表头部
  Private int size; //链表长度

  /**
   * @MethodName: LinkedListQueue
   * @Description: 创建一个队列
   */
  Public LinkedListQueue () {
    This. Head = null;
    This. Tail = null;
    This. Size = 0;
  }

  /**
   * @MethodName: enqueue
   * @Description: 入队操作实现
   * @Param element: 入队元素
   * @Return void
   */
  @Override
  Public void enqueue (E element) {
    If (this. Tail == null) {  //若当前队头没有节点
      This. Tail = new Node (element);  //创建节点，并使得队头指针指向当前节点
      This. Head = this. Tail;  //只有一个节点时，队头尾指针应该指向相同
    } else {  //若当前队列有节点
      This. Tail. Next = new Node (element); //当前队头元素的 next 指向新节点，这样队头就一个是新节点
      This. Tail = this. Tail. Next; //新节点已经插入到链表，所以要改变队头指针指向新节点
    }
    This. Size++;  //入队后队列中的元素加 1
  }

  /**
   * @MethodName: dequeue
   * @Description: 出队操作实现
   * @Return E
   */
  @Override
  Public E dequeue () {
    If (this.IsEmpty ()) { //若当前队列为空，出队抛出异常
      Throw new IllegalArgumentException ("Dequeue failed, Queue is empty");
    }
    Node delNode = this. Head; //暂存当前要删除的队尾节点
    This. Head = this. Head. Next; //改变队尾指针为下一个节点，即跳过要删除的节点
    //若是最后一个节点时，队尾指针自动会指向 null，但是队头指针不会，所以需要判断一下，这里是一个坑
    DelNode. Next = null;  //将要删除节点与链表脱离，方便垃圾回收机制回收
    If (this. Head == null) {  //若删除的节点是最后一个节点时
      This. Tail = null; //队首尾指针应该都指向空
    }
    This. Size--;  //出队后队列中的元素减 1
    Return delNode. Data;  //返回删除的节点数据
  }

  /**
   * @MethodName: getFront
   * @Description: 查看队头元素操作实现
   * @Return E
   */
  @Override
  Public E getFront () {
    If (head == null) {
      Throw new IllegalArgumentException ("Get failed, Queue is empty");
    }
    Return this. Tail. Data;
  }

  /**
   * @MethodName: getSize
   * @Description: 查看队列中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this. Size;
  }

  /**
   * @MethodName: isEmpty
   * @Description: 查看队列是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this. Size == 0;
  }

  @Override
  Public String toString () {
    StringBuilder sb = new StringBuilder ();
    Node cur = this. Head; //存储当前节点的指针，从队尾（链表头）开始遍历
    While (cur != null) { //若当前节点已经为 null，说明当前节点指针已经指到了末尾
      Sb.Append (cur. Data + ",");
      Cur = cur. Next; //当前节点指针后移
    }
    If (sb.Length () > 0) {  //若队列中有元素
      Sb.DeleteCharAt (sb.Length () - 1); //将最后那个多余的逗号删除
    }
    Return "LinkedList{" +
        "Queue=front [" + sb +
        "] tail}";
  }
}

基于堆的优先队列

与普通队列入对是相同的，出队时选择优先级较高（较大或较小）的元素先出队，而不是先进先出，若基于线性结构来实现优先队列，则需要在入队时对元素排序或出队时扫描每个元素找出最大值，时间复杂度较高

堆的堆顶就是全部元素中最大（最小）的元素，在添加和删除时无需将所有元素都遍历一遍，所以使用堆来实现优先队列时间复杂度较低

/**
 * @ClassName: PriorityQueue
 * @Description: 基于堆实现的优先队列
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
  private Heap<E> heap;

  /**
   * @MethodName: PriorityQueue
   * @Description: 为用户设置默认的容量大小，为 10
   */
  Public PriorityQueue () {
    this. Heap = new Heap<>(10);
  }

  /**
   * @MethodName: PriorityQueue
   * @Description: 根据用户需求创建指定大小容量的队列
   * @Param capacity: 用户指定的容量
   */
  Public PriorityQueue (int capacity) {
    this. Heap = new Heap<>(capacity);
  }

  /**
   * @MethodName: enqueue
   * @Description: 入队操作实现
   * @Param element: 入队元素
   * @Return void
   */
  @Override
  Public void enqueue (E element) {
    This.Heap.Add (element);
  }

  /**
   * @MethodName: dequeue
   * @Description: 出队操作实现
   * @Return E
   */
  @Override
  Public E dequeue () {
    Return this.Heap.Remove ();
  }

  /**
   * @MethodName: getFront
   * @Description: 查看队头元素操作实现
   * @Return E
   */
  @Override
  Public E getFront () {
    Return this.Heap.Peek ();
  }

  /**
   * @MethodName: getSize
   * @Description: 查看队列中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this.Heap.GetSize ();
  }

  /**
   * @MethodName: isEmpty
   * @Description: 查看队列是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this.Heap.IsEmpty ();
  }
}