數(shù)據(jù)結(jié)構(gòu)中的數(shù)組

我們要學(xué)習(xí)的第一個(gè)數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，數(shù)組中很多值得挖掘。

數(shù)組基礎(chǔ)

把數(shù)據(jù)碼成一排進(jìn)行存放

數(shù)組中索引從0開始，Java語(yǔ)法中要求數(shù)組存放同一類型的元素，可以通過中括號(hào)下標(biāo)的方式取到元素。

這樣可以看到Main中有的方法。

package cn.mtianyan;

public class Main {

public static void main(String[] args) {
    // 必須傳入長(zhǎng)度
    int[] arr = new int[10];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }

    System.out.println("=========");

    int[] scores = new int[]{100,99,96};
    for (int i = 0; i < scores.length; i++) {
        System.out.println(scores[i]);
    }

    System.out.println("=========");

    for (int score : scores) {
        System.out.println(score);
    }

    System.out.println("=========");
    scores[0] = 92;

    for (int score : scores) {
        System.out.println(score);
    }
}

}

數(shù)組可以這樣遍歷，是因?yàn)樗鼘?shí)現(xiàn)了可遍歷接口。

Java為我們提供的數(shù)組，其中非常重要的一部分就是它的索引。索引可以有語(yǔ)義，也可以沒有語(yǔ)義,2可以代表學(xué)號(hào)，但也可以將其視為沒有語(yǔ)義。

數(shù)組最大的優(yōu)點(diǎn): 快速查詢，scores[2]直接插到2號(hào)索引的。因此數(shù)組最好應(yīng)用于"索引有語(yǔ)義"的情況，查學(xué)號(hào)為2的學(xué)生成績(jī)。

但并非所有有語(yǔ)意的索弓都適用于數(shù)組,如×××號(hào): 1101031985121 66666;依次為索引，這得開辟很大的內(nèi)存空間,空間浪費(fèi)。

數(shù)組也可以處理“索引沒有語(yǔ)意”的情況。我們?cè)谶@一章，主要處理“索引沒有語(yǔ)意”的情況數(shù)組的使用。

索引沒有語(yǔ)意，如何表示沒有元素? capacity 和 size的區(qū)別： 數(shù)組size是3，capacity是8。

如何添加元素（超過size如何處理）?如何刪除元素（挪位）? Java中的數(shù)組并沒有這些方法，我們需要基于java的數(shù)組，二 次封裝屬于我們自己的數(shù)組類。

我們自己做的是動(dòng)態(tài)數(shù)組（內(nèi)部依然使用java數(shù)組實(shí)現(xiàn)），Java的是靜態(tài)數(shù)組。

增刪改查，有的數(shù)據(jù)結(jié)構(gòu)不一定四個(gè)齊全。capacity是數(shù)組最多可以裝多少元素，和實(shí)際能裝多少元素是沒有關(guān)系的。

package cn.mtianyan;

public class Array {
private int[] data;
private int size;

/**
 * 帶容量參數(shù)構(gòu)造函數(shù)
 *
 * @param capacity 數(shù)組容量
 */
public Array(int capacity) {
    data = new int[capacity];
    size = 0;
}

/**
 * 默認(rèn)構(gòu)造函數(shù)
 */
public Array() {
    this(10);
}

/**
 * 靜態(tài)數(shù)組入?yún)?gòu)造函數(shù)
 *
 * @param data 傳入靜態(tài)數(shù)組
 */
public Array(int[] data) {
    this.data = data;
}

/**
 * 獲取數(shù)組元素個(gè)數(shù)
 *
 * @return size 數(shù)組元素個(gè)數(shù)
 */
public int getSize() {
    return size;
}

/**
 * 獲取數(shù)組的容量
 *
 * @return capacity 獲取容量
 */
public int getCapacity(){
    return data.length;
}

/**
 * 判斷數(shù)組是否為空
 *
 * @return 是否為空
 */
public boolean isEmpty(){
    return size == 0;
}

}
向數(shù)組中添加元素

向數(shù)組末尾添加元素

size指向data中第一個(gè)為空位置。因此添加元素時(shí)只需要添加到arr[size],并size++即可。(注意添加元素判滿)

/**
 * 向所有元素末尾添加一個(gè)新元素。
 *
 * @param e 添加的元素
 */
