数据结构-队列

Queue

队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许 在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。向队尾插入元素称为进队或入队，新元素 入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成 为新的队首元素。 由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，也就是说先进队的元素必然先离队，所以称队列为先进先出表（First In First Out,简称 FIFO）。

image.png

顺序存储结构

ArrayQueue

在队列的顺序存储实现中，我们可以将队列当作一般的表用数组加以实现，但这样做的 效果并不好。尽管我们可以用一个指针 last 来指示队尾，使得 enqueue 运算可在Ο(1)时间内 完成，但是在执行 dequeue 时，为了删除队首元素，必须将数组中其他所有元素都向前移动 一个位置。这样，当队列中有 n 个元素时，执行 dequeue 就需要Ο(n)时间。为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组 A[0.. capacity-1]中的单元不是排成一行，而是围成一个圆环

ArrayQueue

public class ArrayQueue<T> extends AbstractList<T> {
    public ArrayQueue(int capacity) {
        this.capacity = capacity + 1;
        this.queue = newArray(capacity + 1);
        this.head = 0;
        this.tail = 0;
    }

    public void resize(int newcapacity) {
        int size = size();
        if (newcapacity < size)
            throw new IndexOutOfBoundsException("Resizing would lose data");
        newcapacity++;
        if (newcapacity == this.capacity)
            return;
        T[] newqueue = newArray(newcapacity);
        for (int i = 0; i < size; i++)
            newqueue[i] = get(i);
        this.capacity = newcapacity;
        this.queue = newqueue;
        this.head = 0;
        this.tail = size;
    }

    @SuppressWarnings("unchecked")
    private T[] newArray(int size) {
        return (T[]) new Object[size];
    }

    public boolean add(T o) {
        queue[tail] = o;
        int newtail = (tail + 1) % capacity;
        if (newtail == head)
            throw new IndexOutOfBoundsException("Queue full");
        tail = newtail;
        return true; // we did add something
    }

    public T remove(int i) {
        if (i != 0)
            throw new IllegalArgumentException("Can only remove head of queue");
        if (head == tail)
            throw new IndexOutOfBoundsException("Queue empty");
        T removed = queue[head];
        queue[head] = null;
        head = (head + 1) % capacity;
        return removed;
    }

    public T get(int i) {
        int size = size();
        if (i < 0 || i >= size) {
            final String msg = "Index " + i + ", queue size " + size;
            throw new IndexOutOfBoundsException(msg);
        }
        int index = (head + i) % capacity;
        return queue[index];
    }

    public int size() {
        // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
        int diff = tail - head;
        if (diff < 0)
            diff += capacity;
        return diff;
    }

    private int capacity;
    private T[] queue;
    private int head;
    private int tail;
}

链式存储结构

队列的链式存储可以使用单链表来实现。为了操作实现方便，这里采用带头结点的单链 表结构。根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。除了链表头 结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操 作的实现。为此一共设置两个指针，一个队首指针和一个队尾指针，如图所示，队首针指(front)向队首元素的前一个结点，即始终指向链表空的头结点; 队尾指针(rear)指向队列当前队尾元素所在的结点。当队列为空时，队首指针与队尾指针均指向空的头结点。在Java中没有显式的指针类型，然而实际上对象的访问就是使用指针来实现的，即在Java中是使用对象的引用来替代指针的。

LinkedQueue node

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

public boolean offer(E e) {
        return add(e);
    }
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

   void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    public E pop() {
        return removeFirst();
    }

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

}