腳本之家服務器常用軟件

快捷導航

TypeScript數(shù)據(jù)結構棧結構Stack教程示例

更新時間：2023年02月05日 10:11:32 作者：前端要努力QAQ

這篇文章主要為大家介紹了TypeScript數(shù)據(jù)結構棧結構Stack教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

1. 認識棧結構

棧是一種后進先出（LIFO）的數(shù)據(jù)結構

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

棧的常用操作:

push（入棧）

pop（出棧）

peek（返回棧頂元素）

isEmpty（判斷是否為空棧）

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

棧的結構示意圖

2. 實現(xiàn)棧結構的封裝

實現(xiàn)棧結構有兩種比較常見的方式：

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

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

2.1 基于數(shù)組 v1 版

// 封裝一個棧
class ArrayStack {
  // 定義一個數(shù)組，用于存儲元素
  private data: any[] = [];
  constructor(data: any[]) {
    this.data = data || [];
  }
  // 實現(xiàn)棧中相關的操作方法
  // push 方法：將一個元素壓入棧中
  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放法：返回棧里元素個數(shù)
  size(): number {
    return this.data.length;
  }
}

測試：

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

2.2 使用泛型重構 v2 版

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

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

// 封裝一個棧
class ArrayStack&lt;T = any&gt; {
  // 定義一個數(shù)組，用于存儲元素
  private data: T[] = [];
  constructor(data: T[]) {
    this.data = data || [];
  }
  // 實現(xiàn)棧中相關的操作方法
  // push 方法：將一個元素壓入棧中
  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放法：返回棧里元素個數(shù)
  size(): number {
    return this.data.length;
  }
}

測試：

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

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

這道題來自 Leetcode 上的第 20 道題，難度：簡單

3.1 題目描述

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

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

3.2 題目分析

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

我們只需要維護一個棧結構

遍歷給定的字符串 s：

遇到 [、{、( 這三種符號時將它們壓入棧，

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

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

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. 實戰(zhàn)二：下一個更大元素 I

這道題是來自 Leetcode 上的第 496 道題，難度：簡單

4.1 題目描述

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

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

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

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

示例 1：

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

示例 2：

輸入： nums1 = [2,4], nums2 = [1,2,3,4].
輸出： [3,-1]
解釋： nums1 中每個值的下一個更大元素如下所述：
- 2 ，用加粗斜體標識，nums2 = [1,2,3,4]。下一個更大元素是 3 。
- 4 ，用加粗斜體標識，nums2 = [1,2,3,4]。不存在下一個更大元素，所以答案是 -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 兩個數(shù)組
在第一層遍歷 nums1 循環(huán)中，找出 nums1[i] 對應在 nums2 中的下標位置 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;
}

復雜度分析

時間復雜度：O(mn) ，其中 m 是 nums1 的長度，n 是 nums2 的長度。

空間復雜度：O(1)

4.3 解二：單調(diào)棧

當題目出現(xiàn)「找到最近一個比其大的元素」的字眼時，應該要會想到「單調(diào)?！?。

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

思路：

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

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;
}

復雜度分析

時間復雜度：O(m + n) ，其中 m 是 nums1 的長度，n 是 nums2 的長度。

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

以上就是TypeScript數(shù)據(jù)結構棧結構Stack教程示例的詳細內(nèi)容，更多關于TypeScript數(shù)據(jù)結構Stack的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: