- 继承机构
- 队列Queue
- 双端队列deque
- 操作第一个元素
- 操作最后一个元素
- 用作FIFO队列
- 用作LIFO堆栈
- ArrayDeque源码分析
- addFirst
- 扩容机制
- 查询
- 队列还是栈
队列还提供额外的插入、提取和检查操作。 这些方法中的每一个都以两种形式存在:一种在操作失败时抛出异常,另一种返回>一个特殊值( null或false ,取决于操作)
| 抛出异常 | 返回特殊值 | |
|---|---|---|
| 添加 | add(e) | offer(e) |
| 移除队列头 | remove() | poll() |
| 返回队列头 | element() | peek() |
操作第一个元素 操作最后一个元素 用作FIFO队列 用作LIFO堆栈 ArrayDeque源码分析双端队列是指允许两端都可以进行入队和出队操作的队列
● 不支持多线程并发访问,
● 禁止空元素.
● 底层是对象数组,默认16,两倍扩容
分析一下ArrayDeque是如何实现双端队列的
transient Object[] elements;// 双端队列的容量,总是2的幂 transient int head; //表示队列头 transient int tail; // 表示队列尾 private static final int MIN_INITIAL_CAPACITY = 8; // 无参构造一个长度16的对象数组,数组末端作为头部,每次add,就在左侧填充.addFirst
arrayDeque底层数据结构是一个数组,无参构造创建的是一个容量为16的对象数组.
添加元素从数组末端开始,依次向数组头方向(head=head-1)添加,如上图
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
// 每次add后检查是否需要扩容,当add元素的索引为0时,扩容为原来的两倍
if (head == tail)
doubleCapacity();
}
元素添加顺序:
数组中的存储顺序:
通过左移运算new = old<<1,新容量为原来的2倍
扩容时机: head==tail,数组空间已被使用完.
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
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;
}
查询以上述add案例继续说明,当数组最后一个空间被占用后,检查head==tail,进行扩容.扩容之后元素在数组中的摆放如下:
因为arrayDeque类中定义了两个属性,head和tail用来表示队列头尾对应的数组索引.所以获取首尾元素很简单,就是指定element
的索引即可
getFirst()
E result = (E) elements[head];
getLast()
E result = (E) elements[(tail - 1) & (elements.length - 1)];
队列还是栈如果没有扩容,按照从队列前面插入元素的规则,第一个插入的放入数组的最后一个索引,即elements.length-1.
当发生扩容后,数组中元素的摆放位置不再是连续有序的,此时则取tail-1索引位. 以容量16为例,扩容后为32,last元素放在未扩容时>的15索引位.即15&31 = 15;
双端队列deque既可以实现队列结构FIFO(比linkedList实现队列要快),也可以实现栈结构LIFO(比stack类快).
取决于取数时是从头部取还是尾部取.
头部存,头部取,则是先进后出,栈
头部存,尾部取,则是先进先出,队列