public void addLast(int e){

// if (isFull()){
// throw new IllegalArgumentException("AddLast failed. Array is Full");
// }else {
// data[size] =e; // data[size++] =e;
// size++;
// }
add(size,e);
}

/**
 * 向索引0號(hào)位置添加元素
 *
 * @param e 添加的元素
 */
public void addFirst(int e){
    add(0,e);
}

/**
 * 在index位置插入一個(gè)新元素e
 *
 * @param index 插入位置索引
 * @param e 插入元素
 */
public void add(int index,int e){
    if (isFull())
        throw new IllegalArgumentException("AddLast failed. Array is Full");
    // 大于size就不是緊密排列了
    if (index<0 || index>size){
        throw new IllegalArgumentException("AddLast failed. Required index<0 or index>size ");
    }
    else {
        // 從哪開始挪呢: 從size-1這個(gè)元素(size本身是指向空的),挪到哪個(gè)呢，index位置的這個(gè)元素也是要挪的。
        for (int i=size-1; i>=index; i--){
            data[i+1] = data[i]; // 后一個(gè)等于前一個(gè)，從數(shù)組最后一個(gè)元素開始。
            // 極端值驗(yàn)證: size 1 index 0;(i=0;i>=0;i--)會(huì)執(zhí)行一次data[1]=data[0].正確。
        }
        data[index] = e;
        size++;
    }
}

77插入，后面的元素都要向后挪動(dòng)。

這里注意必須從100這里，向后挪，否則會(huì)造成值覆蓋。

在數(shù)組中查詢?cè)睾托薷脑?/p>

/**
 * 打印數(shù)組信息及遍歷元素。
 *
 * @return 數(shù)組信息和元素遍歷結(jié)果
 */
@Override
public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d, capacity = %d\n",size,data.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
        res.append(data[i]);
        if (i !=size-1) // 最后一個(gè)元素不要加，
            res.append(", ");
    }
    res.append(']');
    return res.toString();
}

package cn.mtianyan;

public class ArrayTest {
public static void main(String[] args) {
Array array = new Array(20);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
}
}

    array.add(1,100);
    System.out.println(array);
    array.addFirst(-1);
    System.out.println(array);

取出某一個(gè)元素。

/**
 * 傳入索引，獲取該位置元素
 *
 * @param index 要獲取的元素索引
 * @return 返回該位置數(shù)組元素
 */
public int get(int index){
    if (index<0 || index>=size){
        throw new IllegalArgumentException("Get failed. Required index<0 or index>=size ");
    }else {
        return data[index];
    }
}

通過get方法用戶無(wú)法使用到數(shù)組后半截沒有使用到的空間，通過封裝保證。

System.out.println(array.get(array.getSize()-1));

/**
 * 傳入索引和元素值，將該位置元素設(shè)置為傳入值
 * @param index 索引
 * @param e 傳入值
 */
public void set(int index,int e){
    if (index<0 || index>=size){
        throw new IllegalArgumentException("Set failed. Required index<0 or index>=size ");
    }else {
        data[index] = e;
    }
}
    array.set(0,-99);
    System.out.println(array);

數(shù)組中的包含，搜索和刪除元素

如果要?jiǎng)h除索引為1的元素，從88開始，后面都要往前挪,挪size-index次。只需要size--，對(duì)于最后一個(gè)位置的元素不用做其他操作，因?yàn)橛脩粢苍L問不到。

