知芯

jcf-arrayDeque

2019-09-15

ArrayDeque

当要使用栈时,Java已不推荐使用Stack,而推荐使用更高效的ArrayDeque;当需要使用队列时也就首选ArrayDeque(次选LinkedList)。ArrayDeque 实现了接口 Deque

  • ArrayDeque没有容量限制;
  • 非线程安全,因此不支持多线程同时安全访问;
  • 不允许存储Null元素;
  • 作为栈使用时,比Stack快;作为队列使用时,比LinkedList更快。

    Deque

    double ended queue, 支持元素在两端增加和删除的线性容器,这个接口定义了12种方法。分为两类:操作失败抛出异常;操作失败返回特定值 null 或者 false。
    Deque接口extends Queue接口,当作为queue(FIFO)使用时,元素从队列的尾端加入,从队列的首端取出,对应的方法如下:
Queue Equivalent Deque Method Desc
add(e) addLast(e) 向队尾插入元素,失败则抛出异常
offer(e) offerLast(e) 向队尾插入元素,失败则返回false
remove() removeFirst() 获取并删除队首元素,失败则抛出异常
poll() pollFirst() 获取并删除队首元素,失败则返回null
element() getFirst() 获取但不删除队首元素,失败则抛出异常
peek() peekFirst() 获取但不删除队首元素,失败则返回null

Deque也可以当作Stacks(LIFO)使用,元素从deque的首端push和pop,对应的方法如下:

Stack Equivalent Deque Method Desc
push(e) addFirst(e) 向栈顶插入元素,失败则抛出异常
offerFirst(e) 向栈顶插入元素,失败则返回false
pop() removeFirst() 获取并删除栈顶元素,失败则抛出异常
pollFirst() 获取并删除栈顶元素,失败则返回null
peek() peekFirst() 获取但不删除栈顶元素,失败则抛出异常
peekFirst() 获取但不删除栈顶元素,失败则返回null

Important variables

1
2
3
4
5
6
// 存储数组
transient Object[] elements;
// 第一个元素的索引
transient int head;
// 尾端第一个空位
transient int tail;

数组的长度就是deque的容量,它总是2的幂。除了在addX方法中短暂的变满,不允许数组装满。在addX方法中,数组变满后立即对其进行大小调整,从而避免头和尾交叉。另外,不包含元素的位置始终为空。因为是循环数组,所以head不一定总等于0,tail也不一定总是比head大。

Main Methods

  • doubleCapacity()
    在head和tail相遇的时候,表示deque装满了,进行扩容。这样交叉的复制方式保证了性的elements中元素的顺序符合逻辑。
    93999820160507172951125776162110.png

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边的长度
    int newCapacity = n << 1; // 2倍容量
    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;
    }
  • addFirst()
    addFirst.png

    空间问题是在插入元素后考虑的;索引的范围控制交给 head = (head - 1) & (elements.length - 1) 当head=0时,在往左(head-1)加入元素,如下所示,head移动到了element的最后(构成了循环)。

    1
    2
    3
    // head=0,elements.length=16
    head=[head-1]补&[elements.length - 1]补=[-1]补&[15]补=11111111&00001111
    =00001111=[15]补=15
    1
    2
    3
    4
    5
    6
    7
    8
    public void addFirst(E e) {
    if (e == null)
    throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 扩容
    if (head == tail)
    doubleCapacity();
    }
  • addLast()
    addLast.png

    tail 所以和head相反,向右移动,假设当前tail=element.length 放置元素之后.如下所示移动到elements最左(构成了循环)。

    1
    tail = (tail + 1) & (elements.length - 1)=[16]补&[15]补=00010000&00001111=00000000=0
    1
    2
    3
    4
    5
    6
    7
    public void addLast(E e) {
    if (e == null)
    throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
    doubleCapacity();
    }
  • poolFirst()
    过程与addFirst相反,拿出元素,并向右移动head。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
    return null;
    elements[h] = null; // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
    }
  • poolLast()
    过程与addLast相反,拿出元素,并向左移动tail。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null)
    return null;
    elements[t] = null;
    tail = t;
    return result;
    }
  • peakFirst()

    1
    2
    3
    4
    public E peekFirst() {
    // 如果deque为空,elements[head] = null
    return (E) elements[head];
    }
  • peakLast()

    1
    2
    3
    public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
    }
  • Summary

    1. deque保证element数组的大小始终是2的幂,这就使得elements.length - 1 的补码始终是类似于 00001111这样左边为0,右边为1的形式。
    2. & (elements.length - 1)是保证索引构成循环的巧妙实现
    3. 扩容时的交叉复制,保证了元素扩容后顺序符合逻辑。
Tags: jcf
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章