数据结构学习笔记 - 04 队列

介绍

队列的的操作也是数组的子集，不同的是，队列只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。

队列实现

将队列定义为一个接口：

public interface Queue<E> {

    /**
     * 入队。
     * 
     * @param e 入队的元素。
     */
    void enqueue(E e);

    /**
     * 出队。
     * 
     * @return 出队的元素。
     */
    E dequeue();

    /**
     * 获得队首元素。
     * 
     * @return 队首的元素。
     */
    E getFront();

    /**
     * 获得队列中元素的个数。
     * 
     * @return 元素的个数。
     */
    int getSize();

    /**
     * 查看队列是否为空。
     * 
     * @return 队列是否为空。
     */
    boolean isEmpty();
}

使用动态数组实现队列：

/**
 * ArrayQueue
 * 
 * 类似栈的实现，这里也使用动态数组对队列进行一个实现。
 * 
 * 这个队列中的五个方法复杂度：
 * void enqueue(E)     O(1) 均摊
 * E dequeue()         O(n)
 * E getFront()        O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 * 可以看到，数组实现的队列最大问题就是出队的复杂度是 O(n)
 */
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
        array = new Array<>();
    }

    /**
     * 队列的元素个数。
     */
    @Override
    public int getSize() {
        return array.getSize();
    }

    /**
     * 队列元素是否为空。
     */
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 查看实现这个队列的这个动态数组当前的容积。
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 入队。
     */
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    /**
     * 出队。
     */
    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    /**
     * 获取队首元素。
     */
    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }

        res.append("] tail");

        return res.toString();
    }
}

使用循环队列解决数组队列出队复杂度高的问题：

/**
 * LoopQueue
 * 数组队列的问题在于，出队的时间复杂度过高，导致如果队列元素特别多的情况下，出队就比较耗时。
 * 循环队列可以解决这一问题。
 * 
 * 这个队列中的五个方法复杂度：
 * void enqueue(E)     O(1) 均摊
 * E dequeue()         O(1) 均摊
 * E getFront()        O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front, tail;
    private int size;

    @SuppressWarnings("unchecked")
    public LoopQueue(int capacity) {

        // 创建的数组容量比用户期望的多一个，因为循环队列中，我们会有意识的浪费掉一个空间。
        // 因为我们通常认为 front == tail 的时候是队列为空，对于循环队列，我们如果不让出一个空间，那么这个表达式也有可能是队列元素占满的情况。
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    /**
     * 循环队列创建的数组中，我们会有意识地浪费掉一个空间。
     * 
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 循环队列使用 front == tail 来判断元素为空，这也是为什么创建数组需要多一个空间。
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 获得队列元素的个数。
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 入队。
     */
    @Override
    public void enqueue(E e) {

        // 判断队列是否满了
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 出队。
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        // 缩容。
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return data[front];
    }

    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];

        // 第一种遍历循环队列的所有元素的方式。
        for (int i = 0; i < size; i++) {
            // 当扩容或者缩容的时候，原本 front 不为 0 的队列被重新规整为 front 为 0 的队列了
            newData[i] = data[(i + front) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 打印该类的显示字符串。
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("QUeue: size = %d, capacity = %d\n", size, getCapacity()));
        res.append("front [");

        // 第二种遍历循环队列中所有元素的方式。
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

使用链表实现队列：

/**
 * LinkedListQueue
 * 
 * 这里我们使用链表实现队列。
 * 由于队列需要从一端添加，另一端删除，对于链表来说，我们需要给它先添加一个 tail 标记，类似 head 标记那样，这样我们从末尾添加元素就也是 O(1)
 * 级别的了。
 * 但是有一个问题是，即使添加了 tail 标记，在从尾部删除一个元素的时候，我们无法快速找到 tail 之前的那个节点。
 * 
 * 所以合理的设计队列的方式就是，从尾部只负责添加元素，在链表的头部负责删除元素，也就是出队。
 * 
 * 这里我们设计的链表就不使用 dummyHead 了，但是要注意链表为空的情况。
 */
public class LinkedListQueue<E> implements Queue<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        // public Node() {
        //     this(null);
        // }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if (head == null) {
            tail = null;
        }
        size--;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }

        return head.e;
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }

        res.append("NULL tail");

        return res.toString();
    }
}