复习：数组面试总结(笔记)

怼烎@ 2023-03-02 05:08 139阅读 0赞

## 数组 ##

**数组的特性：**

1.  存储空间是连续的
2.  长度是不可变的
3.  只能存储 相同的类型（不严谨）
4.  可以通过下标访问数组的内容 a\[10\] 时间复杂度为O1
5.  每个元素的默认值为‘零’值 （0 或 null 或 false）-> 一个对象的基本的数据域的初始化也是这样的  
    例如 Student 类中的username属性 默认值
6.  ArrayList
7.  自动扩容
8.  长度有限（int的最大值）
9.  默认初始容量为10
10. 每次扩容原来的1.5倍(因为源码中是 a+(a>>1) 是原来值+原来值右移一位，也就是原来值除以2 即1.5倍)
11. 它是线程不安全的
12. 因为在源码中有这样的判断：![在这里插入图片描述][20200727203856577.png]

> 如果多个线程进行add操作时可能会导致elementData数组越界。具体逻辑如下：  
> ArrayList 默认数组大小为 10。假设现在已经添加进去 9 个元素了，size = 9。  
> 线程 A 执行完 add 函数中的ensureCapacityInternal(size + 1)挂起了。  
> 线程 B 开始执行，校验数组容量发现不需要扩容。于是把 “b” 放在了下标为 9 的位置，且 size 自增 1。此时 size = 10。  
> 线程 A 接着执行，尝试把 “a” 放在下标为 10 的位置，因为 size = 10。但因为数组还没有扩容，最大的下标才为 9，所以会抛出数组越界异常 ArrayIndexOutOfBoundsException

1.  new ArrayList（100） 这里边的值可以减少自动扩容的次数
2.  它还有缩容操作 ，但需要手动调用的 最小会缩到现有的元素个数（不能把里边的内容缩没了把？哈哈）
3.  做栈
    
     *  先进后出
     *  会有一种题 就是abcdefg顺序进栈 不可能的出栈顺序是什么 选择题
4.  做队列

*  先进先出

**例如：用双栈实现一个队列**

Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
    
        public void push(int x){ 
            stack1.push(x);
        }
    
        public Integer pop(){ 
            if(!stack2.isEmpty()){ 
                return stack2.pop();
            }else{ 
                while(!stack1.isEmpty()){ 
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
            
        }

[20200727203856577.png]: /images/20230208/6b42e81725724c7c8a6f3c84a589b612.png