/**

• 查找數(shù)組中是否有元素e
• @param e

• @return 包含 true; 不包含 false
  */
  public boolean contains(int e){
  for (int i = 0; i < size; i++) {
  if (data[i] == e){
  return true;
  }
  }
  return false;
  }

  /**

• 查找數(shù)組中元素，返回其索引(第一個(gè)遇到)
• @param e 元素

• @return 不存在 -1; 存在 i
  */
  public int find(int e){
  for (int i = 0; i < size; i++) {
  if (data[i] == e){
  return i;
  }
  }
  return -1;
  }

  public int[] findAll(int e){
  int[] tempArray=new int[size];
  int index = 0;
  for (int i = 0; i < size; i++) {
  if (data[i] == e){
  tempArray[index] = i;
  index++;
  }
  }
  int[] indexArray=new int[index];
  for (int i = 0; i < index; i++) {
  indexArray[i] = tempArray[i];
  }
  return indexArray;
  }
  注意findAll中使用tempArray臨時(shí)對(duì)象的作用: 同時(shí)將int數(shù)組，與它的size一起傳遞了出來。

  System.out.println("===============加入重復(fù)元素后數(shù)組如下===================");
  array.add(3,3);
  array.add(array.getSize()-1,9);
  System.out.println(array);
  System.out.println("================包含 尋找測(cè)試===========================");
  System.out.println(array.contains(-99));
  System.out.println(array.contains(-100));
  System.out.println("3的index: "+array.find(3));
  int [] tmpArr = array.findAll(3);
  for (int i : tmpArr) {
      System.out.print(i+" ");
  }
  System.out.println();

  /**

• 刪除數(shù)組元素，返回刪除的元素值
• @param index 索引

• @return 該索引位置元素值
  */
  public int remove(int index){
  // 判空，空數(shù)組 removeFirst index=0,size=0，index>=size異常?？諗?shù)組 removeLast index=-1 index<0異常;
  if (index<0 || index>=size){
  throw new IllegalArgumentException("Remove failed. Required index<0 or index>=size ");
  }else {
  int ret = data[index];
  for (int i=index+1;i < size;i++){
  // 從哪個(gè)元素開始挪，從index位置的后一個(gè)元素開始，挪到哪個(gè)元素結(jié)束，挪到size-1(因此沒等號(hào))
  data[i-1] = data[i]; // 前一個(gè)等于后一個(gè)
  }
  size--;
  return ret;
  }
  }

  /**

• 刪除第一個(gè)(索引0)元素

• @return 刪除的元素值
  */
  public int removeFirst(){
  return remove(0);
  }

  /**

• 刪除最后一個(gè)(索引size-1)元素

• @return 刪除的元素值
  */
  public int removeLast(){
  return remove(size-1);
  }

  /**

• 刪除數(shù)組中某一個(gè)元素值（刪除數(shù)組中第一個(gè)找到的）
• @param e 元素值

• @return 刪除是否成功
  */
  public boolean removeElement(int e){
  int index = find(e);
  if (index != -1){
  remove(index);
  return true;
  }
  return false;
  }

  /**

• 刪除數(shù)組中包含的所有該元素值
• @param e 元素值

• @return 刪除成功與否
  */
  public boolean removeAllElement(int e){
  int[] indexArray = findAll(e);
  if (indexArray.length != 0){
  for (int i = 0; i < indexArray.length; i++) {
  remove(indexArray[i]-i); // 此處注意-i的巧妙
  }
  return true;
  }
  return false;
  }
  重難點(diǎn)代碼在于remove(indexArray[i]-i);此處很可能會(huì)被忽略，造成異常。因?yàn)閿?shù)組每刪除一個(gè)，原本獲取到的臨近后一個(gè)元素的index值應(yīng)該-1；臨近后兩個(gè)則應(yīng)該-2；以此類推。

  System.out.println("================開始刪除測(cè)試========================");
  System.out.println(array);
  array.remove(3); // 刪除一個(gè)3
  System.out.println(array);
  array.removeElement(1); // 刪除1
  System.out.println(array);
  System.out.println("=====刪除index3 后 刪除元素1如上====");
  
  array.removeAllElement(9);
  System.out.println(array);
  System.out.println("=====刪除所有9=====");
  array.addFirst(-99);
  array.removeAllElement(-99);
  System.out.println(array);
  System.out.println("=====首位添加-99，后刪除所有-99 結(jié)果如上=====");
  
  array.add(4,99);
  array.add(5,99);
  array.addFirst(99);
  array.addLast(99);
  array.add(7,99);
  System.out.println(array);
  System.out.println("=====上面為刪除99前，下面為刪除99后=====");
  array.removeAllElement(99);
  System.out.println(array);

使用泛型

我們上面實(shí)現(xiàn)的數(shù)組目前只能存放int類型，但是我們需要的是可以承載多種類型，甚至自定義對(duì)象的容器。Java泛型可以解決這個(gè)問題。

使用泛型: 讓我們的數(shù)據(jù)結(jié)構(gòu)可以放置“任何”數(shù)據(jù)類型,不可以是基本數(shù)據(jù)類型，只能是類對(duì)象。

