JS中数据结构之栈

接下来我将为大家讲解JS中数据结构之栈的完整攻略。

一、栈的定义

栈是一种受限的线性数据结构，它具有先进后出（Last In First Out, LIFO）的特点，即后进入的元素先出来。栈主要有两个操作：入栈和出栈，同时还需要考虑栈空和栈满两种特殊情况。

二、栈的实现

在JS中，可以通过数组来实现栈的功能。下面是一个实现栈的类：

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;
  }
  size() { // 返回栈的大小
    return this.items.length;
  }
  clear() { // 清空栈
    this.items = [];
  }
}

三、栈的应用

1. 判断括号是否匹配

栈可以用来判断括号是否匹配。例如给定一个字符串，其中包含一些括号，判断这些括号是否匹配。

function isMatchingBrackets(str) {
  const stack = new Stack();
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
      stack.push(str[i]);
    } else if (str[i] === ')' && stack.peek() === '(') {
      stack.pop();
    } else if (str[i] === ']' && stack.peek() === '[') {
      stack.pop();
    } else if (str[i] === '}' && stack.peek() === '{') {
      stack.pop();
    } else {
      return false;
    }
  }
  return stack.isEmpty();
}

console.log(isMatchingBrackets('([]{})')); // true
console.log(isMatchingBrackets('([]{})}')); // false

2. 函数调用栈

栈被广泛应用于函数调用过程中的“调用栈”中。当一个函数被调用时，它的返回地址和参数等信息被压入栈中，当函数执行完毕时，这些信息又被弹出栈。

下面是一个递归函数的示例：

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 输出 120

这个函数用到了递归，每次调用时都会将当前的n值压入栈中，当递归结束时才开始弹出栈中保存的信息，计算阶乘的值。

四、总结

本文介绍了JS中数据结构之栈，包括栈的定义、实现以及两个示例应用，希望对大家有所帮助。