JavaScript版:資料結構之“棧”

語言: CN / TW / HK

theme: juejin

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

1. 棧是什麼?

image.png - 一種先進後出的資料結構; - JavaScript沒有棧的結構;可以用array實現棧的功能 - 入棧 push(x); - 出棧 pop();

image.png ```js const stack = [];

// 入棧 stack.push(1); stack.push(2);

// 出棧 const item1 = stack.pop(); const item2 = stack.pop(); ```

2. 什麼場景下用棧

所有後進先出的結構。

2.1 十進位制轉換為二進位制:最後餘數要倒敘輸出才是正確二進位制;

image.png

  • 後出來的餘數反而要排到前面
  • 把餘數依次入棧,然後出棧,就可以實現餘數倒敘輸出。

2.2 判斷括號是否合法:左括號進棧,右括號出棧,棧空則合法;

image.png

  • 越靠後的左括號,對應的右括號越靠前
  • 左括號入棧,右括號出棧,最後棧空了就是合法的

2.3 函式呼叫棧:最後呼叫的函式,最先執行完;

image.png - 最後呼叫的函式,最先執行完 - JS直譯器使用棧來控制函式呼叫的順序

3. leetcode: 20. 有效的括號

valid-parentheses

image.png

3.1 解題思路

對於沒有閉合的左括號而言,越靠後的左括號,對應的右括號越靠前 js 輸入: "{[]}" 輸出:true

3.2 解題步驟

  • 新建一個棧
  • 掃描字串,遇左括號入棧,遇到和棧頂括號型別匹配的右括號就出棧,型別不匹配直接判定為不合法 ```js /**
  • @param {string} s
  • @return {boolean} */ var isValid = function (s) { if (s.length % 2 === 1) { return false } const stack = []; for (let i = 0; i < s.length; i += 1) { const c = s[i]; if (c === '(' || c === '{' || c === '[') { stack.push(c) } else { const t = stack[stack.length - 1]; if ( (t === '(' && c === ')') || (t === '{' && c === '}') || (t === '[' && c === ']') ) { stack.pop(); } else { return false; } } } return stack.length === 0; }; ```

4. 前端與棧:JS中的函式呼叫棧

後進先出 ```js const func1 = () => { func2(); }; const func2 = () => { func3(); }; const func3 = () => {};

func1();

```

image.png

5. LeetCode:144. 二叉樹的前序遍歷

學習這個題之前,要先了解下什麼是二叉樹·~~

image.png 進階: 遞迴演算法很簡單,你可以通過迭代演算法完成嗎?

利用棧模擬遞迴,改寫遞迴 js /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function (root) { const res = []; const stack = []; if (root) stack.push(root) while (stack.length) { const n = stack.pop(); res.push(n.val) if (n.right) stack.push(n.right) if (n.left) stack.push(n.left) } return res };

6. 棧-總結

  • 棧是一個後進先出的資料結構
  • JavaScript沒有棧的結構;可以用array實現棧的功能
  • 棧常用操作: 入棧 push(x);出棧 pop();最後元素 stack[stack.length - 1]