java中的八種基本類型: boolean , byte, char , short , int , long , float , double;

每個(gè)基本數(shù)據(jù)類型都有對(duì)應(yīng)的包裝類: Boolean , Byte , Char , Short, Int , Long , Float , Double。自動(dòng)的拆包，解包。

public class Array<Element>
public class Array<E>
為類名后面添加泛型類型標(biāo)識(shí)，此處的類型標(biāo)識(shí)可以自定義。

private E[] data;

這里無(wú)法直接通過E實(shí)例化。只能通過間接的Object再轉(zhuǎn)換。

data = (E[]) new Object[capacity];
/**

• 靜態(tài)數(shù)組入?yún)?gòu)造函數(shù)

• @param data 傳入靜態(tài)數(shù)組
  */
  public Array(E[] data) {
  this.data = data;
  }
  public void add(int index,E e){
  public void addLast(E e){
  public void addFirst(E e){
  public boolean contains(int E){
  for (int i = 0; i < size; i++) {
  if (data[i].equals(E)){
  return true;
  }
  }
  return false;
  }
  這里注意，兩個(gè)對(duì)象之間的比較要使用equals方法，將所有的與成員數(shù)組類型相關(guān)的都改了。

  public E remove(int index){
  // 判空，空數(shù)組 removeFirst index=0,size=0，index>=size異常?？諗?shù)組 removeLast index=-1 index<0異常;
  if (index<0 || index>=size){
  throw new IllegalArgumentException("Remove failed. Required index<0 or index>=size ");
  }else {
  E ret = data[index];
  for (int i=index+1;i < size;i++){
  // 從哪個(gè)元素開始挪，從index位置的后一個(gè)元素開始，挪到哪個(gè)元素結(jié)束，挪到size-1(因此沒等號(hào))
  data[i-1] = data[i]; // 前一個(gè)等于后一個(gè)
  }
  size--;
  data[size] = null;
  return ret;
  }
  }
  data[size]還指著一個(gè)值不過用戶訪問不到而已，新的元素添加會(huì)自動(dòng)覆蓋。使用泛型后，data數(shù)組中存放的是類對(duì)象的引用， size-- 后data[size]依然指向一個(gè)引用，引用就涉及到空間釋放的問題，Java有自動(dòng)垃圾回收機(jī)制，但如果 data[size]仍存放引用，就不會(huì)被自動(dòng)垃圾回收。data[size] = null;(不必須，可以被新對(duì)象覆蓋)

如果不置為null，它會(huì)被稱為loitering Objects，沒有用但垃圾回收機(jī)制不回收。 loitering Objects != memory leak 為了程序優(yōu)化，手動(dòng)去除更好。

Main中改動(dòng)

Array<Integer> array = new Array(20);
Array<Integer> array = new Array<>(20);
即使不改，也是可以正常運(yùn)行的。但是我們最好加上更清楚的看出類型，jdk1.7之后不用再后面再重復(fù)一次。

package cn.mtianyan;

public class Student {

private String name;
private int score;

public Student(String studentName, int studentScore){
    name = studentName;
    score = studentScore;
}

@Override
public String toString(){
    return String.format("Student(name: %s, score: %d)", name, score);
}

public static void main(String[] args) {

    Array<Student> arr = new Array();
    arr.addLast(new Student("mtianyan1", 100));
    arr.addLast(new Student("mtianyan2", 66));
    arr.addLast(new Student("mtianyan3", 88));
    System.out.println(arr);
}

}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Student)) return false;
    Student student = (Student) o;
    return score == student.score &&
            (name.equals(student.name));
}

@Override
public int hashCode() {
    return Objects.hash(name,score);
}

重寫hashCode和equals方法。

    System.out.println("================start=======================");
    System.out.println(arr);
    arr.remove(1);
    Student stu1 = new Student("mtianyan1", 100);
    Student stu3 = new Student("mtianyan3", 88);
    arr.removeElement(stu1);
    System.out.println(arr);
    System.out.println("==============================================");
    System.out.println(arr);
    arr.removeAllElement(stu3);
    System.out.println(arr);

動(dòng)態(tài)數(shù)組

