1. 認(rèn)識(shí)棧結(jié)構(gòu)

棧是一種 后進(jìn)先出（LIFO） 的數(shù)據(jù)結(jié)構(gòu)

在 js 中沒有棧，但我們可以用 數(shù)組或鏈表 實(shí)現(xiàn)棧的所有功能

棧的常用操作:

push（入棧）

pop（出棧）

peek（返回棧頂元素）

isEmpty（判斷是否為空棧）

size（返回棧里元素個(gè)數(shù)）

棧的結(jié)構(gòu)示意圖

2. 實(shí)現(xiàn)棧結(jié)構(gòu)的封裝

實(shí)現(xiàn)棧結(jié)構(gòu)有兩種比較常見的方式：

• 基于 數(shù)組 實(shí)現(xiàn)
• 基于 鏈表 實(shí)現(xiàn)

鏈表也是一種數(shù)據(jù)結(jié)構(gòu)，js 中沒有自帶鏈表結(jié)構(gòu)，后續(xù)會(huì)寫關(guān)于鏈表的文章，本章先使用數(shù)組來實(shí)現(xiàn)。

2.1 基于數(shù)組 v1 版

// 封裝一個(gè)棧
class ArrayStack {
  // 定義一個(gè)數(shù)組，用于存儲(chǔ)元素
  private data: any[] = [];
  constructor(data: any[]) {
    this.data = data || [];
  }
  // 實(shí)現(xiàn)棧中相關(guān)的操作方法
  // push 方法：將一個(gè)元素壓入棧中
  push(element: any): void {
    this.data.push(element);
  }
  // pop方法：將棧頂?shù)脑貜棾鰲＃ǚ祷爻鋈?，并且從棧頂移除?
  pop(): any {
    return this.data.pop();
  }
  // peek方法：返回棧頂元素
  peek(): any {
    return this.data[this.data.length - 1];
  }
  // isEmpty方法：判斷棧是否為空
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  // size放法：返回棧里元素個(gè)數(shù)
  size(): number {
    return this.data.length;
  }
}

測(cè)試：

const as = new ArrayStack();
as.push(1);
as.push(2);
as.pop();
as.push(3);
console.log(as); // ArrayStack { data: [ 1, 3 ] }

2.2 使用泛型重構(gòu) v2 版

上面我們已經(jīng)基于數(shù)組實(shí)現(xiàn)了一個(gè)棧結(jié)構(gòu)，其實(shí)是已經(jīng)可以使用了。

但是有個(gè)小問題就是并不能很好的限制棧中元素的類型，原因就是我們用了太多 any，這種情況下我們可以使用范型來限制

// 封裝一個(gè)棧
class ArrayStack<T = any> {
  // 定義一個(gè)數(shù)組，用于存儲(chǔ)元素
  private data: T[] = [];
  constructor(data: T[]) {
    this.data = data || [];
  }
  // 實(shí)現(xiàn)棧中相關(guān)的操作方法
  // push 方法：將一個(gè)元素壓入棧中
  push(element: T): void {
    this.data.push(element);
  }
  // pop方法：將棧頂?shù)脑貜棾鰲＃ǚ祷爻鋈ィ⑶覐臈ｍ斠瞥?
  pop(): T | undefined {
    return this.data.pop();
  }
  // peek方法：返回棧頂元素
  peek(): T | undefined {
    return this.data[this.data.length - 1];
  }
  // isEmpty方法：判斷棧是否為空
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  // size放法：返回棧里元素個(gè)數(shù)
  size(): number {
    return this.data.length;
  }
}

測(cè)試：

const as = new ArrayStack<number>();
as.push(1);
as.push('2'); // ?? 類型“string”的參數(shù)不能賦給類型“number”的參數(shù)。
as.push(2); 
as.pop();
as.push(3);
console.log(as);

3. 實(shí)戰(zhàn)一：有效的括號(hào)

這道題來自 Leetcode 上的第 20 道題，難度：簡(jiǎn)單

3.1 題目描述

給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

• 左括號(hào)必須用相同類型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。
• 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。

示例 1：

輸入： s = "()"
輸出： true

示例 2：

輸入： s = "()[]{}"
輸出： true

示例 3：

輸入： s = "(]"
輸出： false

提示：

• 1 <= s.length <= 104
• s 僅由括號(hào) '()[]{}' 組成

3.2 題目分析

這是一道非常經(jīng)典的關(guān)于 棧 的面試題

我們只需要維護(hù)一個(gè)棧結(jié)構(gòu)

遍歷給定的字符串 s：

遇到 [、{、( 這三種符號(hào)時(shí)將它們壓入棧，

遇到 ]、}、) 這三種符號(hào)時(shí)就取出棧頂元素與之對(duì)比，如果不能夠組成有效括號(hào)則函數(shù)直接返回 false，如果能則進(jìn)入下個(gè)循環(huán)比較

知道循環(huán)結(jié)束，判斷棧中元素如果為空則表示字符串有效，反之則無效

3.3 解一：棧

function isValid(s: string): boolean {
  const stack = new ArrayStack<string>();
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    switch (c) {
      case "{":
        stack.push("}");
        break;
      case "[":
        stack.push("]");
        break;
      case "(":
        stack.push(")");
        break;
      default:
        if (stack.pop() !== c) return false;
    }
  }
  return stack.isEmpty();
}

4. 實(shí)戰(zhàn)二：下一個(gè)更大元素 I

