LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 228|回复: 0

Stack & Queue - addFirst()

[复制链接]
发表于 2023-12-20 15:42:45 | 显示全部楼层 |阅读模式

Stack & Queue概述


Java里有一个叫做Stack的类,却没有叫做Queue的类(它是个接口名字)。当需要使用栈时,Java已不推荐使用Stack,而是推荐使用更高效的ArrayDeque;既然Queue只是一个接口,当需要使用队列时也就首选ArrayDeque了(次选是LinkedList)。

addFirst()
addFirst(E e)的作用是在Deque的首端插入元素,也就是在head的前面插入元素,在空间足够且下标没有越界的情况下,只需要将elements[--head] = e即可。



实际需要考虑: 1.空间是否够用,以及2.下标是否越界的问题。上图中,如果head为0之后接着调用addFirst(),虽然空余空间还够用,但head为-1,下标越界了。下列代码很好的解决了这两个问题。

//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}

上述代码我们看到,空间问题是在插入之后解决的,因为tail总是指向下一个可插入的空位,也就意味着elements数组至少有一个空位,所以插入元素的时候不用考虑空间问题。

下标越界的处理解决起来非常简单,head = (head - 1) & (elements.length - 1)就可以了,这段代码相当于取余,同时解决了head为负值的情况。因为elements.length必需是2的指数倍,elements - 1就是二进制低位全1,跟head - 1相与之后就起到了取模的作用,如果head - 1为负数(其实只可能是-1),则相当于对其取相对于elements.length的补码。

下面再说说扩容函数doubleCapacity(),其逻辑是申请一个更大的数组(原数组的两倍),然后将原数组复制过去。过程如下图所示:



图中我们看到,复制分两次进行,第一次复制head右边的元素,第二次复制head左边的元素。

//doubleCapacity()
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 = (E[])a;
    head = 0;
    tail = n;
}


------
原文链接:https://pdai.tech/md/java/collection/java-collection-Queue&Stack.html


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表