Java靜態(tài)數(shù)組容量有限，固定。我們要將其改造成一個(gè)可伸縮的。

不夠用了，就開辟一個(gè)新的數(shù)組，容量是原來的二倍(4變?yōu)?)，然后把原來數(shù)組的內(nèi)容進(jìn)行復(fù)制過來(size不變)，最后將data指向新的數(shù)組。這里要遍歷的把每個(gè)值都搞過去，對(duì)于性能消耗大不大呢，本章后兩節(jié)會(huì)討論。

    if (isFull())
        throw new IllegalArgumentException("AddLast failed. Array is Full");
    // 大于size就不是緊密排列了
    if (index<0 || index>size){
        throw new IllegalArgumentException("AddLast failed. Required index<0 or index>size ");
    }

坐標(biāo)非法依然拋出異常，但是如果滿了，我們的動(dòng)態(tài)數(shù)組將不會(huì)拋出異常。

    if (isFull())
        resize(2*data.length);

這里的2倍，是優(yōu)于擴(kuò)大固定大小值的。2的選擇是我們自己決定的，Collection中ArrayList中選取了1.5。

private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData;
}

package cn.mtianyan;

public class ArrayTestDynamic {
public static void main(String[] args) {
Array<Integer> array = new Array<>();
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
array.addFirst(99);
System.out.println(array);
array.addLast(100);
System.out.println(array);
}
}

刪除時(shí)壓縮數(shù)組容量

public E remove(int index){
    // 判空，空數(shù)組 removeFirst index=0,size=0，index>=size異常?？諗?shù)組 removeLast index=-1 index<0異常;
    if (index<0 || index>=size){
        throw new IllegalArgumentException("Remove failed. Required index<0 or index>=size ");
    }else {
        E ret = data[index];
        for (int i=index+1;i < size;i++){
            // 從哪個(gè)元素開始挪，從index位置的后一個(gè)元素開始，挪到哪個(gè)元素結(jié)束，挪到size-1(因此沒等號(hào))
            data[i-1] = data[i]; // 前一個(gè)等于后一個(gè)
        }
        size--;
        data[size] = null;

        if (size == data.length /2 )
            resize(data.length /2);
        return ret;
    }
}

這里設(shè)置一個(gè)閾值，當(dāng)數(shù)組一半為空時(shí)，容量減半。

package cn.mtianyan;

public class ArrayTestDynamic {
public static void main(String[] args) {
Array<Integer> array = new Array<>();
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
array.addFirst(99);
System.out.println(array);
array.addLast(99);
System.out.println(array);
array.removeAllElement(99);
System.out.println(array);
for (int i = 0; i < 5; i++) {
array.removeElement(i);
}
System.out.println(array);
}
}

簡(jiǎn)單的復(fù)雜度分析

簡(jiǎn)單的時(shí)間復(fù)雜度分析 感性認(rèn)識(shí) 考研: 細(xì)致推導(dǎo)

O(1), O(n) , O(lgn) , O(nlogn) , O(n^2);

大O描述的是算法的運(yùn)行時(shí)間和輸入數(shù)據(jù)之間的關(guān)系

public static int sum(int[] nums){
int sum = 0;
for(int num: nums) sum += num;
return sum;
}
通常我們說上面這個(gè)代碼的算法，時(shí)間復(fù)雜度是O(n)的。n是nums中的元素個(gè)數(shù);算法和n呈線性關(guān)系,線性關(guān)系表現(xiàn)在一次方。

num 數(shù)字越多，算法執(zhí)行時(shí)間越長(zhǎng)。

為什么要用大O，叫做O(n)?

因?yàn)槲覀兒雎粤顺?shù)，實(shí)際時(shí)間 T=c1*n + c2，大O是一個(gè)大概的; 對(duì)于每一個(gè)數(shù)所花的時(shí)間是c1，int return sum時(shí)間是c2。

因此，無(wú)論c1，c2是多少，只要符合線性關(guān)系都是O(n)的算法。

即使c1，c2很小，但是是二次方，因此是O(n2)，性能差于O(n)。沒錯(cuò)，理論性能差，但是對(duì)于一些小數(shù)據(jù)，如n=10，反倒是O(n2)的要執(zhí)行更快。

