在 JavaScript 中，棧（Stack）是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它遵循后進先出（Last In First Out，LIFO）的原則。在本文中，我們將深入探討棧的概念以及在 JavaScript 中的實際運用。
一、棧的概念
棧是一種線性數(shù)據(jù)結(jié)構(gòu)，它只能在一端進行插入（稱為入?；驂簵?，push）和刪除（稱為出棧或彈棧，pop）操作。想象一下一摞盤子，你只能從最上面拿盤子（出棧）或者把盤子放在最上面（入棧）。
棧通常具有以下幾個基本操作：
push(element)：將一個元素壓入棧頂。
pop()：彈出棧頂元素并返回它。
peek()：查看棧頂元素，但不彈出它。
isEmpty()：判斷棧是否為空。
二、在 JavaScript 中實現(xiàn)棧
以下是用 JavaScript 實現(xiàn)一個簡單棧的代碼：
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[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
三、棧的實際運用
（一）表達式求值
中綴表達式轉(zhuǎn)后綴表達式
在計算機科學(xué)中，將中綴表達式轉(zhuǎn)換為后綴表達式是棧的一個重要應(yīng)用。中綴表達式是我們通常使用的算術(shù)表達式形式，如(2 + 3) * 4。后綴表達式則是將運算符放在操作數(shù)之后，例如2 3 + 4 *。
算法步驟如下：
初始化一個空棧用于存儲運算符。
從左到右遍歷中綴表達式。
如果遇到操作數(shù)，直接輸出。
如果遇到左括號，將其壓入棧。
如果遇到右括號，彈出棧中的運算符并輸出，直到遇到左括號，然后丟棄左括號。
如果遇到運算符，根據(jù)其優(yōu)先級進行處理。如果棧頂運算符的優(yōu)先級高于或等于當(dāng)前運算符，則彈出棧頂運算符并輸出；否則，將當(dāng)前運算符壓入棧。
遍歷結(jié)束后，將棧中的剩余運算符依次彈出并輸出。
以下是用 JavaScript 實現(xiàn)中綴表達式轉(zhuǎn)后綴表達式的代碼：
function infixToPostfix(expression) {
const stack = new Stack();
let postfix = "";
const precedence = {
'+': 1,
'-': 1,
'*': 2,
'/': 2
};
for (let char of expression) {
if (/[0-9]/.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[stack.peek()] >= precedence[char]) {
postfix += stack.pop();
}
stack.push(char);
}
}
while (!stack.isEmpty()) {
postfix += stack.pop();
}
return postfix;
}
后綴表達式求值
一旦將中綴表達式轉(zhuǎn)換為后綴表達式，就可以很容易地對后綴表達式進行求值。
算法步驟如下：
以下是用 JavaScript 實現(xiàn)后綴表達式求值的代碼：
function evaluatePostfix(postfix) {
const stack = new Stack();
for (let char of postfix) {
if (/[0-9]/.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();
}
（二）函數(shù)調(diào)用棧
在 JavaScript 中，當(dāng)一個函數(shù)調(diào)用另一個函數(shù)時，會在內(nèi)存中創(chuàng)建一個稱為調(diào)用棧（Call Stack）的結(jié)構(gòu)。調(diào)用棧是一種棧數(shù)據(jù)結(jié)構(gòu)，它用于跟蹤函數(shù)的調(diào)用順序。
例如：
function functionA() {
console.log("Inside functionA");
functionB();
}function functionB() {
console.log("Inside functionB");
}functionA();
當(dāng)functionA被調(diào)用時，它的執(zhí)行上下文被壓入調(diào)用棧。當(dāng)functionA調(diào)用functionB時，functionB的執(zhí)行上下文也被壓入調(diào)用棧。當(dāng)functionB執(zhí)行完畢后，它的執(zhí)行上下文從調(diào)用棧中彈出。然后，functionA繼續(xù)執(zhí)行，直到它也執(zhí)行完畢，其執(zhí)行上下文也從調(diào)用棧中彈出。
這種機制確保了函數(shù)的正確執(zhí)行順序和變量的作用域管理。
（三）深度優(yōu)先搜索（DFS）
深度優(yōu)先搜索是一種圖遍歷算法，它可以使用棧來實現(xiàn)。
以下是用 JavaScript 實現(xiàn)深度優(yōu)先搜索的代碼：
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
dfs(startVertex) {
const stack = new Stack();
const visited = {};
stack.push(startVertex);
visited[startVertex] = true;
while (!stack.isEmpty()) {
const currentVertex = stack.pop();
console.log(currentVertex);
for (let neighbor of this.adjacencyList[currentVertex]) {
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
}
}
可以使用以下方式調(diào)用：
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');
在這個例子中，深度優(yōu)先搜索從給定的起始頂點開始，使用棧來存儲待訪問的頂點。每次從棧中彈出一個頂點，訪問它，并將其未訪問過的鄰居頂點壓入棧。
（四）括號匹配
檢查一個字符串中的括號是否匹配是棧的另一個常見應(yīng)用。
算法步驟如下：
以下是用 JavaScript 實現(xiàn)括號匹配的代碼：
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();
}
四、總結(jié)
棧是一種強大的數(shù)據(jù)結(jié)構(gòu)，在 JavaScript 中有許多實際應(yīng)用。從表達式求值到函數(shù)調(diào)用棧，從圖的遍歷到括號匹配，棧都發(fā)揮了重要作用。理解棧的概念和操作，以及如何在 JavaScript 中實現(xiàn)和應(yīng)用棧，對于編寫高效的代碼和解決各種編程問題非常有幫助。
轉(zhuǎn)自https://www.cnblogs.com/yurui321/p/18552590
該文章在 2024/11/19 8:39:24 編輯過
400 186 1886
