Stack

Stack是一種線性資料結構，遵循後進先出（LIFO）的原則。

LIFO 現實中的例子可以想像一落堆疊起來的盤子，我們需要從最上面開始拿；又或者像一台塞滿人的電梯，最後進的最靠門的人必須要先出去，後面的人才能出去。

基本操作

Push: 將元素添加到Stack的頂部。
Pop: 從Stack的頂部移除元素。
Peek/Top: 獲取Stack頂部的元素但不移除它。

public static class Stack {
    private static class Node {
        private int data;
        private Node next;
        private Node(int data) {
            this.data = data;
        }
    }

    private Node top; // remove from the top 

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

    // get the top element in the stack
    public int peek() {
        return top.data;
    }

    public void push(int data) {
        Node node = new Node(data);
        node.next = top;
        top = node;
    }

    public int pop() {
        int data = top.data;
        top = top.next;
        return data;
    }
}

How to add a new node to the stack?

How to remove the top node from the stack?

Queue

Queue是一種線性資料結構，遵循先進先出（FIFO）的原則。

FIFO 現實中的例子可以想像排隊買票，先來的人先買到票，後來的人要等前面的人買完才能買。

基本操作

Enqueue/Add: 將元素添加到Queue的尾部。
- 把當前 tail.next 指向新的 data
- 更新 tail 指向新的 data
Dequeue/Remove: 從Queue的頭部移除元素。
- 把當前的 head 指向下一個 data 也就是 head.next
- 如果 head 是 null，那麼 tail 也要指向 null
- 否則返回被移除的元素
Peek/Front: 獲取Queue頭部的元素但不移除它。
- 單純的返回 head.data

public static class Queue {
    private static class Node {
        private int data;
        private Node next;
        private Node(int data) {
            this.data = data;
        }
    }

    private Node head; // remove from the head 
    private Node tail; // add things here 

    public boolean isEmpty() {
        return head == null;
    }
    
    // get the first element in the queue
    public int peek() {
        return head.data;
    }

    public void add(int data){
        Node node = new Node(data);

        // refer to the following Image
        // if tail is not null, then we need to add the new node to the tail.next 
        // 最一開始什麼data都沒有，所以 tail 跟 head 都是 null 
        // if 檢查是為了處理第二次以後的新增 
        if (tail != null) {
            tail.next = node;
        }
        // update the tail to the new node, make sure the new node is the last node
        tail = node;

        // if 檢查是為了處理第一次的新增，之後就不用了
        // if the queue is empty, then the head should be the new node
        if (head == null) {
            head = node;
        }
    }

    public int remove() {
        // get the first element in the queue, which is going to be removed
        int data = head.data;

        // update the head to the next node, prepare to remove the original head 
        head = head.next;

        // if the head is null, then the queue is empty, update the tail to null
        // 如果移除掉最後一個元素，那麼 head 就會是 null，所以 tail 也要是 null
        if (head == null) {
            tail = null;
        }
        // return the removed element
        return data;
    }
}

How to add a new node to the queue?

How to remove the first node from the queue?

差異比較

特性	Stack	Queue
定義	一種後進先出（LIFO）的資料結構	一種先進先出（FIFO）的資料結構
基本操作	Push、Pop、Peek	Enqueue、Dequeue、Peek
運作原則	後進先出（LIFO）	先進先出（FIFO）
插入操作	`Push` - O(1)	`Enqueue(Add)` - O(1)
刪除操作	`Pop` - O(1)	`Dequeue(Remove)` - O(1)
檢查操作	`Peek` - O(1)	`Peek` - O(1)
記憶體使用	只需要一個指針（top）	需要兩個指針（head 和 tail）
使用情境	函數調用、撤銷操作、括號匹配	任務排隊、資源管理、廣度優先搜尋
優點	操作簡單，速度快	高效的順序處理，方便管理流程
缺點	只能訪問和操作棧頂元素	只能訪問和操作隊首元素
視覺化結構	像一疊書：最後放的書最先拿	像排隊等候：最先排隊的最先服務
具體範例	函數調用堆疊、編輯器撤銷、算術表達式	打印隊列、CPU任務排程、網路封包處理

在添加or移除資料方面你會發現差異:

Queue遵循先進先出（FIFO）的原則。這意味著我們需要分別維護隊列的頭（head）和尾（tail）兩個指針，以便能夠高效地進行入隊（enqueue）和出隊（dequeue）操作。
- Enqueue/Add:
  - 檢查 head==null 是為了處理第一次新增的情況，之後就不用了。
  - 檢查 tail!=null 是為了處理第二次以後新增的情況，確保old_tail.next都可以指到最新的data，之後就不用了。
  - 不管如何 tail 都要更新成 new_tail。
- Dequeue/Remove:
  - 在 head=head.next之後，發現是空的
  - 應該要檢查 head==null 把 tail 也更新成 null，因為這樣才能確保 head 跟 tail 都是 null，代表整個 Queue 是空的。
Stack遵循後進先出（LIFO）的原則。這意味著我們只需要一個指針（top）來追蹤棧頂元素即可。
- 不需要檢查top是否為null，因為他的重點是 top 會指向最新的元素 data，top是否為空根本沒人在乎，不影響插入。
- 不需要檢查top是否為null，因為他的重點是 top 會指向 top.next，儘管 top 是 null，不影響刪除。

你會發現 stack 因為只要管最後的人是誰，根本不鳥前面的人，所以比較容易實現。

Queue

public void add(int data){
    Node node = new Node(data);

    // refer to the following Image
    // if tail is not null, then we need to add the new node to the tail.next 
    if (tail != null) {
        tail.next = node;
    }
    // update the tail to the new node, make sure the new node is the last node
    tail = node;

    // if the queue is empty, then the head should be the new node
    if (head == null) {
        head = node;
    }
}
public int remove() {
    // get the first element in the queue, which is going to be removed
    int data = head.data;

    // update the head to the next node, prepare to remove the original head 
    head = head.next;

    // if the head is null, then the queue is empty, update the tail to null
    // 如果移除掉最後一個元素，那麼 head 就會是 null，所以 tail 也要是 null
    if (head == null) {
        tail = null;
    }
    // return the removed element
    return data;
}

Stack

public void push(int data) {
    Node node = new Node(data);
    node.next = top;
    top = node;
}
public int pop() {
    int data = top.data;
    top = top.next;
    return data;
}

總結

我認為比較需要注意的是 Queue 的資料結構，你需要特別注意：

在 add 的時候

在塞新資料到 tail 時，為了讓 old tail 跟 data 串起來，我們需要執行 tail.next = data

但是當 Queue 是 null 的，你會發現 tail.next 會噴錯，因為 tail 本身就是 null
因此要先檢查 tail 是否為 null，如果是 null 就直接讓 tail = data。

tail 更新完後，只有在 queue 是 null 的情況下才會去動 head，否則通常就結束了不會去動到 head

如果塞入的 data 是 Queue 的第一筆資料，我們不僅僅要更新 tail 也要更新 head，將 head = data
否則 head 都會是 null …

在 remove 的時候

因為遵循 FIFO 的原則，我們要去移除 head，不太會動到 tail
唯獨動到 tail 的時候是當我們移除 Queue 裡面的最後一個元素時
- 我們要把 tail 和 head 都設為 null，這樣才能確保 Queue 是空的。
- 因此當 head = head.next 後，我們要檢查 head 是否為 null，如果是 null 就要把 tail 也設為 null。