Java 数据结构 队列

Java 数据结构 队列

今天是春分, 小学入学的具体政策也出来了. 今年这个摇号还真是让人头大. 队列的思想这里就不赘述了, 其核心是先进先出, 像现实中的队伍一样, 从一侧添加数据, 从另外一侧取走数据. 队列的尾和头就和现实中的一样, 添加数据的一侧叫做尾(back), 取出数据的一侧叫做头(front). 队列的接口

今天是春分, 小学入学的具体政策也出来了. 今年这个摇号还真是让人头大. 队列的思想这里就不赘述了, 其核心是先进先出, 像现实中的队伍一样, 从一侧添加数据, 从另外一侧取走数据. 队列的尾和头就和现实中的一样, 添加数据的一侧叫做尾(back), 取出数据的一侧叫做头(front).
  1. 队列的接口
  2. 基于链表实现队列
  3. 基于数组实现队列
  4. 改进的数组实现队列
  5. 用循环链表实现队列
  6. Java提供的队列 - LinkedList

队列的接口

队列的接口, 可以用栈的接口来类比, 栈是从同一侧放入数据和取出数据, 队列是在两端做这两个事情. 一般来说队列无需查找操作, 向队列中添加数据叫做入队(enqueue), 取出一项叫做出队(dequeue), 获取队列最前端的项目的操作叫做取值(getFront).有了栈的经验, 可以很容易的规定队列的接口如下:
public interface QueueInterface<T> {

    void enqueue(T entry);

    T dequeue();

    T getFront();

    boolean isEmpty();

    void clear();

}
回忆一下之前的栈和包, 我们使用了最基础的数据结构也就是数组, 和自行编写的基于面向对象的最基本的结构链表, 实现了栈. 这次也还是可以基于这些结构来实现.

用链表实现队列

还记得上一篇文章里的带有合并功能的链表吗, 其实已经有了一个尾引用, 可以从尾端添加数据, 由于栈是一端添加一端删除. 现在已经有了从链表头部删除数据的方法. 不过我们那个链表已经带有了很多其他功能, 比如排序, 在目前的简单队列中是无需考虑的. 因此我们来重新编写一个队列. 先搭好类结构, 链表需要使用内部类Node, 这个依然沿用原来的Node类, 然后需要一个头引用一个尾引用.
public class LinkedQueue<T> implements QueueInterface<T> {

    private class Node {
        private T data;
        private Node next;

        public Node(T data) {
            this(data, null);
        }

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    private Node firstNode;
    private Node lastNode;

