Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


資料結構筆記 2 - Stack (堆疊), Queue (佇列)

By Jimmy 2022-04-09
發表於 資工 資料結構-資工
資料結構筆記 2 - Stack (堆疊), Queue (佇列)

Stack (堆疊) 和 queue (佇列) 可以說是 array 和 linked-list 的閹割版本,因此個別都可以用 array 和 linked-list 來實現。

1. Stack (堆疊)

1.1 定義與特性

Stack 也是 linear data structure 的一種,和 array 與 linked-list 最大的不同點是:

stack

▲ 圖片來源:維基百科

可能有些人會問,既然 stack 只是 array 和 linked-list 的閹割版,那為什麼不直接使用 array 或 linked-list 就好了?這是為了在某些應用情況下「聚焦」需要解決的問題,例如:瀏覽器的瀏覽紀錄,雖然用 linked-list 也可以實現,但用 stack 可以聚焦在操作瀏覽紀錄的行為:後進先出的行為。

誠如文章開頭提到的,stack 和 queue 都可以用 array 和 linked-list 來實作,因此嚴格來說 stack 和 queue 都可以按照儲存結構分為

用 array 實作的 stack 和 queue 有類似的特性:長度固定,不過可以用一些 method 來動態調整長度。用 linked-list 實作的 stack 和 queue 則是每一個資料節點都含有 pointer。

但因為 JavaScript 的 array 只有一種,因此以下就直接用 JavaScript 的 array 來實作 stack 和 queue,如果想知道如何用 array 和 linked-list 來實作 stack 和 queue,可以參考以下文章 (用 C++ 實作的):

[Stack: 以Array與Linked list實作](以Array與Linked list實作)
Queue: Intro(簡介),並以Linked list實作
Queue: 以Array實作Queue

1.2 時間複雜度

對 stack CRUD 的 time complexity (Average)

AccessSearchInsertionDeletion
O(n)O(n)O(1)O(1)

1.3 JavaScript 實作

class Stack {
  constructor() {
    this.data = [];
  }
  push(record) {
    this.data.push(record);
  }
  pop() {
    return this.data.pop();
  }
  peek() {
    return this.data[this.data.length - 1];
  }
  isEmpty() {
    return this.data.length === 0;
  }
  clear() {
    this.data = [];
  }
  size() {
    return this.data.length;
  }
}

2. Queue (佇列)

2.1 定義與特性

Queue 可以說是 stack 的兄弟,和 stack 有類似的屬性:

可以觀察到和 stack 最大的差別就是在新增元素的時候,stack 是在末端新增元素 (對應到 JavaScript 的 Array.prototype.push()),queue 則是在首端新增元素 (對應到 JavaScript 的 Array.prototype.unshift())。

queue

▲ 圖片來源:維基百科

2.2 時間複雜度

對 queue CRUD 的 time complexity (Average)

AccessSearchInsertionDeletion
O(n)O(n)O(1)O(1)

2.3 JavaScript 實作

class Queue {
  constructor() {
    this.data = [];
  }
  enqueue(record) {
    this.data.unshift(record);
  }
  dequeue() {
    return this.data.pop();
  }
  getFront() {
    return this.data[0];
  }
  getBack() {
    return this.data[this.data.length - 1];
  }
  isEmpty() {
    return this.data.length === 0;
  }
  clear() {
    this.data = [];
  }
  size() {
    return this.data.length;
  }
}

3. 參考資料

大話資料結構(全新彩色版)
[Stack: 以Array與Linked list實作](%E4%BB%A5Array%E8%88%87Linked list%E5%AF%A6%E4%BD%9C)
Queue: Intro(簡介),並以Linked list實作
Queue: 以Array實作Queue


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More