From Gossip@caterpillar

Algorithm Gossip: 堆疊 - 使用 Java 作物件封裝

說明

如果您使用C++或Java等支援物件導向的語言來實作堆疊，您可以使用類別的方式來包括堆疊的功能，將所有的堆疊操作由堆疊物件來處理，一旦包裝完成，則使用堆疊物件的時候，只要呼叫加入、刪除等方法，而無需處理堆疊的top或判斷是否為空等細節。

解法

使用C++與使用Java來作類別包裝其實是類似的，在這邊我們使用Java實作，因為它的語法看來較簡潔；Java雖然沒有指標，但可以使用參考（Reference）來達到鏈結的效果，一個節點的類別包裝方式如下：

class Node {
    private int data;   // 節點資料
    private Node next; // 下一個節點位置

    public void setData(int data); // 節點資料
    public void setNext(Node next); // 下一個節點位置
    public int getData(); // 傳回節點資料
    public Node getNext(); // 傳回下一個節點位置
}

其中next是個物件參考名稱，它可以用來參考至（指向）下一個節點物件的記憶體位置，而堆疊類別可以如下包裝：

class Stack {
    private Node top;    // 堆疊頂端
    private String name; // 只是個名稱

    // 利用建構子建立堆疊
    public Stack();
    public Stack(String name);

    // 插入資料至頂端
    public void add(int data);

    // 傳回頂端資料
    public int printTop();

    // 刪除頂端資料
    public void del();

    // 列出堆疊內容
    public void list();
}

利用物件導向來包裝資料結構，雖然在設計時需要花較多的心思，但設計完成之後，日後呼叫使用就簡單了，以後您只要注意主程式的邏輯設計就可以了。

實作

Java

import java.io.*; 

// 節點 
class Node { 
    private int data;   // 節點資料 
    private Node next;  // 下一個節點位置 

    public void setData(int data) {  // 節點資料 
        this.data = data; 
    } 

    public void setNext(Node next) {  // 下一個節點位置 
        this.next = next; 
    } 

    public int getData() {  // 傳回節點資料 
        return data; 
    } 

    public Node getNext() {  // 傳回下一個節點位置 
        return next; 
    } 
} 

// 堆疊 
class Stack { 
    private Node top; 
    private String name;  // 只是個名稱 

    public Stack() { 
        this("list"); 
    } 

    // 利用建構子建立堆疊 
    public Stack(String name) { 
        this.name = name; 
        top = null; 
    } 

    // 插入資料至頂端 
    public void add(int data) { 
        Node newNode = new Node(); 
        newNode.setData(data); 
        newNode.setNext(top); 
        top = newNode; 
    } 

    // 傳回頂端資料 
    public int printTop() { 
        return top.getData(); 
    } 

    // 刪除頂端資料 
    public void del() { 
        Node tmpNode; 
        tmpNode = top; 

        if(tmpNode == null) { 
            System.out.println("\n堆疊已空！"); 
            return; 
        } 

        top = top.getNext(); 
        tmpNode = null; 
    } 

    // 列出堆疊內容 
    public void list() { 
        Node tmpNode; 
        tmpNode = top; 

        System.out.print("\n堆疊內容："); 
        while(tmpNode != null) { 
            System.out.print(tmpNode.getData() + " "); 
            tmpNode = tmpNode.getNext(); 
        } 
    } 
} 

public class StackShow { 
    public static void main(String[] args) 
                                  throws IOException { 
        int input, select; 
        BufferedReader buf; 
        buf = new BufferedReader(
                       new InputStreamReader(System.in)); 

        Stack s1 = new Stack("堆疊測試"); 

        while(true) {  
            System.out.print("\n\n請輸入選項(-1結束)："); 
            System.out.print("\n(1)插入值至堆疊"); 
            System.out.print("\n(2)顯示堆疊頂端"); 
            System.out.print("\n(3)刪除頂端值"); 
            System.out.print("\n(4)顯示所有內容"); 
            System.out.print("\n$c>"); 

            select = Integer.parseInt(buf.readLine()); 

            if(select == -1) 
                break; 

            switch(select) { 
                case 1: 
                    System.out.print("\n輸入值："); 
                    input = Integer.parseInt(buf.readLine()); 
                    s1.add(input); 
                    break; 
                case 2: 
                    System.out.print("\n頂端值：" +  
                                             s1.printTop()); 
                    break; 
                case 3: 
                    s1.del(); 
                    break; 
                case 4: 
                    s1.list(); 
                    break; 
                default: 
                    System.out.print("\n選項錯誤！"); 
            } 
        } 

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