    public LinkedQueue() {
        this.firstNode = null;
        this.lastNode = null;
    }
}
在最开始的时候, 队列为空, 头尾节点的引用都为null, 所以构造器中将其设置为null, 当然新创建域不赋值的话本来就是null, 这其实是多余的, 不过语义更加明晰. 之后来依次实现接口中的方法. 先是入队方法, 注意这里我们是从尾部插入元素, 从头部弹出. 入队的时候要考虑操作头尾两个节点. 由于一开始队列是空的, 插入第一个元素之后, 头尾节点应该都指向这个元素. 如果队列不为空, 由于是在尾部插入, 因此更改尾节点的next指向新节点, 再移动尾节点引用到最新的节点即可. 基于这个逻辑, 可以编写如下的方法:
@Override
public void enqueue(T entry) {
    //创建一个新节点
    Node newNode = new Node(entry);

    //由于是尾部插入, 不管如何lastNode都要等于newNode, 所以可以放在判断语句之外
    if (isEmpty()) {
        //为空要同时更新首尾节点
        firstNode = newNode;
    } else {
        //不为空则只需要更新尾节点即可
        lastNode.next = newNode;
    }
    lastNode = newNode;

}
然后是出队方法, 既然是从尾部添加元素, 很显然出队需要从头部出队. 这里在出队完毕之后需要加一个判断, 即是否为空, 为空的话需要额外修改尾节点, 如果不为空, 则尾节点无需变动. 这里还有一个细节, 就是队列为空怎么办, 可以选择报错, 也可以选择返回null. 我们这里选择返回null. 既然如此, 说明我们的队列不允许入队null. 因此在入队方法那里也需要更新一下,如果入队的值是null, 就抛个异常, 这里就省略了.
@Override
public T dequeue() {
    //获取首节点
    T result = null;

    //队列不为空的话获取第一个节点的数据, 然后将firstNode指向其next, 标准的从链表头部删除元素的操作
    if (!isEmpty()) {
        Node target = firstNode;
        firstNode = firstNode.next;
        target.next = null;
        result = target.data;
        //删除结束之后, 还要再看一眼链表是否为空, 如果为空说明刚删除了唯一一个元素, 此时lastNode还指向那个元素, 需要将其设置为null.
        if (firstNode == null) {
            lastNode = null;
        }
    }
    return result;
}
这个方法也很简单, 在完成了标准的删除链表首节点的操作之后, 只要检查一下此时firstNode的状态, 如果指向null说明删干净了, 要把lastNode也设置为null. 如果没删干净就不用修改lastNode. 剩下的方法就比较简单了, getFront做一个简单的判断:
@Override
public T getFront() {
    if (isEmpty()) {
        return null;
    } else {
        return firstNode.data;
    }
}
isEmpty()判断两个头尾节点都是null即可, 其实通过逻辑可以发现, :
@Override
public boolean isEmpty() {
    return firstNode == null && lastNode == null;
}
clear方法直接清空头尾引用即可:
    @Override
    public void clear() {
        firstNode = null;
        lastNode = null;
    }
编写完了可以回头来看一看这样一个队列的各种操作. 可以看到, 无论是入队还是出队, 由于有了头尾指针, 其操作都是常数, 与队列长度无关. 其他方法也是类似.

基于数组实现队列

用数组实现队列首先就有一个问题, 就是数组定长的情况下, 假如从数组的尾部添加数据, 头部拿走数据, 则数据的整个可用空间会越来越小. 如果数组不定长, 即使扩大数组长度, 也是一样. 这就要求要有一个方法, 可以充分利用数组的空间. 于是就有了循环队列这一说. 很显然, 与链表一样, 可以用两个索引来指向队列的开头元素与结尾元素. 但是既然数组头部会被清空, 那么就可以来重新再其中放入数据. 所以我们只需要让两个索引循环即可, 即如果超过了数组的限界, 就从0开始. 不过在开始之前, 要想一想什么时候队列为空或者满了. 想象一个5个长度的数组, 一开始没有数据, 为了表示此种特殊情况, 可以人为规定比如都等于-1, 此时firstIndex=lastIndex, 然后放入1个东西, 之后firstIndex=lastIndex=0. 之后不断放入新东西, 放入2个东西后, lastIndex=1; 放入3个东西后, lastIndex=2 ... 放入5个东西之后, lastIndex会指向4. 此时队列已经满了. 按照循环队列的理论, 如果此时数组头部空出来了, 比如从索引0处拿走了一个东西, 那么lastIndex的下一个值应该是0. 不过此时还没有拿东西, 所以可以发现, 此时 firstIndex = Mod(lastIndex+1). 现在放满了, 来删除数据, 首先删除第一个, firstIndex要移动到下一个位置, 也就是索引1的位置, 然后删除第二个, firstIndex要移动到下一个索引的位置, 即2...删除第四个之后, firstIndex=4. 此时数组中还有一个元素, 将其删除之后, 很显然, firstIndex也必须移动到0. 此时队列为空, 然后可以发现firstIndex = 0, lastIndex=4, 两者的关系依然是 firstIndex = Mod(lastIndex+1). 结果发现, firstIndex = Mod(lastIndex+1), 这种情况同时可能表示队列满或者空, 这就给只使用两个索引的循环队列带来了问题. 立刻能想到的办法是, 对队列中的元素进行计数, 一旦满, 下一次插入会触发一个操作, 增加数组长度, 然后将原来队列中的内容按照次序复制到新队列; 一旦计数到达0, 强行将firstIndex和lastIndex设置为-1, 将数组也恢复到一个初始长度. 按照这个思路, 可以先写出来一个队列:
/**
 * 带有计数器的队列类
 */
public class ArrayQueueWithCounter<T> implements QueueInterface<T> {

    /**
     * 数组初始长度, 一开始队列的容量是16, 上限是10000
     */
    private int length = 8;
    private static int MAX_SIZE = 17;

    //数组中已经放入的元素个数
    private int count;

    /**
     * 用于表示队列空的特殊情况, 即指向队列头和尾的索引都是-1
     */
    private int firstIndex;
    private int lastIndex;

    private Object[] array;