這道題是來自 Leetcode 上的第 496 道題，難度：簡(jiǎn)單

4.1 題目描述

nums1 中數(shù)字 x 的 下一個(gè)更大元素 是指 x 在 nums2 中對(duì)應(yīng)位置 右側(cè) 的 第一個(gè) 比 x ****大的元素。

給你兩個(gè) 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，下標(biāo)從 0 開始計(jì)數(shù)，其中nums1 是 nums2 的子集。

對(duì)于每個(gè) 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標(biāo) j ，并且在 nums2 確定 nums2[j] 的 下一個(gè)更大元素 。如果不存在下一個(gè)更大元素，那么本次查詢的答案是 -1 。

返回一個(gè)長(zhǎng)度為 nums1.length 的數(shù)組 **ans **作為答案，滿足 **ans[i] **是如上所述的 下一個(gè)更大元素 。

示例 1：

輸入： nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出： [-1,3,-1]
解釋： nums1 中每個(gè)值的下一個(gè)更大元素如下所述：
- 4 ，用加粗斜體標(biāo)識(shí)，nums2 = [1,3,4,2]。不存在下一個(gè)更大元素，所以答案是 -1 。
- 1 ，用加粗斜體標(biāo)識(shí)，nums2 = [1,3,4,2]。下一個(gè)更大元素是 3 。
- 2 ，用加粗斜體標(biāo)識(shí)，nums2 = [1,3,4,2]。不存在下一個(gè)更大元素，所以答案是 -1 。

示例 2：

輸入： nums1 = [2,4], nums2 = [1,2,3,4].
輸出： [3,-1]
解釋： nums1 中每個(gè)值的下一個(gè)更大元素如下所述：
- 2 ，用加粗斜體標(biāo)識(shí)，nums2 = [1,2,3,4]。下一個(gè)更大元素是 3 。
- 4 ，用加粗斜體標(biāo)識(shí)，nums2 = [1,2,3,4]。不存在下一個(gè)更大元素，所以答案是 -1 。

提示：

1 <= nums1.length <= nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 104

nums1和nums2中所有整數(shù) 互不相同

nums1 中的所有整數(shù)同樣出現(xiàn)在 nums2 中

4.2 解一：暴力

這道題可以通過暴力法解決。

思路：

• 雙重循環(huán)遍歷 nums1 和 nums2 兩個(gè)數(shù)組
• 在第一層遍歷 nums1 循環(huán)中，找出 nums1[i] 對(duì)應(yīng) 在 nums2 中的下標(biāo)位置 pos
• 從 pos + 1 位置開始遍歷 nums2 數(shù)組，查找比 nums[i] 大的數(shù)字

代碼：

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  let res: number[] = [];
  for (let i = 0; i < nums1.length; i++) {
    let pos: number = 0;
    for (let j = 0; j < nums2.length; j++) {
      if (nums2[j] === nums1[i]) {
        pos = j;
        break;
      }
    }
    if (pos === nums2.length - 1) res.push(-1);
    for (let j = pos + 1; j < nums2.length; j++) {
      if (nums2[j] > nums1[i]) {
        res.push(nums2[j]);
        break;
      }
      if (j >= nums2.length - 1) res.push(-1);
    }
  }
  return res;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(mn) ，其中 m 是 nums1 的長(zhǎng)度，n 是 nums2 的長(zhǎng)度。

空間復(fù)雜度：O(1)

4.3 解二：?jiǎn)握{(diào)棧

當(dāng)題目出現(xiàn)「找到最近一個(gè)比其大的元素」的字眼時(shí)，應(yīng)該要會(huì)想到「單調(diào)?！?。

解釋一下什么是單調(diào)棧：就是棧中存放的數(shù)據(jù)是有序的，比如：?jiǎn)握{(diào)遞增棧 和 單調(diào)遞減棧

思路：

• 創(chuàng)建一個(gè) map（哈希表），它的 key 為 nums2 中的值，value 為 key 值右側(cè)的 下一個(gè)更大元素
• 維護(hù)一個(gè) stack 單調(diào)棧，倒序遍歷 nums2 數(shù)組
• 在循環(huán)中比較 nums2[i] 與 單調(diào)棧中的值，將小于 nums2[i] 的值 pop 出，最后剩下的都是比 nums2[i] 大的數(shù)，且棧頂?shù)闹稻褪窍乱粋€(gè)更大元素
• 使用 map 哈希表記錄每個(gè) nums2[i] 對(duì)應(yīng)目標(biāo)值。

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const map = new Map<number, number>();
  const stack = new ArrayStack<number>();
  for (let i = nums2.length - 1; i >= 0; --i) {
    const num = nums2[i];
    while (stack.size() && num >= (stack.peek() as number)) {
      stack.pop();
    }
    map.set(num, stack.size() ? (stack.peek() as number) : -1);
    stack.push(num);
  }
  const res = new Array(nums1.length).fill(0).map((_, i) => map.get(nums1[i]) as number);
  return res;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(m + n) ，其中 m 是 nums1 的長(zhǎng)度，n 是 nums2 的長(zhǎng)度。

空間復(fù)雜度：O(n) 用于存儲(chǔ)哈希表 map

以上就是TypeScript數(shù)據(jù)結(jié)構(gòu)棧結(jié)構(gòu)Stack教程示例的詳細(xì)內(nèi)容，更多關(guān)于TypeScript數(shù)據(jù)結(jié)構(gòu)Stack的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論