算法1.3

Java 应用类型必须被实例化为引用类型，即封装类型（如int-》Integer）

• 自动装箱

• 自动拆箱

背包：一种不支持从中删除元素的集合数据类型，用于收集元素并无序遍历迭代所有收集到的元素

• 用例：计算平均值

基于数组的栈大小动态调整

• 栈的大小在数组创建时固定，数组大小无法改变，容易在压入时造成栈溢出的问题或空间浪费的问题，因此在使用栈前必须预估栈的最大容量

• 修改数组大小：将原栈转移到另一更大容量的数组中

  private void resize(int max){
    Item[] temp = (Item[]) new Object[max];//max大于原栈大小N
    for(int i = 0; i<N;i++){
      temp[I] = a[I];          
    }
    a=temp;
  }
  

• 压入数据：检查栈大小N与数组大小a.length，相等则a.length加倍

  private void push(Item item){
    if(N == a.length){resize(2*a.length)；}
    a[N++] = item;
  }
  

• 删除栈顶元素（最近添加元素）：删除栈顶元素，然后检查a.length是否为N4倍，是则将a.length减半，使其保持约半满状态，接下来仍可以进行多次push或pop操作

  private Item pop(){
    Item item = a[--N];
    a[N] = null;//避免被删除对象游离，使其被垃圾回收器回收
    if(N>0 && N <= a.length/4){resize(a.length/2);}
    return item;
  }
  

• 由以上操作可知栈的数组大小为偶数