    @SuppressWarnings("unchecked")
    public ArrayQueueWithCounter() {
        count = 0;
        firstIndex = -1;
        lastIndex = -1;
        array = (T[]) new Object[length];
    }

    /**
     * 入队的方法.当队列为空的时候, 固定将项目添加在第一项, 然后设置firstIndex和lastIndex都为0
     * //不为空的情况下, 检测长度有没有已经满了. 已经满了, 扩大数组长度, 不满则无需扩大.
     * @param entry 要进入队列的项
     */
    @Override
    public void enqueue(T entry) {

        if (isEmpty()) {
            array[0] = entry;
            firstIndex = 0;
            lastIndex = 0;
        } else {
            //满了就需要扩容
            if (count == length) {
                //无法扩容就抛异常
                increaseCapacity();
            }

            //添加一项并将lastIndex指向那一项, 要对lastIndex取模
            lastIndex = (lastIndex + 1) % length;
            array[lastIndex] = entry;
        }
        count++;
    }


    /**
     * 出队方法. 如果队列空就返回null.
     * 如果不空,先要获取队列头的元素, 并数组对应位置清空, 之后根据队列长度判断是否要恢复到原始状态
     * @return 返回出队的项
     */
    @Override
    @SuppressWarnings("unchecked")
    public T dequeue() {

        if (isEmpty()) {
            return null;
        } else {
            T result = (T) array[firstIndex];
            array[firstIndex] = null;
            //只有一项, 获取之后, 将全部参数重新恢复到初始.
            if (count == 1) {
                clear();
            } else {
                //超过一项, 弹完之后, 应该将firstIndex向后移动一个位置
                firstIndex = (firstIndex + 1) % length;
                count--;
            }
            return result;
        }
    }

    /**
     * 查看队列头部的方法. 很简单.
     * @return 返回队列头部的项
     */
    @Override
    @SuppressWarnings("unchecked")
    public T getFront() {
        if (isEmpty()) {
            return null;
        } else {
            return (T)array[firstIndex];
        }
    }

    /**
     * 其实只需要判断这三者的任何一个即可.
     * @return 如果空返回True
     */
    @Override
    public boolean isEmpty() {
        return firstIndex == -1 && lastIndex == -1 && count == 0;
    }

    /**
     * 清除队列的方法, 重置所有内容到初始化状态
     */
    @Override
    @SuppressWarnings("unchecked")
    public void clear() {
        firstIndex = -1;
        lastIndex = -1;
        count = 0;
        length = 16;
        array = (T[]) new Object[length];
    }

    /**
     * 扩容的方法, 先修改length变量, 然后创建新数组, 将原来数组复制到新数组中, 用新数组取代原来的数组.
     * 之后重新设置firstIndex和lastIndex
     */
    @SuppressWarnings("unchecked")
    private void increaseCapacity() {

        //操作length变量, 即当前内部数组的总长度
        if (length == MAX_SIZE) {
            throw new RuntimeException("队列已经达到最大长度, 无法再入队.");
        } else {
            length = Math.min(length * 2, MAX_SIZE);
        }

        Object[] newArray = (T[]) new Object[length];

        //将旧数组中的内容复制到新数组, 如何复制呢, 只需要从firstIndex开始, 不断复制count个数据就可以了.

        int startIndex = 0;
        int oldLength = array.length;
        while (startIndex != count) {
            newArray[startIndex] = array[firstIndex];
            firstIndex = (firstIndex + 1) % oldLength;
            startIndex++;
        }

        //循环结束之后所有的原来数组的东西都复制到新数组从0开始的位置, 用新数组取代原来的数组, 之后重新设置 firstIndex 和 lastIndex
        array = newArray;
        firstIndex = 0;
        lastIndex = count - 1;
    }

}
这个队列就是上述思想的体现, 通过控制firstIndex与lastIndex两个索引在数组中不断循环来完成队列的任务. 队列的满与不满则交给count变量来控制. 这其中的数组扩容方法, 复制的时候实际上重新安排了firstIndex和lastIndex变量. 看看这个数组操作的效率. 入队和出队在正常情况下, 也都是常数级别的. 但是入队和出队各有可能触发数组扩容和队列清空的状态, 队列清空由于是新创建固定长度的对象,也可以认为是常数级别. 但是入队时候触发的扩容, 就是O(n)级别. 所以整体上, 相对于链表实现, 数组实现的队列在性能上不相上下, 主要问题还是会有额外的内存空间占用.

改进的数组实现队列

在类中使用额外的计数器来达成队列, 是合理的实现方案. 不过还有方法更加有趣, 可以节省掉这个计数器, 让逻辑更加简单. 来详细看这个方法. 在刚才的实现里, 为了达到队列为空这个特殊状态, 将firstIndex和lastIndex都设置为了-1, 因为单纯从firstIndex = Mod(lastIndex+1)无法判断满和空, 所以就将判断满和空的任务交给了count变量以及扩容方法. 而在改进的方法中, 不管内部数组一开始有多长, 会给firstIndex和lastIndex一个初始值, 在初始值的基础上向后操作. 假如内部数组初始长度是n, 那么一开始让firstIndex = 0, lastIndex = n-1 即可. 在后续的变动中, 先进行如下判断:
  1. 如果firstIndex = Mod(lastIndex+1), 队列是空的.
  2. 如果firstIndex = Mod(lastIndex+2), 队列是满的.
根据判断的结果, 决定是否放入数据. 实际用简单的例子模拟一下就可以知道, 这么做会导致数组中始终有一个位置不会被放入数据, 然而却不需要维护额外的变量. 比较简单. 其他的数组扩容等方法, 与刚才编写的方法都没什么本质区别. 现在就重写这个类, 刚才自己写的类中忘记了一件事: 由于构造器除了给域赋值之外, 还会新创建对象, 为了安全起见, 可以加一个参数表示是否已经初始化完成. 先把这个类的基础设施写好如下:
public class ArrayQueue<T> implements QueueInterface<T> {

