TypeScript数据结构栈结构Stack教程示例

时间:2023-03-20 前端要努力QAQ 人气:0

1. 认识栈结构

栈是一种后进先出（LIFO）的数据结构

在 js 中没有栈，但我们可以用数组或链表实现栈的所有功能

栈的常用操作:

push（入栈）

pop（出栈）

peek（返回栈顶元素）

isEmpty（判断是否为空栈）

size（返回栈里元素个数）

栈的结构示意图

2. 实现栈结构的封装

实现栈结构有两种比较常见的方式：

基于数组实现
基于链表实现

链表也是一种数据结构，js 中没有自带链表结构，后续会写关于链表的文章，本章先使用数组来实现。

2.1 基于数组 v1 版

// 封装一个栈
class ArrayStack {
  // 定义一个数组，用于存储元素
  private data: any[] = [];
  constructor(data: any[]) {
    this.data = data || [];
  }
  // 实现栈中相关的操作方法
  // push 方法：将一个元素压入栈中
  push(element: any): void {
    this.data.push(element);
  }
  // pop方法：将栈顶的元素弹出栈（返回出去，并且从栈顶移除）
  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放法：返回栈里元素个数
  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 版

上面我们已经基于数组实现了一个栈结构，其实是已经可以使用了。

但是有个小问题就是并不能很好的限制栈中元素的类型，原因就是我们用了太多 any，这种情况下我们可以使用范型来限制

// 封装一个栈
class ArrayStack&lt;T = any&gt; {
  // 定义一个数组，用于存储元素
  private data: T[] = [];
  constructor(data: T[]) {
    this.data = data || [];
  }
  // 实现栈中相关的操作方法
  // push 方法：将一个元素压入栈中
  push(element: T): void {
    this.data.push(element);
  }
  // pop方法：将栈顶的元素弹出栈（返回出去，并且从栈顶移除）
  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放法：返回栈里元素个数
  size(): number {
    return this.data.length;
  }
}

测试：

const as = new ArrayStack&lt;number&gt;();
as.push(1);
as.push('2'); // ✖️ 类型“string”的参数不能赋给类型“number”的参数。
as.push(2); 
as.pop();
as.push(3);
console.log(as);

3. 实战一：有效的括号

这道题来自 Leetcode 上的第 20 道题，难度：简单

3.1 题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

3.2 题目分析

这是一道非常经典的关于栈的面试题

我们只需要维护一个栈结构

遍历给定的字符串 s：

遇到 [、{、( 这三种符号时将它们压入栈，

遇到 ]、}、) 这三种符号时就取出栈顶元素与之对比，如果不能够组成有效括号则函数直接返回 false，如果能则进入下个循环比较

知道循环结束，判断栈中元素如果为空则表示字符串有效，反之则无效

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. 实战二：下一个更大元素 I

这道题是来自 Leetcode 上的第 496 道题，难度：简单

4.1 题目描述

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x ****大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 **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中所有整数互不相同

nums1 中的所有整数同样出现在 nums2 中

4.2 解一：暴力

这道题可以通过暴力法解决。

思路：

双重循环遍历 nums1 和 nums2 两个数组
在第一层遍历 nums1 循环中，找出 nums1[i] 对应在 nums2 中的下标位置 pos
从 pos + 1 位置开始遍历 nums2 数组，查找比 nums[i] 大的数字

代码：

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 解二：单调栈

当题目出现「找到最近一个比其大的元素」的字眼时，应该要会想到「单调栈」。

解释一下什么是单调栈：就是栈中存放的数据是有序的，比如：单调递增栈和单调递减栈

思路：

创建一个 map（哈希表），它的 key 为 nums2 中的值，value 为 key 值右侧的下一个更大元素
维护一个 stack 单调栈，倒序遍历 nums2 数组
在循环中比较 nums2[i] 与单调栈中的值，将小于 nums2[i] 的值 pop 出，最后剩下的都是比 nums2[i] 大的数，且栈顶的值就是下一个更大元素
使用 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

加载全部内容