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

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 { // 定义一个数组，用于存储元素 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(); 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(); for (let i = 0; i 

4. 实战二：下一个更大元素 I

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

4.1 题目描述

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

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

对于每个 0 <= i  ，找出满足 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[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(); const stack = new ArrayStack(); 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数据结构栈结构Stack教程示例的详细内容，更多关于TypeScript数据结构Stack的资料请关注0133技术站其它相关文章！