前言

后进先出（Last In, First Out，LIFO）是栈（Stack）这种数据结构的核心特性。栈是一种具有特定操作的线性数据结构，其基本操作包括压入（push）和弹出（pop）元素。栈的特点是只能在一端进行插入和删除操作，这一端被称为栈顶，而另一端被称为栈底。

当你向栈中压入（push）一个元素时，该元素被放置在当前栈顶的位置上；而当你从栈中弹出（pop）一个元素时，栈顶的元素被移除，并且下一个元素成为新的栈顶。因此，最后被压入栈的元素最先被弹出，这就是“后进先出”的含义。

栈常常用于需要临时存储和恢复数据顺序的场景，比如函数调用的执行过程中需要保存函数的调用信息，递归算法的实现中需要保存递归调用的上下文等。另外，栈还广泛应用于计算机科学中的算法和数据结构，例如表达式求值、深度优先搜索、逆波兰表达式转换等。

数组复习

因为栈本质上就是一种受到限制的数组，因此我们先进行数组内容的复习。

数组中map方法

我们通过new的方式创建一个有长度的数组，再通过fill方法去填充1，这样子我们就得到了具有7个1的数组。数组中有一个map方法。里面的函数可以接受三个参数，其中分别表示当前元素，当前元素下标和数组（不常用），通常用作元素的遍历，其中这些作用foreach方法也有，但是map不同的点在于它可以改变数组中的元素然后返回新的数组，最后输出结果是7个2.

遍历数组元素

我们要操作数组，改变数组元素，可以通过for循环来操作

这个方法可以将数组中的元素全部变为字符串类型

数组基本方法

1. push往数组末尾推入元素，返回更新后数组的长度
2. unshift往数组头放入元素，返回更新后数组的长度
3. pop在数组末尾删除元素，返回删除的元素
4. shift删除数组头部元素，返回删除的元素
5. splice当后面传入两个值，第一个为删除下标的起始位置，第二个为要删除多少个，返回删除元素数组
6. splice后面传入三个值，第一个为插入元素起始位置，第二个为这个位置开始往后删除多少个元素，第三个为插入元素。返回删除的元素数组

栈

当我们把数组的基本内容复习完毕之后，就可以弄栈了，因为栈是后进先出的数据结构，因此栈是只有push和pop方法的特殊数组。

这个结果是先取出绿色心情，最后钟薛高。

之后让我们通过一道与栈有关的算法题来加深我们的理解

leetCode20

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

思路

这个问题可以使用栈来解决。我们可以遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，判断栈顶是否为相应的左括号，如果是，则弹出栈顶元素，继续遍历；如果不是，则返回 false。

最后，如果栈为空，则说明所有的括号都匹配，返回 true；如果栈不为空，则说明有未闭合的括号，返回 false。

var isValid = function(s) {
  // 初始化一个空栈
  let stack = [];
  
  // 遍历字符串 s 中的每个字符
  for (let i = 0; i < s.length; i++) {
      switch(s[i]) {
          // 如果是左括号，将对应的右括号压入栈中
          case '(':
              stack.push(')');
              break;
          case '{':
              stack.push('}');
              break;
          case '[':
              stack.push(']');
              break;
          // 如果是右括号
          default:
              // 弹出栈顶元素，并与当前字符比较是否匹配
              if (stack.pop() !== s[i]) {
                  return false; // 不匹配则返回 false
              }
      }
  }
  
  // 最后，如果栈为空，则说明所有括号都匹配，返回 true；否则返回 false
  return stack.length === 0;
};

过程

1. 首先，我们初始化一个空栈 stack，用来存储左括号。

2. 然后，我们遍历输入的字符串 s 中的每个字符。

3. 对于每个字符，我们使用 switch-case 语句来判断其类型：

   • 如果是左括号（(、{、[），则将对应的右括号压入栈中。

   • 如果是右括号，则与栈顶元素进行比较：

     • 如果栈为空或者栈顶元素与当前字符不匹配，则说明括号不配对，返回 false。
     • 如果匹配成功，则继续遍历下一个字符。

4. 最后，如果遍历结束后栈为空，则说明所有的括号都配对成功，返回 true；否则，返回 false。

这段代码利用了栈的后进先出（LIFO）特性来判断括号是否配对。如果在遍历过程中发现不匹配的括号，立即返回 false；如果遍历结束后栈为空，则说明所有的括号都配对成功，返回 true。