【資料結構】Java 實作堆疊（Stack）

堆疊是一種能存放多個資料，但無法透過索引（index）來操作的結構。堆疊在資料的管理方式具有「後進先出」的特性，在應用上包含資料的順序反轉、函式呼叫的返回等等。

本文會講解堆疊的結構與操作方式，並撰寫Java程式，分別以鏈結串列和陣列實作出來。

一、堆疊的結構與操作方式

堆疊顧名思義就是將東西一個一個往上疊，讀者可以想像成桌上放著一疊書。我們從外在的狀況能看出這疊書有幾本，以及最頂端的封面長怎樣。但如果要再放其他的書，只能放在最頂端。或是想把書拿走，也只能從頂端開始拿。這兩點形成了「後進先出」（Last In First Out，LIFO）的特性。

本文會以鏈結串列與陣列實作出不同的堆疊。為了有所規範，筆者設計一個叫「IStack」的介面，定義堆疊基本的操作方式。

public interface IStack<E> {
    boolean push(E data);
    E pop();
    E peek();
    int size();
    boolean isFull();
}

以下是這些方法的用途

push：新增一筆資料到堆疊頂端，並回傳是否新增成功。
pop：從堆疊頂端拿出一筆資料。
peek：回傳堆疊頂端的資料，但不會從堆疊中移除。
size：回傳堆疊的資料筆數。
isFull：回傳堆疊空間是否已滿。

二、鏈結串列實作堆疊

鏈結串列是由「節點」所構成，因此我們先準備好節點的類別。

public class Node<E> {
    private E data;
    private Node<E> next;

    public Node(E data) {
        this.data = data;
    }

    public E getData() {
        return data;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

再來是堆疊的類別，它會實作 IStack 介面。其具有 topNode 的節點欄位，代表最頂端的資料；而 size 欄位代表堆疊中有幾筆資料。以下是示意圖與範例程式。

public class LinkedListStack<E> implements IStack<E>{
    private Node<E> topNode;
    private int size;

    public boolean push(E data) {
        // TODO
        return true;
    }

    public E pop() {
        // TODO
        return null;
    }

    public E peek() {
        if (this.size == 0) {
            throw new RuntimeException();
        }
        return this.topNode.getData();
    }

    public int size() {
        return this.size;
    }

    public boolean isFull() {
        return false;
    }
}

我們從 push 方法開始實作，做法相當於在串列的最前面加入新節點。因此只要將新節點的鏈結指向原本的頂端節點，再更新 topNode 欄位即可。

public boolean push(E data) {
    Node<E> node = new Node<>(data);
    node.setNext(this.topNode);
    this.topNode = node;
    this.size++;

    return true;
}

接著是 pop 方法，做法相當於刪除串列最前面的節點，並回傳被刪除的資料。因此我們從頂端節點（第一個節點）的鏈結獲取第二個節點，將其更新到 topNode 欄位，最後回傳第一個節點資料。若堆疊原本就只有一筆資料，則 topNode 欄位最終會被設為 null，代表堆疊中沒有資料可以存取了。

public E pop() {
    if (this.size == 0) {
        throw new EmptyStackException();
    }

    Node<E> node = this.topNode;
    this.topNode = this.topNode.getNext();
    this.size--;

    return node.getData();
}

三、陣列實作堆疊

在堆疊的類別中，同樣會實作 IStack 介面。而資料的儲存之處是一個陣列，其容量（長度）透過建構子來給定。而 size 欄位則代表堆疊中有幾筆資料。以下是示意圖與範例程式。

public class ArrayStack<E> implements IStack<E> {
    private Object[] elements;
    private int size;

    public ArrayStack(int capacity) {
        this.elements = new Object[capacity];
    }

    public boolean push(E data) {
        // TODO
        return false;
    }

    public E pop() {
        // TODO
        return null;
    }

    public E peek() {
        if (this.size == 0) {
            throw new EmptyStackException();
        }
        return (E) this.elements[this.size - 1];
    }

    public int size() {
        return this.size;
    }

    public boolean isFull() {
        return this.size >= this.elements.length;
    }
}

接著從 push 方法開始實作，我們將新資料往陣列的後面擺放，這與鏈結串列相反。讀者首先要知道，size 會比最後一個加入的元素的索引大1。因此新資料的索引正好就是 size。

public boolean push(E data) {
    if (isFull()) {
        return false;
    }

    this.elements[this.size] = data;
    this.size++;
    return true;
}

再來實作 pop 方法。我們知道 size - 1 就是目前最後一筆資料的索引。只要將元素值清空（設為 null），並回傳該筆資料即可。

public E pop() {
    if (this.size == 0) {
        throw new EmptyStackException();
    }

    int targetIndex = this.size - 1;
    E data = (E) this.elements[targetIndex];
    this.elements[targetIndex] = null;
    this.size--;

    return data;
}

四、擴大堆疊的陣列容量

上一節實作出的堆疊，由於在建立時就已經決定陣列容量，所以當空間滿了，將無法再加入新資料。本節我們會基於上一節的堆疊做進一步的調整，讓容量能自行擴大，以下簡稱擴容。

首先宣告另一個無參數的建構子，而陣列的容量給予0。這是一種節省記憶體空間的手法，考慮了建立出堆疊，卻完全沒用到的可能性。等真的要新增資料，再索取記憶體進行擴容就好。

public class ArrayListStack<E> implements IStack<E> {
    private Object[] elements;
    private int size;

    public ArrayListStack() {
        this.elements = new Object[0];
    }

    public ArrayListStack(int capacity) {
        this.elements = new Object[capacity];
    }

    public boolean push(E data) {
        // TODO
        return true;
    }
    // 其餘略過，與ArrayStack相同
}

接下來實作擴容的程式。針對上述容量為0的堆疊，我們給予預設容量10。之後每次都讓容量擴大為原本的1.5倍。建立出新陣列後，再將目前的資料複製過去，並指定給堆疊即可。

private void grow() {
    int newCapacity = this.elements.length == 0
            ? 10
            : (int) (this.elements.length * 1.5);
    Object[] newElements = new Object[newCapacity];

    for (int i = 0; i < this.elements.length; i++) {
        newElements[i] = this.elements[i];
    }
    this.elements = newElements;
}

最後在加入資料時，先判斷堆疊是否已滿，是的話則呼叫 grow 方法。如此一來便不必擔心堆疊空間不夠了。但另一方面，也會有多餘空間用不到，形成浪費的問題，這是陣列的缺點。

public boolean push(E data) {
    if (isFull()) {
        grow();
    }

    // 其餘略過，與ArrayStack相同
}

以下是本文的完整程式碼：
https://gist.github.com/ntub46010/f6d8f0c215028182c0daa2cb8da842c6

新手工程師的程式教室

搜尋此網誌