思路

  1. 先進後出
  2. 紀錄最上面的元素

實作

測試方法

public class Stack_Array2 {
    Integer[] ary; // 傳入陣列
    Integer[] stack;
    Integer i_top = null; // LIFO 後進先出 set top

    public Stack_Array2(Integer[] ary) {
        this.ary = ary;
    }

    public void build_stack(){
    this.stack = new Integer[this.ary.length];
        for (int i = 0; i < this.ary.length; i++) {
            push(ary[i]);
        }
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1,2,3,4,5};
        Stack_Array2 stack_array = new Stack_Array2(nums);
        stack_array.build_stack();

        // full - extend the storage size
        // 拓展空間
        stack_array.push(6);

        Integer num = stack_array.pop(); // 取出最上面的元素 6
        num = stack_array.pop(); // 取出最上面的元素 5
        num = stack_array.pop(); // 取出最上面的元素 4
        num = stack_array.pop(); // 取出最上面的元素 3
        num = stack_array.pop(); // 取出最上面的元素 2
        num = stack_array.pop(); // 取出最上面的元素 1

        // empty
        num = stack_array.pop(); // null

        System.out.println();
    }

具體

push

private void push(Integer val) {
     // 如果最上面 == 當前 stack 長度表示已到空間長度
     // 5==5
    if (size() == stack.length) {
        // 需要拓展空間
        expand_space();
    }

    if (size() == 0) { //如果為第一個
        i_top = 0; // top -> 0
    }else {
        i_top++; // top -> 1,2,3,4,5
    }
    // stack[1] = 2;
    // stack[2] = 3;
    stack[i_top] = val; //將參數放入上層
}

private int size() {
    if (i_top == null) return 0; // 如果是空的 -> 為第一個
    return i_top + 1; // 第二個位置 a[0]->a[1]
}

private void expand_space() {
    Integer[] stack_new = new Integer[stack.length * 2]; // *2
    for (int i = 0; i < stack.length; i++) {
        stack_new[i] = stack[i]; // 依序放入新 stack
    }
    this.stack = stack_new;
}

pop

public Integer pop() { // 取出
    if (size() == 0) { // 全部都取出沒內容時
        return null;
    }

    Integer val = stack[i_top]; //取出最上層 -> val
    stack[i_top] = null; // 清空最上層

    if (size() == 1) { // 如果 size = 1 表示取出後 stack 會變成空(已經是最後一個)
        i_top = null; // 配置 i_top = 0
    }else {
        i_top--;
    }

    return val;
}