    private T[] queue;

    private int frontIndex;

    private int backIndex;

    private boolean initialized = false;

    private static final int DEFAULT_CAPACITY = 50;

    private static final int MAX_CAPACITY = 10000;

    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public ArrayQueue(int size) {

        if (size > MAX_CAPACITY) {
            throw new RuntimeException("队列长度超过限制");
        }
        //创建长度加1的数组, 很重要, 因为数组有一个空位没有用到, 因此数组实际长度必须是队列长度+1
        queue = (T[]) new Object[size+1];
        frontIndex = 0;
        backIndex = size;
        initialized = true;
    }

    private void checkInitialization() {
        if (!initialized) {
            throw new RuntimeException("队列对象初始化发生错误, 请重新创建队列对象.");
        }
    }

}
然后也是一个一个来实现方法, 先来看最核心的入队:
@Override
public void enqueue(T entry) {

    checkInitialization();

    if (entry == null) {
        throw new RuntimeException("不允许入队null值");
    }
    //检查容量, 如果小于就不做动作, 大于就扩容, 超过上限则报错. 所以另外编写一个方法
    checkCapacity();
    //能通过检查容量之后, 肯定可以添加, 添加逻辑和之前一样
    backIndex = (backIndex + 1) % queue.length;
    queue[backIndex] = entry;

}
入队的逻辑和之前编写带计数器的队列几乎一样, 只是少了判断count变量. 因为现在判断数组满没满无需使用count变量, 所以都交给checkCapacity()方法去做即可. 然后是出队方法, 记住我们不允许有null值, 所以为空的时候返回异常:
@Override
public T dequeue() {
    checkInitialization();
    if (isEmpty()) {
        throw new RuntimeException("队列已经为空");
    } else {
        T result = queue[frontIndex];
        //这是个好习惯, 将数组原来的位置清空, 否则频繁操作可能会有内存泄露
        queue[frontIndex] = null;
        frontIndex = (frontIndex + 1) % queue.length;
        return result;
    }
}
接下来是查看队伍头的方法, 一样的逻辑, 在队列为空的时候报异常:
@Override
public T getFront() {
    checkInitialization();
    if (isEmpty()) {
        throw new RuntimeException("队列已经为空");
    } else {
        return queue[frontIndex];
    }
}
然后是isEmpty()方法, 逻辑在最前边已经分析过了:
@Override
public boolean isEmpty() {
    checkInitialization();
    return frontIndex == (backIndex + 1) % queue.length;
}
之后是最后一个接口方法clear(), 所作的工作就是重置frontIndex和backIndex, 比较好的做法是将其中的所有对象引用全部设置成null. :
@Override
public void clear() {
    checkInitialization();

    //一直移动frontIndex, 清除其中所有引用
    while (!isEmpty()) {
        queue[frontIndex] = null;
        frontIndex = (frontIndex + 1) % queue.length;
    }
    //重置frontIndex和backIndex
    frontIndex = 0;
    backIndex = queue.length - 1;
}
最后就是一个核心方法, 逻辑基本上都和原来一样:
@SuppressWarnings("unchecked")
private void checkCapacity() {

    checkInitialization();

    //如果数组是满的, 先看当前容量是不是已经超过上限
    if (frontIndex == (backIndex + 2) % queue.length) {
        if (queue.length == MAX_CAPACITY + 1) {
            throw new RuntimeException("队列无法再扩容");
        }

        //没有超过上限, 比较MAX_CAPACITY+1 与 队列的实际要放的内容的长度乘以2再加1, 哪个小, 就作为新数组的长度.
        T[] newQueue = (T[]) new Object[Math.min((queue.length - 1) * 2 + 1, MAX_CAPACITY + 1)];

        //代码执行到这里, 至少扩容到还可以放下一个元素. 先把原来的数组的所有东西都复制进来, 移动firstIndex直到isEmpty()即可

        int startIndex = 0;
        while (!isEmpty()) {
            newQueue[startIndex] = queue[frontIndex];
            frontIndex = (frontIndex + 1) % queue.length;
            startIndex++;
        }

        queue = newQueue;
        frontIndex = 0;
        backIndex = startIndex - 1;
    }

}
这个无需额外使用计数器的队列就写好了. 逻辑实际上比使用计数器的还要清晰.

用循环链表实现队列

还有一种非常有意思的方式, 是使用循环链表. 所谓循环链表, 就是一个链表的尾节点的next指向头节点, 这就叫做循环链表, 其实就是一个圈, 如果一直遍历是可以回到起点的. 一般循环链表是用一个引用指向所谓的头节点就可以了. 单纯作为链表来说, 使用循环链表没有什么太大用处, 但是对于队列, 可以简化判断队列是空还是满的方法. 这里的循环链表的特殊之处在于, 一开始并不是空的, 而是有一个节点, 类似循环数组一样, 这个结点永远不使用. 一个引用A指向分配给队列的节点, 一个引用B指向所有空白节点部分的开始. 然后有意思部分是, 追加到队尾的时候, 是从B处进行添加的, B会为当前队伍添加一项, 然后继续指向下一个空白. 出队的时候, 是从A引用出队的, 出队的时候会将A引用往前走一个节点. 由于始终有一个节点不使用, 所以很好判断节点是不是满的. 如果B.next == A, 队伍就满了, 下一次插入就要分配一个新节点. 如果B==A, 则是一开始的情况, 即isEmpty(). 说起来比较麻烦, 实际上操作起来没有想象中的复杂, 只需要注意一个内容, 就是一开始要为链表分配一个节点. 而且为了识别空白节点, 可以考虑不允许将null放入队列中. 当然也可以采取其他方式, 比如给节点增加一个额外的枚举属性等, 这个就看具体实现了. 来先搭建一些基础设施:
public class LoopLinkedQueue<T> implements QueueInterface<T> {

