亲宝软件园·资讯

展开

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

前端要努力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<T = any> {
  // 定义一个数组,用于存储元素
  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<number>();
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

提示:

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

nums1nums2中所有整数 互不相同

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

4.2 解一:暴力

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

思路:

代码:

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) ,其中 mnums1 的长度,nnums2 的长度。

空间复杂度:O(1)

4.3 解二:单调栈

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

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

思路:

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) ,其中 mnums1 的长度,nnums2 的长度。

空间复杂度:O(n) 用于存储哈希表 map

加载全部内容

相关教程
猜你喜欢
用户评论