JavaScript数据结构之栈实例用法

本文将会介绍栈在JavaScript中的实例用法以及栈作为一种数据结构的基本概念。

栈的定义

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端称作栈底，不含任何元素的栈称为空栈。

栈的应用场景

栈其应用场景是非常广泛的。在现实世界中，许多普通的场景都可以使用栈作为一个基本数据结构来解决。比如：

• 撤销、恢复操作
• 浏览器历史记录
• 实现编译器中的语法分析等

JavaScript中栈的实现

JavaScript是一种可以动态扩展数组的语言，因此我们可以使用数组来实现栈。在JavaScript中，我们可以使用以下方式来实现一个栈：

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 = []
  }
}

我们可以使用es6的class语法来创建一个stack类，其中此类主要有以下方法：

• push：添加一个元素到栈顶
• pop：移除栈顶的元素并返回该元素
• peek：返回栈顶的元素，但不移除它
• isEmpty：如果栈里没有任何元素就返回true，否则返回false
• size：返回栈里的元素个数
• clear：移除栈里的所有元素

栈的实例用法

示例1：括号匹配

在括号匹配的场景中，将所有的左括号（如“（”、“{”、“[”等）入栈，当我们遇到右括号（如“）”、“}”、“]”等）时，我们将会从栈中弹出相应的左括号，并检查两者是否匹配。如果这两个括号不匹配，那么我们就发现了一个不正确的字符串。

以下是使用stack类来实现的代码：

function isBracketMatching(str) {
  const stack = new Stack();

  for (let i = 0; i < str.length; i++) {
    const bracket = str.charAt(i);

    if (bracket === '(' || bracket === '{' || bracket === '[') {
      stack.push(bracket);
    } else if (bracket === ')' && stack.peek() === '(') {
      stack.pop();
    } else if (bracket === '}' && stack.peek() === '{') {
      stack.pop();
    } else if (bracket === ']' && stack.peek() === '[') {
      stack.pop();
    } else {
      return false;
    }
  }

  return stack.isEmpty();
}

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

以上面的代码为例，我们先定义了一个isBracketMatching函数，该函数接受一个字符串参数，判断该字符串中的括号是否匹配。我们创建一个新的stack对象，然后开始迭代这个字符串中的每一个字符。如果这个字符是一个左括号，我们把它放在栈顶。如果这个字符是一个右括号，我们将会检查栈顶元素是否匹配。如果匹配，我们就弹出栈顶元素。最后，如果所有的括号都已被匹配，那么栈里的元素将会全部被弹出，函数就会返回true。

示例2：进制转换

进制转换也是栈的经典应用场景之一。假设我们需要把一个数字从十进制转换成二进制。我们可以使用以下算法来实现：

function decimalToBinary(decimalNum) {
  const stack = new Stack();
  let binaryStr = '';

  while (decimalNum > 0) {
    const binaryDigit = decimalNum % 2;
    decimalNum = Math.floor(decimalNum / 2);
    stack.push(binaryDigit);
  }

  while (!stack.isEmpty()) {
    binaryStr += stack.pop().toString();
  }

  return binaryStr;
}

console.log(decimalToBinary(10)); // 1010
console.log(decimalToBinary(100)); // 1100100
console.log(decimalToBinary(1000)); // 1111101000

我们定义了一个名为decimalToBinary的函数，它接受一个十进制数字作为参数，然后使用乘以2和取余数的方式来计算这个数字的二进制表示。然后，我们可以将每一个计算得到的0或1入栈，直到数字变成了0为止。最后，我们弹出栈中得到的每一个0或1，将它们组合成一个字符串，这就是这个数字的二进制表示。