前言

原文来自我的个人博客

1. 认识栈结构

1. 栈是一种 后进先出（LIFO） 的数据结构
2. 在 js 中没有栈，但我们可以用 数组或链表 实现栈的所有功能

3. 栈的常用操作:

   1. `push（入栈）`
   2. `pop（出栈）`
   3. `peek（返回栈顶元素）`
   4. `isEmpty（判断是否为空栈）`
   5. `size（返回栈里元素个数）` 
   

栈的结构示意图

# 2. 实现栈结构的封装

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

1. 基于 数组 实现

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. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

3.2 题目分析

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

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

2. 遍历给定的字符串 s：

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

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 解一：暴力

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

思路：

1. 双重循环遍历 nums1 和 nums2 两个数组
2. 在第一层遍历 nums1 循环中，找出 nums1[i] 对应 在 nums2 中的下标位置 pos
3. 从 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 解二：单调栈

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

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

思路：

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