---
tags: 資料結構, LeetCode
disqus: HackMD
---

# 堆疊(Stack)

:::spoiler 文章目錄
[toc]
:::

## 介紹

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

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

(圖片取自於[Stacks & Queues](https://medium.com/@joshalphonse/stacks-queues-97037b3c01c6))

## 複雜度

### 時間複雜度

| 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](https://visualgo.net/zh/list))

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](https://visualgo.net/zh/list))

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](https://visualgo.net/zh/list))

1. 檢查`head`是否為空，如果是，則返回 `null`
2. 否則回傳`head`的值

peek() {
    if(this.head === null){
      return null;
    } else {
        return this.head.value;
    }
}

## 實戰

[20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

### 題目說明

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

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

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


### 實戰

[詳細解法](https://leetcode.com/problems/valid-parentheses/solutions/2956907/beats-93-84-detailed-javascript-solution/?orderBy=hot)

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]