JS中的算法与数据结构之栈(Stack)实例详解

什么是栈？

栈（Stack）是一种遵从后进先出（LIFO）原则的有序集合，是一种线性数据结构，只允许在栈顶进行插入和删除操作。

如何实现栈？

JavaScript中可以通过数组来实现栈，使用数组的pop()、push()方法可以轻松地实现栈的相关操作。

创建一个栈（Stack）类

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 bracketsMatch(str) {
  let stack = new Stack();
  let arr = str.split('');
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == '(') {
      stack.push(arr[i]);
    } else if (arr[i] == ')') {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty();
}

console.log(bracketsMatch('(a+b)*(c-d)')); // true
console.log(bracketsMatch('(a+b)*((c-d)')); // false

示例 2: 使用栈实现进制转换

function decimalToBinary(decimalNum) {
  let stack = new Stack();
  while (decimalNum > 0) {
    let remainder = decimalNum % 2;
    stack.push(remainder);
    decimalNum = Math.floor(decimalNum / 2);
  }
  let binaryStr = '';
  while (!stack.isEmpty()) {
    binaryStr += stack.pop().toString();
  }
  return binaryStr;
}

console.log(decimalToBinary(10)); // '1010'
console.log(decimalToBinary(23)); // '10111'

总结

栈是一种常用的数据结构，使用栈可以方便地实现多种算法和问题的解决方案。在JavaScript中可以通过数组来实现栈的相关操作，也可以通过递归等方式实现栈的应用。