栈介绍

上一篇说完时间复杂度，第三篇开始讲栈，栈在算法中也是不可或缺的数据结构

什么是栈

栈是一种遵循后进先出（LIFO，Last In First Out）原则的有序集合。这意味着最后添加到栈中的元素会是第一个被移除的元素。栈的插入操作称为“推入”（push），删除操作称为“弹出”（pop），此外，通常还有一个操作是查看栈顶元素而不移除它，这称为“窥视”（peek）。

栈的特点

• 后进先出（LIFO）：最后添加的元素最早被移除。
• 操作限制：栈的操作主要限制在栈的一端，即只在栈顶进行插入和删除。
• 访问限制：不能直接访问栈中的任意元素，只能访问栈顶元素。

JavaScript中的栈

JavaScript 没有内置的栈数据结构，但可以很容易地用数组实现栈的所有功能，因为 JavaScript 的数组自带了处理栈操作的方法，如 push() 和 pop()。

如何在JavaScript中模拟栈

以下是使用JavaScript模拟栈的基本实现：

class Stack {
  constructor() {
    this.items = []; // 使用数组存储栈元素
  }

  // 向栈中添加元素
  push(element) {
    this.items.push(element);
  }

  // 从栈中移除元素
  pop() {
    if (this.isEmpty()) throw "Stack is empty";
    return this.items.pop();
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) throw "Stack is empty";
    return this.items[this.items.length - 1];
  }

  // 检查栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取栈的大小
  size() {
    return this.items.length;
  }

  // 清空栈
  clear() {
    this.items = [];
  }
}

栈的应用场景

十进制转二进制

十进制转二进制的过程可以通过不断地将十进制数除以2，并记录下每次的余数（0或1），最后将这些余数逆序排列得到二进制表示。使用栈（后进先出的数据结构）可以方便地实现这个逆序排列的过程，因为我们可以将余数推入栈中，然后再依次弹出，依次弹出的顺序即是我们所需要的逆序。

具体步骤：

1. 初始化一个空栈：用于存放余数。
2. 循环除以2：将十进制数除以2，将得到的余数推入栈中。然后更新被除数为原数除以2的商，向下取整。
3. 重复操作：重复第2步，直到十进制数变为0。
4. 构造二进制结果：栈中的元素依次弹出，这个弹出的顺序就是二进制数的正确顺序。

现在，我们用JavaScript代码来实施这个算法：

function decimalToBinary(decNumber) {
  const remStack = new Stack(); // 创建一个新的栈实例
  let number = decNumber; // 需要转换的十进制数
  let binaryString = ''; // 存储二进制结果的字符串
  let remainder; // 存储每次除以2的余数

  // 不断除以2，直到数变为0
  while (number > 0) {
    remainder = Math.floor(number % 2);
    remStack.push(remainder); // 将余数推入栈中
    number = Math.floor(number / 2);
  }

  // 弹出栈元素构造二进制字符串
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString();
  }

  return binaryString;
}

// 测试函数
console.log(decimalToBinary(233)); // 输出应该是11101001

函数调用堆栈

想必这个前端不会陌生，以一个简单的例子来说明函数调用堆栈的执行过程：

function first() {
  second();
  console.log('第一个函数执行');
}
function second() {
  third();
  console.log('第二个函数执行');
}
function third() {
  console.log('第三个函数执行');
}

first();

执行流程如下：

1. first() 被调用，为 first 函数创建一个新的帧并将其推入堆栈。
2. 在 first 函数内部，second() 被调用，为 second 函数创建一个新的帧并将其推入堆栈的顶部。
3. 接着，second 函数内部调用了 third()，为 third 函数创建一个新的帧并将其推入堆栈顶部。
4. third() 函数执行，并打印出消息。完成后，其帧从堆栈中弹出。
5. 接下来，控制回到 second 函数，它继续执行并打印出消息。完成后，其帧从堆栈中弹出。
6. 最后，控制回到 first 函数，它继续执行并打印出消息。完成后，其帧从堆栈中弹出。

括号匹配

这是一个简单的算法题，要判断字符串中的括号是否有效，我们可以使用栈的数据结构。

基本思路：

遍历字符串，每次遇到一个开括号，就将其推入栈中；遇到闭括号时，检查栈顶元素是否是与之匹配的开括号，如果是，则将栈顶的元素弹出；如果不是或者栈为空，则说明括号无效。若所有的括号都能找到匹配的另一半，且最后栈为空，则该字符串中的括号有效。

下面是使用JavaScript来实现这个算法的示例：

// 检查括号是否有效的函数
function isValidParentheses(s) {
    // 使用之前定义的Stack类
  const stack = new Stack();
  const parenthesesMap = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    
    if (['(', '[', '{'].includes(char)) {
      // 遇到开括号，推入栈
      stack.push(char);
    } else if ([')', ']', '}'].includes(char)) {
      // 遇到闭括号，检查栈顶元素
      if (stack.peek() === parenthesesMap[char]) {
        // 栈顶元素是匹配的开括号，弹出栈顶元素
        stack.pop();
      } else {
        // 栈顶元素不匹配或栈为空，括号无效
        return false;
      }
    }
  }
  
  // 字符串遍历完成后，检查栈是否为空
  return stack.isEmpty();
}

// 测试示例
console.log(isValidParentheses("()")); // 应该返回 true
console.log(isValidParentheses("()[]{}")); // 应该返回 true
console.log(isValidParentheses("(]")); // 应该返回 false
console.log(isValidParentheses("([)]")); // 应该返回 false
console.log(isValidParentheses("{[]}")); // 应该返回 true

这段代码定义了一个isValidParentheses函数，它接收一个字符串s作为输入，并返回一个布尔值表示括号是否有效。我们使用Stack类作为辅助数据结构，用来存放遇到的开括号，并在遇到闭括号时检查栈顶的开括号是否与之匹配。

总结

总而言之，栈是一种重要的数据结构，它的特性为后进先出（LIFO，Last In First Out）。这种特性使得栈在处理类似于反转顺序、函数调用、符号匹配等问题时非常有效。