likes
comments
collection
share

JavaScript：栈详解

作者站长头像
站长
· 阅读数 61

引言

在计算机科学中，栈是一种重要的数据结构，它遵循后进先出（LIFO）的原则。这意味着最后加入栈的元素会第一个被移除。由于其这种特性，栈在许多编程场景中都非常有用，如函数调用、处理括号匹配问题、反转字符串等。在JavaScript中，虽然没有内置的栈类型，但我们可以使用数组来模拟栈的所有功能。

栈的基本概念

栈是一个只允许在一端进行插入或删除操作的特殊列表。栈的操作主要有四种：

  • 压栈（push） ：将元素放入栈顶。
  • 弹栈（pop） ：移除栈顶元素，并返回该元素。
  • 查看栈顶（peek） ：返回栈顶元素，不对栈进行修改。
  • 检查栈是否为空（isEmpty） ：判断栈是否为空，返回布尔值。

图解说明

接下来，我们可以为“压栈”和“弹栈”的操作制作一个简单的图解。这将帮助理解元素是如何被添加和删除的。

JavaScript：栈详解

栈的JavaScript实现

在JavaScript中，没有专门的栈来实现一端进出元素的功能，但我们可以使用数组来实现栈的功能，我们把一个数组看成是一个栈，然后只对一端进行插入删除操作，就可以实现栈的功能了。

下面是一个简单的栈类实现：

1. 压栈（push）

压栈操作是指将一个新元素添加到栈的顶部。这是栈数据结构中最常见的操作之一。

push(element) {
    this.items.push(element); // 将新元素添加到数组的末尾，即栈顶
}

2. 弹栈（pop）

弹栈操作是指移除栈顶的元素，并返回被移除的元素。这也是栈的基本操作，遵循后进先出（LIFO）的原则。

pop() {
    if (this.items.length == 0) {
        return "Underflow"; // 如果栈为空，返回"Underflow"
    }
    return this.items.pop(); // 移除并返回数组的最后一个元素，即栈顶元素
}

3. 查看栈顶（peek）

查看栈顶操作是指返回栈顶的元素，但不移除它。这允许我们查看最后一个添加到栈中的元素。

peek() {
    return this.items[this.items.length - 1]; // 返回数组的最后一个元素，即栈顶元素，不修改栈
}

4. 检查栈是否为空（isEmpty）

检查栈是否为空是一个实用操作，用于判断栈内是否还有元素。如果栈为空，返回true；否则，返回false。

isEmpty() {
    return this.items.length === 0; // 如果数组长度为0，表示栈为空，返回true
}

这个栈类使用数组items来存储栈的元素。push方法用于添加元素到栈顶，pop用于移除栈顶元素，peek则返回栈顶元素而不移除它，isEmpty用来检查栈是否为空。

栈的应用场景

栈在算法和日常编程中的应用非常广泛。例如，在浏览器的函数调用栈中管理函数调用过程，或者在解析和执行表达式时使用栈来处理操作符和操作数。此外，栈也常用于回溯算法中，例如解决迷宫或括号匹配问题。

算法题示例

设计一个算法，判断一个给定的字符串是否是有效的括号序列。括号序列包括小括号 '(' 和 ')'，中括号 '[' 和 ']'，大括号 '{' 和 '}'，且括号必须以正确的顺序闭合。

例如：

  1. 输入："()"，输出：true
  2. 输入："()[]{}"，输出：true
  3. 输入："(]"，输出：false
  4. 输入："([)]"，输出：false
  5. 输入："{[]}"，输出：true

解析： 这道题可以使用栈来解决。遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，判断栈顶是否是与之对应的左括号，如果是，则将栈顶元素弹出，否则返回 false。最后，如果栈为空，则说明所有的括号都被正确闭合，返回 true；否则，返回 false。

下面是该算法的详细解析：

function isValid(s) {
  // 创建一个空栈
  let stack = [];
  // 定义左括号和右括号的对应关系
  let mapping = {')': '(', ']': '[', '}': '{'};
  
  // 遍历字符串
  for (let char of s) {
      // 如果是左括号，压入栈中
      if (Object.values(mapping).includes(char)) {
          stack.push(char);
      }
      // 如果是右括号
      else if (char in mapping) {
          // 如果栈为空或者栈顶元素不是与之对应的左括号，则返回 False
          if (stack.length === 0 || mapping[char] !== stack.pop()) {
              return false;
          }
      }
      else {
          // 如果是非括号字符，则跳过
          continue;
      }
  }
  
  // 如果栈为空，则说明所有的括号都被正确闭合，返回 True；否则，返回 False
  return stack.length === 0;
}

// 测试
console.log(isValid("()"));      // 输出：true
console.log(isValid("()[]{}"));  // 输出：true
console.log(isValid("(]"));      // 输出：false
console.log(isValid("([)]"));    // 输出：false
console.log(isValid("{[]}"));    // 输出：true

该算法的时间复杂度为 O(n)，其中 n 是输入字符串的长度。因为我们只需一次遍历输入字符串，并且栈的操作都是 O(1) 的时间复杂度。

总结

栈的简洁性和高效性使其在解决类似问题时非常有用。掌握栈的操作和应用能够帮助你更好地理解和实现复杂的算法和数据结构。通过本文，你不仅学会了如何在JavaScript中实现和使用栈，还解决了一个常见的算法问题，希望你能在今后的编程和算法学习中，能够灵活运用栈来简化问题解决过程。

转载自:https://juejin.cn/post/7366967246374223891
评论
请登录