From Gossip@caterpillar

Algorithm Gossip: 佇列 - 使用Java 作物件封裝

說明

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

解法

在這邊使用Java實作，Java雖然沒有指標，但可以使用參考（Reference）來達到鏈結的效果，一個節點的類別包裝方式如下：
class Node {
    int data;   // 節點資料
    Node next;  // 下一個節點位置  
} 
 
其中next是個物件參考名稱，它可以用來參考至（指向）下一個節點物件的記憶體位置，而佇列類別可以如下包裝：
class Queue {
    private Node front;
    private Node rear;

    // 加入資料至尾端
    void add(Node node) {
        if(front == null) {
            front = node;
            rear = front;
        }
        else {
            if(front.next == null) {
                front.next = node;
            }
            rear.next = node;
            rear = node;
        }
    }

    // 取得前端資料
    Node peek() {
        return front;
    }

    // 刪除前端資料
    Node remove() {
        Node tmp = front;
        if(tmp != null) {
            front = tmp.next;
        }
        return tmp;
    }

    // 列出佇列內容
    List<Node> list() {
        List<Node> nodes = new ArrayList<Node>();
        nodes.add(front);
        Node tmp = front.next;
        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 Queue { 
    private Node front; 
    private Node rear; 

    void add(Node node) {
        if(front == null) {
            front = node;
            rear = front;
        }
        else {
            if(front.next == null) {
                front.next = node; 
            }
            rear.next = node;
            rear = node; 
        }
    } 

    Node peek() {
        return front;
    } 

    Node remove() { 
        Node tmp = front;
        if(tmp != null) {
            front = tmp.next; 
        }
        return tmp;
    } 

    public List<Node> list() {
        List<Node> nodes = new ArrayList<Node>();
        nodes.add(front);
        Node tmp = front.next; 
        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)); 

        Queue queue = new Queue(); 

        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;
                    queue.add(node); 
                    break;
                case 2: 
                    System.out.println("取得前端：" + queue.peek().data);
                    break; 
                case 3: 
                    System.out.println("刪除前端：" + queue.remove().data);
                    break; 
                case 4: 
                    for(Node n : queue.list()) {
                        System.out.println(n.data);
                    }
                    break; 
                default: 
                    System.out.print("\n選項錯誤！"); 
            } 
        } 

        System.out.println(); 
    } 
}