漸進(jìn)時(shí)間復(fù)雜度，描述n趨近于無(wú)窮的情況。（3000）高階算法常數(shù)低反而快于低階算法: 高級(jí)排序算法，歸并排序，快速排序，都可以對(duì)于小數(shù)據(jù)轉(zhuǎn)為插入排序，獲得10-15%優(yōu)化，插入排序高階但常數(shù)小。

因?yàn)槭勤呄蛴跓o(wú)窮的情況，因此可以將其中的低階項(xiàng)忽略掉。

分析動(dòng)態(tài)數(shù)組的時(shí)間復(fù)雜度

添加操作

addLast(e) // O(1) 末尾添加，直接賦值，其他什么也不做。
O(1)意味著它與我們的數(shù)組規(guī)模沒有關(guān)系,不管數(shù)組n有多大，addLast都能在常數(shù)時(shí)間內(nèi)完成，此時(shí)不考慮size變化。

addFirst(e) // O(n) 前面添加，所有元素后挪
n個(gè)元素，就要后挪n-1次。

add(index, e)
與index有關(guān)。因此可以這樣分析：index這么多取值的概率是相等的，嚴(yán)格計(jì)算需要一些概率論知識(shí)，求出時(shí)間期望；平均來看是O(n/2)

添加操作綜合來看，整體是O(n)級(jí)別的。

在算法復(fù)雜度分析上通常關(guān)注的是最壞的情況,有一些特例，下小節(jié)講個(gè)特例。

resize // O(n)級(jí)別
刪除操作:

修改操作:

set(index, e) // O(1)級(jí)別
查找操作:

get(index) // O(1)
contains(e) // O(n)
find(e) // O(n)

數(shù)組最好情況是已知索引。

如果只對(duì)最后一個(gè)元素操作，addLast RemoveLast O(1)依然是O(n),因?yàn)閞esize把全部元素重新遍歷賦值一遍?？雌饋韗esize好像是一個(gè)性能很差的操作。

對(duì)于resize的分析，使用最差情況是不合理的。下一小節(jié)使用均攤復(fù)雜度進(jìn)行分析。

均攤復(fù)雜度和防止復(fù)雜度的震蕩

添加操作

最壞情況下，尾部添加就擴(kuò)容，從O(1)變成了O(n)級(jí)別;但是我們不可能每次操作都resize，10次才會(huì)觸發(fā)一次resize。

假設(shè)當(dāng)前capacity=8,并且每一次添加操作都使用addLast：

9次addLast操作，觸發(fā)resize,總共進(jìn)行了17次基本操作。大約平均每次addLast操作，進(jìn)行2次基本操作。

推廣開: 假設(shè)capacity = n, 第n+1次addLast,觸發(fā)resize，總共進(jìn)行2n+1次基本操作，平均每次addLast操作，進(jìn)行2次基本操作。

這就將resize的時(shí)間平均給了每一次addLast操作,這樣均攤下來，時(shí)間復(fù)雜度是O(1)級(jí)別的！和n沒有關(guān)系。

在這個(gè)例子里，這樣均攤計(jì)算，比計(jì)算最壞情況有意義。均攤復(fù)雜度 amortized time complexity

同理，我們看removeL ast操作，均攤復(fù)雜度也為0(1)

復(fù)雜度震蕩。

我們單獨(dú)看removeLast和addLast,它的復(fù)雜度為O(1)

但當(dāng)兩個(gè)在capacity臨界點(diǎn)，一次add 一次remove，會(huì)不停的觸發(fā)resize。存在該情況，出現(xiàn)問題的原因: removeLast時(shí)resize過于著急
(Eager)

解決方案: Lazy

當(dāng)數(shù)組size是當(dāng)前容量的1/4，進(jìn)行縮容量，縮1/2,則還有1/4空間可以加元素。size == capacity/4時(shí)，才將capacity減半。

Lazy方式，懶一下，算法性能更好。后面講到線段樹時(shí)還有例子:當(dāng)更懶，改善算法性能(懶機(jī)制代碼更多)。

        if (size == data.length /4 && data.length/2 !=0)
            resize(data.length /2);

因?yàn)槭钦麛?shù)除法，所以當(dāng)length為1時(shí)，會(huì)造成等于0，而我們無(wú)法new一個(gè)容量為0的數(shù)組。