js中栈的运用
JavaScript 中栈的运用在 JavaScript 中，栈（Stack）是一种非常有用的数据结构，它遵循后进先出（Last In First Out，LIFO）的原则。在本文中，我们将深入探讨栈的概念以及在 JavaScript 中的实际运用。
一、栈的概念
栈是一种线性数据结构，它只能在一端进行插入（称为入栈或压栈，push）和删除（称为出栈或弹栈，pop）操作。想象一下一摞盘子，你只能从最上面拿盘子（出栈）或者把盘子放在最上面（入栈）。
栈通常具有以下几个基本操作：
[*]push(element)：将一个元素压入栈顶。
[*]pop()：弹出栈顶元素并返回它。
[*]peek()：查看栈顶元素，但不弹出它。
[*]isEmpty()：判断栈是否为空。
二、在 JavaScript 中实现栈
以下是用 JavaScript 实现一个简单栈的代码：
class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return "Underflow"; } return this.items.pop(); } peek() { if (this.isEmpty()) { return null; } return this.items; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; }}三、栈的实际运用
（一）表达式求值
[*]中缀表达式转后缀表达式
在计算机科学中，将中缀表达式转换为后缀表达式是栈的一个重要应用。中缀表达式是我们通常使用的算术表达式形式，如(2 + 3) * 4。后缀表达式则是将运算符放在操作数之后，例如2 3 + 4 *。
算法步骤如下：
[*]初始化一个空栈用于存储运算符。
[*]从左到右遍历中缀表达式。
[*]如果遇到操作数，直接输出。
[*]如果遇到左括号，将其压入栈。
[*]如果遇到右括号，弹出栈中的运算符并输出，直到遇到左括号，然后丢弃左括号。
[*]如果遇到运算符，根据其优先级进行处理。如果栈顶运算符的优先级高于或等于当前运算符，则弹出栈顶运算符并输出；否则，将当前运算符压入栈。
[*]遍历结束后，将栈中的剩余运算符依次弹出并输出。
以下是用 JavaScript 实现中缀表达式转后缀表达式的代码：
function infixToPostfix(expression) { const stack = new Stack(); let postfix = ""; const precedence = { '+': 1, '-': 1, '*': 2, '/': 2 }; for (let char of expression) { if (//.test(char)) { postfix += char; } else if (char === '(') { stack.push(char); } else if (char === ')') { while (!stack.isEmpty() && stack.peek()!== '(') { postfix += stack.pop(); } stack.pop(); // 弹出左括号 } else { while (!stack.isEmpty() && precedence >= precedence) { postfix += stack.pop(); } stack.push(char); } } while (!stack.isEmpty()) { postfix += stack.pop(); } return postfix;}
[*]后缀表达式求值
一旦将中缀表达式转换为后缀表达式，就可以很容易地对后缀表达式进行求值。
算法步骤如下：
[*]从左到右遍历后缀表达式。
[*]如果遇到操作数，将其压入栈。
[*]如果遇到运算符，弹出栈中的两个操作数，进行相应的运算，然后将结果压回栈。
[*]遍历结束后，栈中唯一的元素就是表达式的结果。
以下是用 JavaScript 实现后缀表达式求值的代码：
function evaluatePostfix(postfix) { const stack = new Stack(); for (let char of postfix) { if (//.test(char)) { stack.push(parseInt(char)); } else { const operand2 = stack.pop(); const operand1 = stack.pop(); switch (char) { case '+': stack.push(operand1 + operand2); break; case '-': stack.push(operand1 - operand2); break; case '*': stack.push(operand1 * operand2); break; case '/': stack.push(operand1 / operand2); break; } } } return stack.pop();}（二）函数调用栈
在 JavaScript 中，当一个函数调用另一个函数时，会在内存中创建一个称为调用栈（Call Stack）的结构。调用栈是一种栈数据结构，它用于跟踪函数的调用顺序。
例如：
function functionA() { console.log("Inside functionA"); functionB();}function functionB() { console.log("Inside functionB");}functionA();当functionA被调用时，它的执行上下文被压入调用栈。当functionA调用functionB时，functionB的执行上下文也被压入调用栈。当functionB执行完毕后，它的执行上下文从调用栈中弹出。然后，functionA继续执行，直到它也执行完毕，其执行上下文也从调用栈中弹出。
这种机制确保了函数的正确执行顺序和变量的作用域管理。
（三）深度优先搜索（DFS）
深度优先搜索是一种图遍历算法，它可以使用栈来实现。
以下是用 JavaScript 实现深度优先搜索的代码：
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList) { this.adjacencyList = []; } } addEdge(vertex1, vertex2) { this.adjacencyList.push(vertex2); this.adjacencyList.push(vertex1); } dfs(startVertex) { const stack = new Stack(); const visited = {}; stack.push(startVertex); visited = true; while (!stack.isEmpty()) { const currentVertex = stack.pop(); console.log(currentVertex); for (let neighbor of this.adjacencyList) { if (!visited) { stack.push(neighbor); visited = true; } } } }}可以使用以下方式调用：
const graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('B', 'D');graph.addEdge('C', 'E');graph.dfs('A');在这个例子中，深度优先搜索从给定的起始顶点开始，使用栈来存储待访问的顶点。每次从栈中弹出一个顶点，访问它，并将其未访问过的邻居顶点压入栈。
（四）括号匹配
检查一个字符串中的括号是否匹配是栈的另一个常见应用。
算法步骤如下：
[*]初始化一个空栈。
[*]遍历字符串中的每个字符。
[*]如果遇到左括号，将其压入栈。
[*]如果遇到右括号，检查栈是否为空。如果为空，说明右括号没有匹配的左括号，返回 false。如果栈不为空，弹出栈顶元素，检查弹出的左括号是否与当前右括号匹配。如果不匹配，返回 false。
[*]遍历结束后，如果栈为空，说明所有括号都匹配，返回 true；否则，返回 false。
以下是用 JavaScript 实现括号匹配的代码：
function isBalanced(str) { const stack = new Stack(); for (let char of str) { if (char === '(' || char === '[' || char === '{') { stack.push(char); } else if (char === ')' || char === ']' || char === '}') { if (stack.isEmpty()) { return false; } const top = stack.pop(); if ((char === ')' && top!== '(') || (char === ']' && top!== '[') || (char === '}' && top!== '{')) { return false; } } } return stack.isEmpty();}四、总结
栈是一种强大的数据结构，在 JavaScript 中有许多实际应用。从表达式求值到函数调用栈，从图的遍历到括号匹配，栈都发挥了重要作用。理解栈的概念和操作，以及如何在 JavaScript 中实现和应用栈，对于编写高效的代码和解决各种编程问题非常有帮助。
页:
[1]