[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 中的堆疊 class

這邊只是先放著看看直接用 Java 內建的 Stack class 有多方便。

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());
    }
}

用 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;
    }
}

用 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 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 為新節點
    }

    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty, cannot pop.");
            return null;
        } else {
            int value = top.value;
            top = top.next;
            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() {
        int count = 0;
        Node current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

佇列 (Queue)

Java 中的佇列 class

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

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

        queue.add(1);
        queue.add(3);
        queue.add(2);
        queue.add(5);

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

        int removeVal = queue.remove();
        System.out.println("Removed value: " + removeVal);

        front = queue.peek();
        System.out.println("The front is: " + front);

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

用 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();
    }
}

用 Linked List 實做 Queue

public class QueueOfList {
    public static void main(String[] args) {
        System.out.println("=== LinkedList-based Queue ===");
        ListQueue queueList = new ListQueue();
        queueList.enqueue(1);
        queueList.enqueue(3);
        queueList.enqueue(2);
        queueList.enqueue(5);

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

        // 嘗試在空的狀況下 dequeue
        queueList.dequeue();
        queueList.dequeue();
        queueList.dequeue();
    }
}

class ListQueue {
    private Node front, rear;

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

    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) { // queue 為空
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty, cannot dequeue.");
            return null;
        } else {
            int value = front.value;
            front = front.next;
            if (front == null) rear = null; // 全部取完
            return value;
        }
    }

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

    public int size() {
        int count = 0;
        Node current = front;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public boolean isEmpty() {
        return front == null;
    }
}