JavaScript?中棧的運用操作步驟

更新時間：2024年11月19日 08:53:03 作者：擾晨

棧是一種強大的數(shù)據(jù)結(jié)構(gòu),在?JavaScript?中有許多實際應用,從表達式求值到函數(shù)調(diào)用棧,從圖的遍歷到括號匹配,棧都發(fā)揮了重要作用,這篇文章主要介紹了JavaScript中棧的運用,需要的朋友可以參考下

JavaScript 中棧的運用

在 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)后綴表達式在計算機科學中，將中綴表達式轉(zhuǎn)換為后綴表達式是棧的一個重要應用。中綴表達式是我們通常使用的算術(shù)表達式形式，如(2 + 3) * 4。后綴表達式則是將運算符放在操作數(shù)之后，例如2 3 + 4 *。

算法步驟如下：

初始化一個空棧用于存儲運算符。
從左到右遍歷中綴表達式。
如果遇到操作數(shù)，直接輸出。
如果遇到左括號，將其壓入棧。
如果遇到右括號，彈出棧中的運算符并輸出，直到遇到左括號，然后丟棄左括號。
如果遇到運算符，根據(jù)其優(yōu)先級進行處理。如果棧頂運算符的優(yōu)先級高于或等于當前運算符，則彈出棧頂運算符并輸出；否則，將當前運算符壓入棧。
遍歷結(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)換為后綴表達式，就可以很容易地對后綴表達式進行求值。

算法步驟如下：

從左到右遍歷后綴表達式。
如果遇到操作數(shù)，將其壓入棧。
如果遇到運算符，彈出棧中的兩個操作數(shù)，進行相應的運算，然后將結(jié)果壓回棧。
遍歷結(jié)束后，棧中唯一的元素就是表達式的結(jié)果。

以下是用 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 中，當一個函數(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();

當functionA被調(diào)用時，它的執(zhí)行上下文被壓入調(diào)用棧。當functionA調(diào)用functionB時，functionB的執(zhí)行上下文也被壓入調(diào)用棧。當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)先搜索從給定的起始頂點開始，使用棧來存儲待訪問的頂點。每次從棧中彈出一個頂點，訪問它，并將其未訪問過的鄰居頂點壓入棧。

（四）括號匹配

檢查一個字符串中的括號是否匹配是棧的另一個常見應用。

算法步驟如下：

初始化一個空棧。
遍歷字符串中的每個字符。
如果遇到左括號，將其壓入棧。
如果遇到右括號，檢查棧是否為空。如果為空，說明右括號沒有匹配的左括號，返回 false。如果棧不為空，彈出棧頂元素，檢查彈出的左括號是否與當前右括號匹配。如果不匹配，返回 false。
遍歷結(jié)束后，如果棧為空，說明所有括號都匹配，返回 true；否則，返回 false。

以下是用 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 中有許多實際應用。從表達式求值到函數(shù)調(diào)用棧，從圖的遍歷到括號匹配，棧都發(fā)揮了重要作用。理解棧的概念和操作，以及如何在 JavaScript 中實現(xiàn)和應用棧，對于編寫高效的代碼和解決各種編程問題非常有幫助。

到此這篇關(guān)于JavaScript 中棧的運用的文章就介紹到這了,更多相關(guān)js棧的運用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

到此這篇關(guān)于JavaScript 中棧的運用操作步驟的文章就介紹到這了,更多相關(guān)js棧的運用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: