[Data Structure] 堆疊 & 佇列

資訊

Stack 與 Queue 基本實做方式會用陣列或鏈結串列來實做。
但在這裡，用陣列實做時不會用傳統 Java array，其原因是傳統陣列大小是固定的，無法動態增減元素。
這對於 Stack 與 Queue 來說並不方便，因為這兩種資料結構通常會需要動態增減元素。
所以用 array 實做 stack 會改用 Java 對 array 有更靈活操作的 ArrayList class 來實做。

至於用鏈結串列實做時，則是直接手動實作鏈結串列 (Linked List) 來實做 stack 與 queue。
雖然 Java 本身也有 LinkedList class 可用，但它跟封裝太多東西，包括 Node 的指向等細節都被封裝起來了，導致無法直接觀察鏈結的內部運作。
對於學習資料結構原理來說，這樣反而不利於理解 Stack 和 Queue 的真實底層運作方式。

堆疊 (Stack)

Stack 是一種依循後進先出 (LIFO, Last In First Out) 原則來存取資料的線性資料結構。
Stack 可以存取多筆資料，但跟 array 不同，他不能用索引值來直接存取資料。
基本上 stack 的方法有三種：

1. push：將資料放入堆疊頂端。
2. pop：將堆疊頂端的資料移除並回傳該資料。
3. peek：回傳堆疊頂端的資料，但不移除該資料。

Java 內建 Stack 範例

import java.util.Stack;

public class stackInJava {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(3);
        stack.push(2);
        stack.push(5);

        int top = stack.peek();
        System.out.println("The top is: " + top);

        int removeVal = stack.pop();
        System.out.println("Remove val is: " + removeVal);
        top = stack.peek();
        System.out.println("The top is: " + top);

        System.out.println("The stack size is: " + stack.size());
        System.out.println("Is the stack empty? Ans: " + stack.isEmpty());
        System.out.println("Is the stack empty? Ans: " + stack.empty());
    }
}

用 Linked List 實做 Stack

使用 Linked List 實作 Stack 時，會將鏈結串列的開頭 (head) 作為堆疊頂端 (top)。
每次入堆疊 (push) 時，會在鏈結串列的開頭插入新節點；每次出堆疊 (pop)時，則從開頭移除節點。

由於在鏈結串列的開頭插入或刪除節點只需調整指標，時間複雜度為 O(1)，不需要像陣列那樣搬移資料，因此效率很高。
同時，鏈結串列可以動態擴充節點，非常適合實作可自由增減元素的堆疊結構。

public class StackOfList {
    public static void main(String[] args) {
        ListStack stackList = new ListStack();
        stackList.push(1); // [1]
        stackList.push(3); // [3,1]
        stackList.push(2); // [2,3,1]
        stackList.push(5); // [5,2,3,1]

        System.out.println("Stack size: " + stackList.size());
        System.out.println("Top element: " + stackList.peek());
        System.out.println("Pop: " + stackList.pop());
        System.out.println("Pop: " + stackList.pop());
        System.out.println("Stack size: " + stackList.size());
        System.out.println("Is empty? " + stackList.isEmpty());

        // 嘗試在空的狀況下 pop
        stackList.pop();
        stackList.pop();
        stackList.pop(); // 不會拋錯，只會顯示提示訊息
    }
}

class ListStack {
    private Node top;
    private int stackSize = 0; // 記錄 stack 目前元素數量

    private static class Node {
        int value;
        Node next;
        Node(int value) {
            this.value = value;
        }
    }

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top; // 新節點指向目前的 top
        top = newNode; // 更新 top 為新節點
        stackSize++;
    }

    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty, cannot pop.");
            return null;
        } else {
            int value = top.value;
            top = top.next;
            stackSize--;
            return value;
        }
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty, no top element.");
            return null;
        } else {
            return top.value;
        }
    }

    public int size() {
        return stackSize;
    }

    public boolean isEmpty() {
        return stackSize == 0;
    }
}

用 Array 實做 Stack

