學習資源

https://labuladong.online/algo/data-structure-basic/queue-stack-basic/

學習記錄

今天是學習的第 8 天，主要學習了隊列 / 棧基本原理：

之後要介紹的資料結構都建立在兩種基本儲存方式之上：

• 陣列（順序儲存）
• 鏈表（鏈式儲存）

操作受限的資料結構

隊列和棧屬於 「操作受限」 的資料結構。相比於基本的陣列和鏈表，它們刻意限制了可用的操作，只保留頭尾操作元素的 API。

• 隊列：只允許在隊尾插入元素，在隊頭刪除元素
• 棧：只允許在棧頂插入元素，從棧頂刪除元素

隊列和棧的差異

隊列的程式碼

隊列是一種 「先進先出」 的資料結構，就像排隊一樣，最先進入的元素最先被取出。

// 隊列的基本 API
class MyQueue {
    // 向隊尾插入元素，時間複雜度 O(1)
    push(e) {}

    // 從隊頭刪除元素，時間複雜度 O(1)
    pop() {}

    // 查看隊頭元素，時間複雜度 O(1)
    peek() {}

    // 返回隊列中的元素個數，時間複雜度 O(1)
    size() {}
}

棧的程式碼

棧是一種 「先進後出」 的資料結構，就像疊盤子一樣，最後放上去的最先被拿走。

class MyStack {
    // 向栈顶插入元素，时间复杂度 O(1)
    push(e) {}

    // 从栈顶删除元素，时间复杂度 O(1)
    pop() {}

    // 查看栈顶元素，时间复杂度 O(1)
    peek() {}

    // 返回栈中的元素个数，时间复杂度 O(1)
    size() {}
}

學習總結

• 資料結構都建立在陣列和鏈表之上
• 隊列和棧屬於 「操作受限」 的資料結構
• 隊列是一種 「先進先出」 的資料結構，最先進入的元素最先被取出
• 棧是一種 「先進後出」 的資料結構，最後放上去的最先被拿走