Stack 堆疊

Stack 是一種基礎的資料結構，可以拿堆盤子來幫助想像，它的特性是：

1. 只能在堆疊的最上方新增或刪除元素
2. 後進先出（Last in first out, LIFO）
3. 最上方稱為 Top ，底部稱為 Bottom

操作有：

1. Push，新增元素
2. Pop，拿出元素
3. Peak，查看最上方的元素

此外，Java 標準函式庫也有 Stack。

import java.util.Stack;

宣告方法為：

Stack<T> stack = new Stack<T>();

1. Class

首先，先建立 Stack Class。

我們需要一個陣列來放元素，同時也需要一個數字告訴我們容量才能建立陣列。此外我們還需要一個 Flag 來紀錄最上方元素的 Index。

先新增 Stack 的屬性：

public class Stack {
    private int capacity;
    private int data[];
    private int top = -1;
}

加入 Constructor：

public Stack(int capacity) {
    this.capacity = capacity;
    data = new int[capacity];
}

我們可以開始實作功能了。

2. Functions

首先，我們先實作 Push 來加入元素：

1. 把 top 往上移，指到一個空位
2. 把元素填進去這個空位

public void push(int element) {
    data[++top] = element;
}

接著實作 Pop：

1. 回傳最上方的元素
2. 把 top 往下移，讓下面那個元素成為 top

public int pop() {
    return data[top--];
}

實作 Peak：

1. 回傳最上方的元素

public int peak() {
    return data[top];
}

3. State

由於我們可能在多次 Push Pop 之後可能會忘記 Stack 裝了多少元素，還有多少空間，可能會導致 Stack 滿了仍繼續 Push 產生 Overflow，或是 Stak 空了仍繼續 Pop 產生 Underflow，所以我們引入幾個 State Getter 來取得 Stack 的容量情況。

1. isFull
2. isEmpty
3. size

public Boolean isFull() {
    return this.top == this.capacity - 1;
}

public Boolean isEmpty() {
    return this.top == -1;
}

public int size() {
    return top + 1;
}

Code

public class Stack {
    private int capacity;
    private int data[];
    int top = -1;

    // Constructor
    public Stack(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
    }

    // Push
    public void push(int element) {
        data[++top] = element;
    }

    // Pop
    public int pop() {
        return data[top--];
    }

    // Peak
    public int peak() {
        return data[top];
    }

    // isFull
    public Boolean isFull() {
        return this.top == this.capacity - 1;
    }

    // isEmpty
    public Boolean isEmpty() {
        return this.top == -1;
    }

    // size
    public int size() {
        return top + 1;
    }
}