使用 array 實做 stack 時，可以將 array 的尾部作為堆疊頂，入堆疊跟出堆疊的操作即為分別在 array 的尾部新增或移除元素。
因為入堆疊的元素是可以一直增加的，所以這邊用 ArrayList (Java 的動態陣列) 來實做比較方便。

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class StackCreatedByArray {

    public static void main(String[] args) {
        System.out.println("=== Array-based Stack ===");
        StackArray stackArr = new StackArray();
        stackArr.push(1);
        stackArr.push(3);
        stackArr.push(2);
        stackArr.push(5);

        System.out.println("Satck size: " + stackArr.size());
        System.out.println("Top element: " + stackArr.peek());
        System.out.println("Pop: " + stackArr.pop());
        System.out.println("Satck size: " + stackArr.size());
        System.out.println("Pop: " + stackArr.pop());
        System.out.println("Pop: " + stackArr.pop());
        System.out.println("Pop: " + stackArr.pop());
        System.out.println("Is empty? " + stackArr.isEmpty());
    }
}

class StackArray {
    ArrayList<Integer> arr = new ArrayList<Integer>();

    void push (int val) {
        arr.add(val);
    }

    Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty, cannot pop.");
            return null;
        } else {
            int popVal = arr.get(size() - 1);
            arr.remove(size() - 1);
            return popVal;
        }
    }

    Integer peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty, no top element.");
            return null;
        } else {
            return arr.get(size() - 1);
        }
    }


    int size () {
        return arr.size();
    }

    boolean isEmpty () {
        return size() == 0;
    }
}

佇列 (Queue)

佇列與堆疊剛好相反，佇列的邏輯是依循先進先出 (FIFO, First In First Out) 原則來存取資料。
以一個生活中的常見例子來舉例說明佇列就是台灣人特別喜歡的排隊，即新來的人不斷地加入隊伍的尾端，而最早加入隊伍的人會則可以最優先買到東西離開隊伍。
對佇列來說，把元素加入佇列尾的動作稱為「入佇列 (enqueue)」，而從佇列頭移除元素的動作稱為「出佇列 (dequeue)」。

跟 stack 相同，資料結構上的 queue 基本也有三種方法，而在 Java 中，queue class 對應其三種方法分別是 offer、poll、peek：

1. push：將資料放入佇列尾端。在 Java 中對應的方法是 offer。
2. pop：將佇列頭端的資料移除並回傳該資料。在 Java 中對應的方法是 poll。
3. peek：回傳佇列頭端的資料，但不移除該資料。在 Java 中對應的方法是 peek。

提示

根據 oracle 文件，其實 queue class 也有 add 和 remove 兩個方法，功能分別跟 offer 和 poll 類似。
但實務上多半會用 offer 和 poll 來取代 add 和 remove，因為前者在佇列滿或空的狀況下不會拋出例外 (exception)，而是回傳特定值 (例如 false 或 null) 來表示操作失敗。
這種行為在實務上會比較好處理，不會因為佇列滿或空而導致程式崩潰。

Java 內建 Queue 範例

import java.util.LinkedList;
import java.util.Queue;

public class QueueInJava {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 實務上多用 offer 取代另一個 method add
        queue.offer(1);
        queue.offer(3);
        queue.offer(2);
        queue.offer(5);
        queue.offer(4);

        int size = queue.size();
        System.out.println("The size of queue is: " + size);
        int front = queue.peek();
        System.out.println("The front element value is: " + front);
        System.out.println("");

        // 實務上多用 poll 取代 remove
        int removedElement =  queue.poll();
        front = queue.peek();
        System.out.println("The removed element value is: " + removedElement);
        System.out.println("The front element value is: " + front);
    }
}

用 Linked List 實做 Queue

使用 linked list 實做 queue 時，會將鏈結串列的開頭 (head) 作為佇列頭 (front)，而鏈結串列的尾端 (tail) 則作為佇列尾 (rear)。
每次入佇列 (offer) 時，會在鏈結串列的尾端插入新節點；每次出佇列 (poll) 時，則從開頭移除節點。

