谈谈集合.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，不知道我的理解对不对。