From Gossip@caterpillar

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

說明

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

解法

在這邊使用Java實作，Java雖然沒有指標，但可以使用參考（Reference）來達到鏈結的效果，一個節點的類別包裝方式如下：
class Node {
    int data;  
    Node next;
}
 
其中next是個物件參考名稱，它可以用來參考至（指向）下一個節點物件的記憶體位置，而堆疊類別可以如下包裝：
// 堆疊
class Stack {
    private Node top;
   
    // 加入資料至頂端
    void add(Node node) {
        node.nex = top;
        top = node;
    }

    // 傳回頂端資料
    Node top() {
        return top;
    }

    // 取出頂端資料
    Node pop() {
        Node tmp = top;
        top = top.next;
        return tmp;
    }

    // 列出堆疊內容
    List<Node> list() {
        List<Node> nodes = new ArrayList<Node>();
        Node tmp = top;
        while(tmp != null) {
            nodes.add(tmp);
            tmp = tmp.next;
        }
        return nodes;
    }
} 
 
利用物件導向來包裝資料結構，雖然在設計時需要花較多的心思，但設計完成之後，日後呼叫使用就簡單了，以後您只要注意主程式的邏輯設計就可以了。

實作

  • Java 
import java.util.*;
import java.io.*; 

class Node { 
    int data;  
    Node next; 
} 

class Stack { 
    private Node top; 
    
    void add(Node node) {
        node.next = top; 
        top = node; 
    } 

    Node top() { 
        return top; 
    } 

    Node pop() { 
        Node tmp = top; 
        top = top.next; 
        return tmp;
    } 

    List<Node> list() { 
        List<Node> nodes = new ArrayList<Node>();
        Node tmp = top;
        while(tmp != null) { 
            nodes.add(tmp);
            tmp = tmp.next; 
        } 
        return nodes;
    } 
} 

public class Demo { 
    public static void main(String[] args) throws IOException { 
        BufferedReader buf = 
                 new BufferedReader(
                       new InputStreamReader(System.in)); 

        Stack stack = 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>"); 

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

            if(select == -1) 
                break; 

            switch(select) { 
                case 1: 
                    System.out.print("\n輸入值："); 
                    int input = Integer.parseInt(buf.readLine()); 
                    Node node = new Node();
                    node.data = input;
                    stack.add(node); 
                    break; 
                case 2: 
                    System.out.print("\n頂端值：" +  stack.top().data); 
                    break; 
                case 3: 
                    System.out.println("\n刪除：" + stack.pop().data); 
                    break; 
                case 4: 
                    for(Node n : stack.list()) {
                        System.out.println(n.data);
                    }
                    break; 
                default: 
                    System.out.print("\n選項錯誤！"); 
            } 
        } 

        System.out.println(); 
    } 
}