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();
  }
}