简单了解JavaScript数据结构与算法之栈

1. 什么是栈

栈是一种数据结构，它最大的特点是是后进先出（LIFO，Last In First Out），也就是最后入栈的元素最先出栈。类比于现实生活中的栈，你往一个栈中塞东西，只能从栈的顶端抽出。栈可以理解为一个只能在栈顶进行插入和删除的线性表。

1.1 栈的基本操作

栈的基本操作包括：入栈（push），出栈（pop），查看栈顶元素（peek） 和 判断栈是否为空（isEmpty）。

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

2. 栈的应用

2.1 函数调用栈

栈在计算机科学中有着广泛的应用，一个经典的例子是函数调用栈。当你调用一个函数时，你在当前的栈顶压入一个函数的栈帧（包括函数的返回地址、局部变量等信息），当函数执行完成后，从栈顶弹出这个栈帧。这个过程一直重复，直到程序的结束。

2.2 浏览器的前进后退

在浏览器中，点击网页上的链接时，浏览器就会把这个链接对应的网页地址压到一个栈里面，我们称之为前进栈。当我们点击浏览器的后退按钮时，浏览器就会从前进栈中弹出最顶部的网页地址，把它压入后退栈中。当我们再次点击前进按钮时，浏览器就会从后退栈中弹出最顶部的网页地址，把它压回前进栈中。

2.3 匹配括号

栈还有一个常见的应用是判断一个字符串中的括号是否匹配。这个问题可以用栈很容易地解决。我们从左到右扫描字符串，遇到左括号的时候，把它压入栈中；遇到右括号的时候，从栈中弹出一个左括号，如果弹出失败或者弹出的左括号与右括号不匹配，那么说明这个括号不匹配；最后当我们扫描完整个字符串且栈为空时，说明字符串中的括号全部匹配。

function isBracketMatch(str) {
  const stack = [];
  for (let i = 0; i < str.length; i++) {
    const c = str.charAt(i);
    if (c === '(') {
      stack.push(c);
    } else if (c === ')') {
      if (stack.pop() !== '(') {
        return false;
      }
    }
  }
  return stack.length === 0;
}

3. 小结

栈是一种非常简单但又非常有用的数据结构，它可以解决一些非常实际的问题（如函数调用栈、浏览器的前进后退、括号匹配等）。理解栈这种数据结构对于提高程序员的编程能力有着非常大的帮助。