谈谈集合.Queue

之前说到，java中集合的主要作用就是装盛其他数据和实现常见的数据结构。所以当我们要用到“栈”、“队列”、“链表”和“数组”等常见的数据结构时就应该想到可以直接使用jdk给我们提供的集合框架。比如说当我们想用到队列时就应该想到使用linkedlist和arraydeque。本篇博客将介绍collection框架中的queue。

queue接口继承了collection接口，所以collection的所有方法queue的实现类中都包含，同时还有一个子接口dqueue，表示双端队列。对于queue我们主要掌握arraydeque和linkedlist，了解priorityqueue(优先级队列)。

1. 接口介绍

queue也是java集合框架中定义的一种接口，直接继承自 collection 接口。除了基本的 collection 接口规定测操作外，queue 接口还定义一组针对队列的特殊操作。通常来说，queue是按照先进先出(fifo)的方式来管理其中的元素的，但是优先队列是一个例外。

deque接口继承自queue接口，但deque支持同时从两端添加或移除元素，因此又被成为双端队列。鉴于此，deque接口的实现可以被当作fifo队列使用，也可以当作lifo队列（栈）来使用。官方也是推荐使用 deque的实现来替代stack。deque的主要实现类有arraydeque和linkedlist。

arraydeque是deque接口的一种具体实现，是依赖于可变数组来实现的。arraydeque没有容量限制，可根据需求自动进行扩容。arraydeque不支持值为null的元素。

linkedlist的具体特性已经在之前的博客中介绍过了，这边不再重新介绍了。

1.1 queue接口概览

queue可以被当做一个队列来使用，实现fifo操作，主要提供下面的操作

public interface queue<e> extends collection<e> {
    //向队列尾部插入一个元素，并返回true
    //如果队列已满，抛出illegalstateexception异常
    boolean add(e e);

    //向队列尾部插入一个元素，并返回true
    //如果队列已满，返回false
    boolean offer(e e);

    //取出队列头部的元素，并从队列中移除
    //队列为空，抛出nosuchelementexception异常
    e remove();

    //取出队列头部的元素，并从队列中移除
    //队列为空，返回null
    e poll();

    //取出队列头部的元素，但并不移除
    //如果队列为空，抛出nosuchelementexception异常
    e element();

    //取出队列头部的元素，但并不移除
    //队列为空，返回null
    e peek();
}

1.2 deque接口

deque接口是一个双端队列，可以对队列的头尾进行操作，所以也可以当做栈来使用。

下面的表格列举了queue和deque接口的相对应方法

queue方法	deque方法
add(e)	addlast(e)
offer(e)	offerlast(e)
remove()	removefirst()
poll()	pollfirst()
element()	getfirst()
peek()	peekfirst()

deque还有一个重要的功能是可以当做栈来使用

stack方法	deque方法
push(e)	addfirst(e)
pop()	removefirst()
peek()	peekfirst()

2. arraydeque

arraydeque是deque基于数组的实现。

以下内容来源于网络

2.1 arraydeque的成员变量

    //数组存储元素
    transient object[] elements;
    //头部元素索引
    transient int head;
    //尾部元素索引
    transient int tail;
    //最小容量
    private static final int min_initial_capacity = 8;

arraydeque底层使用数组存储元素，同时还使用head和tail来表示索引，但注意tail不是尾部元素的索引，而是尾部元素的下一位，即下一个将要被加入的元素的索引。

2.2 初始化

public arraydeque() {
    elements = new object[16];
}

public arraydeque(int numelements) {
    allocateelements(numelements);
}

public arraydeque(collection<? extends e> c) {
    allocateelements(c.size());
    addall(c);
}

private void allocateelements(int numelements) {
    int initialcapacity = min_initial_capacity;
    // find the best power of two to hold elements.
    // tests "<=" because arrays aren't kept full.
    if (numelements >= initialcapacity) {
        initialcapacity = numelements;
        initialcapacity |= (initialcapacity >>>  1);
        initialcapacity |= (initialcapacity >>>  2);
        initialcapacity |= (initialcapacity >>>  4);
        initialcapacity |= (initialcapacity >>>  8);
        initialcapacity |= (initialcapacity >>> 16);
        initialcapacity++;

        if (initialcapacity < 0)   // too many elements, must back off
            initialcapacity >>>= 1;// good luck allocating 2 ^ 30 elements
    }
    elements = new object[initialcapacity];
}

这边讲下private void allocateelements(int numelements)这个方法。arraydeque的初始化容量必须是2^n。所以你传的初始化容量如果是10，那么实际申请的数组容量是16，如果申请的容量是33，那么实际的容量是62。如果申请的容量是62,那么实际申请的容量是128。

2.3 add方法

public void addfirst(e e) {
    if (e == null)
        throw new nullpointerexception();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doublecapacity();
}

public void addlast(e e) {
    if (e == null)
        throw new nullpointerexception();
    //tail中保存的是即将加入末尾的元素的索引
    elements[tail] = e;
    //tail向后移动一位
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        //tail和head相遇，空间用尽，需要扩容
        doublecapacity();
}

在存储的过程中，这里有个有趣的算法，就是tail的计算公式(tail = (tail + 1) & (elements.length - 1))，注意这里的存储采用的是环形队列的形式，也就是当tail到达容量最后一个的时候，tail就为等于0，否则tail的值tail+1。

head也采用了类似的方式，每次在头部添加元素后，head都会指向最新被添加进去的那个元素所在的位置。当head小于0时也会采取环的形式存元素，比如head已经指向位置0，又向队列中头部添加一个元素后，head会变成length-1。

关于head和tail，需要主要的是head永远指向第一个元素的索引位置，tail永远指向尾部位置（这个位置上暂时还没有元素，如果在尾部插入元素，则在这个位置上插入）

2.4 扩容机制

private void doublecapacity() {
    assert head == tail; //扩容时头部索引和尾部索引肯定相等
    int p = head;
    int n = elements.length;
    //头部索引到数组末端(length-1处)共有多少元素
    int r = n - p; // number of elements to the right of p
    //容量翻倍
    int newcapacity = n << 1;
    //容量过大，溢出了
    if (newcapacity < 0)
        throw new illegalstateexception("sorry, deque too big");
    //分配新空间
    object[] a = new object[newcapacity];
    //复制头部索引到数组末端的元素到新数组的头部
    system.arraycopy(elements, p, a, 0, r);
    //复制其余元素
    system.arraycopy(elements, 0, a, r, p);
    elements = a;
    //重置头尾索引
    head = 0;
    tail = n;
}

下图是扩容的示意图

3. 总结

arraydeque是deque 接口的一种具体实现，是依赖于可变数组来实现的。arraydeque 没有容量限制，可根据需求自动进行扩容。arraydeque 可以作为栈来使用，效率要高于stack；arraydeque 也可以作为队列来使用，效率相较于基于双向链表的linkedlist也要更好一些。

所以我们程序中如果要使用到“队列”和“栈”这种数据结构，我们要首先想到linkedlist和arraydeque。个人认为作为队列和栈来使用的话，两者性能相差不大，但是arraydeque需要扩容，还需要申请连续的内存空间，所以个人更推荐使用linkedlist，不知道我的理解对不对。