JS 栈|极客笔记

JS 栈

在计算机科学中，栈（stack）是一种具有特定规则的数据结构，遵循先进后出（FILO，First In Last Out）的原则。栈常用于实现函数调用、表达式求值等场景。

在 JavaScript 中，栈也有着重要的应用。本文将详细介绍 JavaScript 中栈的概念、实现及相关应用。

栈的概念

栈是一种具有限制访问位置的线性数据结构，只能在表的一端进行插入和删除操作。在栈中通常有两种基本操作：

入栈（push）：将元素添加到栈的顶部；
出栈（pop）：从栈的顶部删除元素。

栈的实现通常基于数组或链表。在 JavaScript 中，我们可以使用数组实现栈结构。

用数组实现栈

我们可以通过 JavaScript 的数组方法来实现栈的基本操作。

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  printStack() {
    let str = "";
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.printStack()); // Output: 1 2 3

console.log(stack.peek()); // Output: 3

console.log(stack.pop()); // Output: 3

console.log(stack.printStack()); // Output: 1 2

上面的代码实现了一个简单的栈结构，通过数组的 push 和 pop 方法来实现入栈和出栈操作。同时，还实现了 peek 方法用于返回栈顶元素，isEmpty 方法判断栈是否为空，以及 printStack 方法用于打印栈中的元素。

栈的应用

1. 函数调用栈

在 JavaScript 中，每当函数调用时，都会创建一个称为 “执行上下文” 的对象来存储函数的局部变量、参数和返回地址。这些执行上下文被压入一个称为 “调用栈” 的栈结构中，当函数执行结束后，将其从栈顶弹出。

function a() {
  b();
  console.log("In function a");
}

function b() {
  console.log("In function b");
}

a();

在上面的代码中，当函数 a 调用时，先执行函数 b，然后在函数 a 中打印输出。函数调用栈的顺序为：

将全局上下文入栈
执行函数 a，将函数 a 的上下文入栈
执行函数 b，将函数 b 的上下文入栈
函数 b 执行完毕，将函数 b 的上下文出栈
函数 a 执行完毕，将函数 a 的上下文出栈
全局上下文出栈

2. 表达式求值

栈也可以用于表达式求值，例如计算后缀表达式。根据后缀表达式的特点，可以通过栈来实现其求值过程。

function evaluatePostfixExpression(expression) {
  const stack = new Stack();

  for (let i = 0; i < expression.length; i++) {
    const char = expression[i];

    if (!isNaN(parseInt(char))) {
      stack.push(parseInt(char));
    } else {
      const num2 = stack.pop();
      const num1 = stack.pop();

      if (char === "+") {
        stack.push(num1 + num2);
      } else if (char === "-") {
        stack.push(num1 - num2);
      } else if (char === "*") {
        stack.push(num1 * num2);
      } else if (char === "/") {
        stack.push(num1 / num2);
      }
    }
  }

  return stack.pop();
}

const postfixExpression = "53+";
console.log(evaluatePostfixExpression(postfixExpression)); // Output: 8

在上面的代码中，我们通过栈实现了一个简单的后缀表达式求值器。遍历后缀表达式，如果是数字则入栈，如果是运算符则从栈中取出两个操作数计算并将结果入栈，最终返回栈顶的计算结果。