public class QueueCreatedByList {
    public static void main(String[] args) {
        ListQueue listQueue = new ListQueue();
        int queueSize = listQueue.size();
        Integer queueFrontValue = listQueue.peek();
        System.out.println("Size of queue is: " + queueSize);
        System.out.println("Front value of queue is: " + queueFrontValue);
        System.out.println("");

        listQueue.offer(1);
        queueSize = listQueue.size();
        queueFrontValue = listQueue.peek();
        System.out.println("Size of queue is: " + queueSize);
        System.out.println("Front value of queue is: " + queueFrontValue);
        System.out.println("");

        listQueue.offer(3);
        queueSize = listQueue.size();
        queueFrontValue = listQueue.peek();
        System.out.println("Size of queue is: " + queueSize);
        System.out.println("Front value of queue is: " + queueFrontValue);
        System.out.println("");

        listQueue.offer(2);
        listQueue.offer(5);
        listQueue.offer(4);
        queueSize = listQueue.size();
        System.out.println("Size of queue is: " + queueSize);
        System.out.println("");

        Integer removedValue = listQueue.poll();
        System.out.println("Removed value is: " + removedValue);
        queueSize = listQueue.size();
        queueFrontValue = listQueue.peek();
        System.out.println("Size of queue is: " + queueSize);
        System.out.println("Front value of queue is: " + queueFrontValue);
        System.out.println("");
    }
}

class ListQueue {
    private static class Node {
        int value;
        Node next;
        Node(int value) {
            this.value = value;
        }
    }

    private Node front; // 記錄佇列頭，亦即頭節點
    private Node tail; // 記錄佇列尾，亦即尾節點
    private int queueSize = 0;

    // generator 在這裡可有可無，因為上面的宣告預設就是 null
    public ListQueue() {
        this.front = null;
        this.tail = null;
    }

    public int size() {
        return queueSize;
    }

    public boolean isEmpty() {
        return queueSize == 0;
    }

    // 插入元素
    public void offer(int value) {
        Node newNode = new Node(value);

        if (tail == null) {
            // queue 為空時執行這邊
            front = newNode;
            tail = newNode;
        } else {
            // queue 不為空時執行這邊
            tail.next = newNode; // 舊的尾節點指向新結點
            tail = newNode; // 紀錄尾節點的變數更新為新節點
        }

        queueSize++;
    }

    // 刪除元素
    public Integer poll() {
        if (isEmpty()) {
            System.out.println("Queue is empty, cannot dequeue.");
            return null;
        } else {
            int removedVal = front.value;
            front = front.next;
            queueSize--;

            // 刪到空時把 tail 也設為 null
            if (front == null) {
                tail = null;
            }

            return removedVal;
        }
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty, no front element.");
            return null;
        } else {
            return front.value;
        }
    }
}

用 Array 實做 Queue

import java.util.ArrayList;

public class QueueCreatedByArray {

    public static void main(String[] args) {
        System.out.println("=== Array-based Queue ===");
        ArrayQueue queueArr = new ArrayQueue();
        queueArr.enqueue(1);
        queueArr.enqueue(3);
        queueArr.enqueue(2);
        queueArr.enqueue(5);

        System.out.println("Queue size: " + queueArr.size());
        System.out.println("Front element: " + queueArr.peek());
        System.out.println("Dequeue: " + queueArr.dequeue());
        System.out.println("Queue size: " + queueArr.size());
        System.out.println("Dequeue: " + queueArr.dequeue());
        System.out.println("Dequeue: " + queueArr.dequeue());
        System.out.println("Dequeue: " + queueArr.dequeue());
        System.out.println("Is empty? " + queueArr.isEmpty());
    }
}

class ArrayQueue {
    private ArrayList<Integer> arr = new ArrayList<>();

    public void enqueue(int val) {
        arr.add(val); // 放到尾端
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty, cannot dequeue.");
            return null;
        }
        int value = arr.get(0); // 取出前端
        arr.remove(0); // 移除前端
        return value;
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty, no front element.");
            return null;
        }
        return arr.get(0);
    }

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

    public boolean isEmpty() {
        return arr.isEmpty();
    }
}