堆疊(Stack)

介紹

堆疊是資料結構的一種，將數據排成一列，可以把它想像在疊積木，資料不斷往上堆疊，每次取出資料時，只能從最上方的資料開始拿起

  • 後進先出原理，稱為 Last in First out ，簡稱 LIFO
  • 資料無index
  • 只能從最上方加入，並從最上方開始拿取


(圖片取自於Stacks & Queues)

複雜度

時間複雜度

Action動作 平均 最壞
訪問(Access) $O(n)$ $O(n)$
搜尋(Search) $O(n)$ $O(n)$
插入(Insertion) $O(1)$ $O(1)$
刪除(Deletion) $O(1)$ $O(1)$

空間複雜度

$O(n)$

空間複雜度隨著 Stack 中元素的數量線性增長

利用 JS 模擬 Stack

Js Array寫法

我們可以利用js array達成stack效果，利用push新增資料在末端，要取出資料使用pop方法即可

let stack = [];
stack.push(92); // 新增資料
stack.push(46);
stack.push(51);
stack.push(53);

stack.pop(); // 移除尾端資料

Object Property

以下利用物件導向實作

初始化Node

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

初始化Stack

新增頭跟尾

class Stack {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

Stack新增push方法

將物件插入 Stack 的頂端。


(圖片來自於visualgo)

  1. 創建一個新的節點 newNode 並將其初始化為 value。
  2. 檢查是否為空串列，是的話則將 head 和 tail 都指向新的節點
  3. 否則將 head 指向新的節點，並將新的節點的 next 屬性指向舊的 head（即舊的頂端）。
  4. stack 長度加一
push(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      let temp = this.head;
      this.head = newNode;
      this.head.next = temp;
    }
    this.length++;
}

Stack新增pop方法

移除並傳回在 Stack 頂端的物件。


(圖片來自於visualgo)

  1. 檢查是否為空列表，如果是，則返回 null
  2. 如果列表長度為 1，則將 head 和 tail 都設置為 null，並將列表長度設置為 0，最後返回被移除的節點
  3. 如果列表長度大於 1，則將 head 設置為它的下一個節點，並將列表長度減 1，最後返回被移除的節點。
pop(){
    if(this.head === null){
      return null;
    } else if(this.length === 1){
      let temp = this.head;
      this.head = null;
      this.tail = null;
      this.length = 0;
      return temp;
    } else {
      let temp = this.head;
      this.head = this.head.next;
      this.length--;
      return temp;
    }
}

Stack新增peek方法

傳回 Stack 頂端的物件而不需移除它。


(圖片來自於visualgo)

  1. 檢查head是否為空，如果是，則返回 null
  2. 否則回傳head的值
peek() {
    if(this.head === null){
      return null;
    } else {
        return this.head.value;
    }
}

實戰

20. Valid Parentheses

題目說明

給定一個僅包含字符 '('、')'、'{'、'}'、'[' 和 ']' 的字符串 s，確定輸入字符串是否有效。

如果滿足以下條件，則輸入字符串有效：

  • 開括號必須由相同類型的括號閉合。
  • 打開的括號必須以正確的順序關閉。
  • 每個閉括號都有一個對應的相同類型的開括號。

實戰

詳細解法

  1. 數組opened和closed被定義為分別表示左括號和右括號。 然後將字符串 s 轉換為稱為 sarray 的字符數組，並使用for循環遍歷sarray。
  2. 在循環的每次迭代中，檢查當前字符以查看它是否是左括號之一
  3. 如果是則將opened數組中的相應索引推送到stack數組中
  4. 如果不是，則當前字符必須是右括號
  5. 如果stack不為空，則檢查stack數組的最後一個元素，看它是否等於closed數組中的相應索引
  6. 如果等於相對應索引，則stack數組的最後一個元素pop出來（因為已找到匹配的括號並且可以將其刪除）
  7. 如果不是，函數返回 false
  8. 最後再檢查stack是否為空，空則返回true表示有效，否則反之
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let opened = ["(", "[", "{"]
    let closed = [")", "]", "}"]
    let sarray = [...s]
    let stack = []
    for (let i = 0; i < sarray.length; i++) {
        if (opened.includes(sarray[i])) {
            stack.push(opened.indexOf(sarray[i]))
        } else {
            if(stack.length != 0 && stack[stack.length - 1] == closed.indexOf(sarray[i])) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length > 0 ? false : true
};

[name=@joe94113] [time=Tue, Feb 5, 2023 10:00 PM] [color=#907bf7]