1. 认识栈结构
栈是一种 后进先出（LIFO） 的数据结构
在 js 中没有栈，但我们可以用 数组或链表 实现栈的所有功能
栈的常用操作:
push（入栈）
pop（出栈）
peek（返回栈顶元素）
isEmpty（判断是否为空栈）
size（返回栈里元素个数）
栈的结构示意图
2. 实现栈结构的封装
实现栈结构有两种比较常见的方式：
基于 数组 实现基于 链表 实现
链表也是一种数据结构，js 中没有自带链表结构，后续会写关于链表的文章，本章先使用数组来实现。
2.1 基于数组 v1 版
测试：
2.2 使用泛型重构 v2 版
上面我们已经基于数组实现了一个栈结构，其实是已经可以使用了。
但是有个小问题就是并不能很好的限制栈中元素的类型，原因就是我们用了太多 any，这种情况下我们可以使用范型来限制
测试：
3. 实战一：有效的括号
这道题来自 Leetcode 上的第 20 道题，难度：简单
3.1 题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入： s = "()"输出： true
示例 2：
输入： s = "()[]{}"输出： true
示例 3：
输入： s = "(]"输出： false
提示：
1 <= s.length <= 104s 仅由括号 '()[]{}' 组成
3.2 题目分析
这是一道非常经典的关于 栈 的面试题
我们只需要维护一个栈结构
遍历给定的字符串 s：
遇到 [、{、( 这三种符号时将它们压入栈，
遇到 ]、}、) 这三种符号时就取出栈顶元素与之对比，如果不能够组成有效括号则函数直接返回 false，如果能则进入下个循环比较
知道循环结束，判断栈中元素如果为空则表示字符串有效，反之则无效
3.3 解一：栈
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] 大的数字
代码：
复杂度分析
时间复杂度：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] 对应目标值。
复杂度分析
时间复杂度：O(m + n) ，其中 m 是 nums1 的长度，n 是 nums2 的长度。
空间复杂度：O(n) 用于存储哈希表 map
以上就是TypeScript数据结构栈结构Stack教程示例的详细内容，更多关于TypeScript数据结构Stack的资料请关注脚本之家其它相关文章！
您可能感兴趣的文章:前端算法之TypeScript包含min函数的栈实例详解TypeScript调整数组元素顺序算法TypeScript合并两个排序链表的方法详解Typescript tsconfig.json的配置详情TypeScript手写一个简单的eslint插件实例TypeScript数据结构之队列结构Queue教程示例TypeScript实现十大排序算法之归并排序示例详解
