1. 认识栈结构

栈是一种 后进先出（LIFO） 的数据结构
在 js 中没有栈，但我们可以用 数组或链表 实现栈的所有功能
栈的常用操作:
1. push（入栈）
2. pop（出栈）
3. peek（返回栈顶元素）
4. isEmpty（判断是否为空栈）
5. size（返回栈里元素个数）

栈的结构示意图

2. 实现栈结构的封装

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

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

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

2.1 基于数组 v1 版

typescript
// 封装一个栈
class ArrayStack {
  // 定义一个数组，用于存储元素
  private data: any[] = [];

  // 实现栈中相关的操作方法
  // 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;
  }
}

测试：

typescript
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，这种情况下我们可以使用范型来限制

ts
// 封装一个栈
class ArrayStack<T = any> {
  // 定义一个数组，用于存储元素
  private data: T[] = [];

  // 实现栈中相关的操作方法
  // 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;
  }
}

测试：

ts
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

提示：

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

3.2 题目分析

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

我们只需要维护一个栈结构
遍历给定的字符串 s：
1. 遇到 [、{、( 这三种符号时将它们压入栈，
2. 遇到 ]、}、) 这三种符号时就取出栈顶元素与之对比，如果不能够组成有效括号则函数直接返回 false，如果能则进入下个循环比较
3. 知道循环结束，判断栈中元素如果为空则表示字符串有效，反之则无效

3.3 解一：栈

ts
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] 大的数字

代码：

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

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

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