    private class Node {
        private T data;
        private Node next;

        public Node(T data) {
            this(data, null);
        }

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    //表示被数据占用部分的开始节点
    private Node queueNode;
    //表示空白部分的开始节点
    private Node vacancyNode;

    public LoopLinkedQueue() {
        //创建一个新的包含null值的节点
        Node startNode = new Node(null);
        //将其指向自己
        startNode.next = startNode;
        //然后将两个引用都指向这个节点.
        queueNode = startNode;
        vacancyNode = startNode;

    }

}
这里要注意构造器部分, 创建了一个带有null值的节点, 这个节点永远不会放入实际数据, 然后一开始将两个引用都指向这个节点, 并且关键的是这个节点的next也指向自己. 然后来一点一点实现接口方法. 首先就是isEmpty():
@Override
public boolean isEmpty() {
    return vacancyNode == queueNode;
}
可以看到, 刚创建的队列, 就符合这个条件, 即vacancyNode == queueNode, 这是因为两个引用都指向同一个节点, 只要插入之后, 由于有一个节点不使用, 这个队列就不会再有这个情况, 如果每次弹出数据就删除一个节点, 那么当没有其他节点的时候, 就会恢复到此种情况. 接下来先看第一个方法, 就是入队:
@Override
public void enqueue(T entry) {
    if (entry == null) {
        throw new RuntimeException("不允许将null入队");
    }

    //如果是从isEmpty()的情况开始, 需要将第一个新节点插入到不使用节点的后边, 同时注意我们的规则, 就是vacancyNode指向空白部分的开头, 而queueNode指向有数据的开始部分
    if (isEmpty()) {
        Node newNode = new Node(entry);
        queueNode.next = newNode;
        newNode.next = vacancyNode;
        queueNode = queueNode.next;
    //如果不空, 看是不是满, 满就插入一个空节点, 不满就不用插入, 然后将entry加入当前的vacancyNode, 然后移动一次vacancyNode
    } else {
        if (isFull()) {
            Node newNode = new Node(null);
            newNode.next = vacancyNode.next;
            vacancyNode.next = newNode;
        }
        vacancyNode.data = entry;
        vacancyNode = vacancyNode.next;
    }
}
写好了这个代码之后, 我发现, 其实不需要判断是否为空, 因为在最开始的时候, 下边的操作一样有效, 即插入一个空节点, 然后将当前节点载入数据, 再移动vacancy. 所以代码可以修改的更简明:
@Override
public void enqueue(T entry) {
    if (entry == null) {
        throw new RuntimeException("不允许将null入队");
    }

    //只要插入新数据, 必定要将当前空白节点装入新数据
    vacancyNode.data = entry;

    //如果队列满, 在当前位置下一个插入一个新节点
    if (isFull()) {
        Node newNode = new Node(null);
        newNode.next = vacancyNode.next;
        vacancyNode.next = newNode;
    }
    //如果不满, 就移动一次vacancyNode
    vacancyNode = vacancyNode.next;

}
然后是出队, 出队的方法也比较有趣, 和原来的链表出一个队就删除一个结点不同, 这里出队, 只需要返回当前queueNode的值, 然后将当前queueNode的data置为null,再前进一下即可. 如果全部的项都出完, queueNode就会移动到空白链条的开始, 也就是queueNode = vacancyNode, 这又符合了isEmpty()的条件:
@Override
public T dequeue() {
    if (isEmpty()) {
        throw new RuntimeException("队列已经为空");
    }

    T result = queueNode.data;
    queueNode.data = null;
    queueNode = queueNode.next;
    return result;
}
有了这几个方法, 剩下的就简单了:
@Override
public T getFront() {
    if (isEmpty()) {
        throw new RuntimeException("队列为空");
    } else {
        return queueNode.data;
    }

}
clear()可以直接将queueNode设置成vacancy即可. 不过还是要依次释放其中的引用以避免内存泄露:
@Override
public void clear() {
    if (!isEmpty()) {
        while (queueNode != vacancyNode) {
            queueNode.data = null;
            queueNode = queueNode.next;
        }
    }
}
clear()其实还有更简单的做法, 就是直接像构造器一样重新初始化, 但是这样会造成重新插入节点, 所以不推荐.除非内存非常紧张. 最后再补一个打印队列的方法:
public void show() {
    Node currentNode = queueNode;
    while (currentNode != vacancyNode) {
        System.out.print(currentNode.data);
        if (currentNode.next != vacancyNode) {
            System.out.print(" -> ");
        }
        currentNode = currentNode.next;
    }
    System.out.println();
}
循环链表的方式相比普通链表, 一大好处就是避免了每次插入数据的时候删除数据, 同时还可以方便的进行比较和重用链表. 如果链表经常维持在使用度比较高的情况下, 可以考虑循环链表. 没想到一个队列的实现, 也能有这么多种办法, 这还只是一个基础的队列.

Java提供的队列 - LinkedList

Java提供的队列接口是java.util.Queue<E>, 然后有一个实现类是java.util.AbstractQueue<E>, 只要继承这个类, 然后重写其中的方法就可以实现自己的队列. 慢着, 竟然还要自己实现, 难道Java就没有提供一个简单的标准队列吗, 实际上, 想要使用队列, 可以直接使用java.util.LinkedList即可. 链表实现的是Deque接口, 即双端队列. Deque继承了Queue接口, 所以双端队列也支持普通队列的操作. 因此想要使用简单队列或者双端队列, 可以直接使用LinkedList类即可. 多说一句,优先队列Java是提供了单独的实现的. 此外还有并发队列, 以后再看了.
LICENSED UNDER CC BY-NC-SA 4.0
Comment