队列

HeChuangJun约 1029 字大约 3 分钟

队列介绍

队列是一种线性数据结构，它通过两个主要操作（即入队和出队）来模拟现实世界的队列。
队列是一个有序列表，可以用数组或是链表来实现。遵循先进先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
优先级队列：每个元素都具有一定的优先级。并且可比较，优先级队列中元素的优先级决定了从优先级队列中移除元素的顺序。
索引优先级队列：在优先级队列上支持快速更新和删除键值对。适用于快速更新队列状态
使用场景
- 任何等待线都可模拟队列，例如电影院/银行排队
- 跟踪最近添加的元素
- Web 服务器请求管理，先到先得
- 广度优先搜索 (BFS) 图遍历
优先级队列使用场景
- Dijkstra 最短路径算法的某些实现。
- 任何时候您需要动态获取下一个最佳或下一个最差元素。
- 用于 Huffman 编码（通常用于无损数据压缩）。
- 最佳优先搜索 (BFS) 算法（例如 A*）使用 PQs 连续抓取下一个最有希望的节点。
- 用于最小生成树 (MST) 算法。
算法复杂度
enqueue O(1)
dequeue O(1)
peeking O(1)
contains O(n)
removal O(n)
isEmpty O(1)
contains、removal可能都需要扫描整个链表

基于单向环形带哨兵链表实现的队列(可选)

存在的问题:数组不能复用,使用算法改成环形队列取模解决

public class LinkedListQueue<E>
        implements Queue<E>, Iterable<E> {

    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> head = new Node<>(null, null);
    private Node<E> tail = head;
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;

    {
        tail.next = head;
    }

    public LinkedListQueue() {}

    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        Node<E> added = new Node<>(value, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

基于环形数组实现的队列

循环队列不容易判断队列满和空的情况，因为此时队首指针和队尾指针都指向同一个位置，解决方法如下

添加一个不存储元素的空位区分队列为满时和队列为空时的情况，当( rear + 1 ) % maxSize == front表示队列满，front == tail表示队列空(本例)
附加一个标志位tag，当head赶上tail，队列空，则令tag=0,当tail赶上head，队列满，则令tag=1

有效数字的个数size = (rear+maxSize-front)%maxSize,推导过程,前提条件是rear - front < maxSize

当rear在front后面，size = rear - front, 取模保证size在maxSize范围内(rear - front) % maxSize + maxSize % maxSize = (rear + maxSize - front) % maxSize
当rear在front前面，size = 0到rear+font到尾= (rear-0) + (maxSize - front), 取模保证size在maxSize范围内 (rear + maxSize - front) % maxSize

//ArrayQueue与IntQueue区别是泛型和size，ArrayQueue的大小、空和满状态是根据公式计算的
public class ArrayQueue<T> {
  private Object[] data;
  private int front;
  private int rear;

  public ArrayQueue(int capacity) {
    data = new Object[capacity + 1];// ArrayQueue maximum size is data.length - 1;为了留一个位置判断队满或者队空
    front = 0;
    rear = 0;
  }

  public void offer(T elem) {
    if (isFull()) throw new RuntimeException("Queue is full");
    data[rear++] = elem;//将元素放入 rear 指向的位置，并将 rear 向后移动一位。
    rear = adjustIndex(rear, data.length);
  }

  public T poll() {
    if (isEmpty()) throw new RuntimeException("Queue is empty");
    int tempFront = front;
    front = adjustIndex(++front, data.length);
    return (T) data[tempFront];
  }

  public T peek() {
    if (isEmpty()) throw new RuntimeException("Queue is empty");
    return (T) data[front];
  }

  public int size() { return adjustIndex(rear + data.length - front, data.length); }

  public boolean isEmpty() { return rear == front;}

  public boolean isFull() { return (rear + 1) % data.length == front }

  private int adjustIndex(int index, int size) {//调整索引以保持在数组范围内,相当于取模
    return index % size;//index >= size ? index - size : index;
  }
}