快捷導(dǎo)航

JavaScript?中棧的運(yùn)用操作步驟

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

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

JavaScript 中棧的運(yùn)用

在 JavaScript 中，棧（Stack）是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它遵循后進(jìn)先出（Last In First Out，LIFO）的原則。在本文中，我們將深入探討棧的概念以及在 JavaScript 中的實(shí)際運(yùn)用。

一、棧的概念

棧是一種線性數(shù)據(jù)結(jié)構(gòu)，它只能在一端進(jìn)行插入（稱為入?；驂簵＃琾ush）和刪除（稱為出?；驈棗?，pop）操作。想象一下一摞盤子，你只能從最上面拿盤子（出棧）或者把盤子放在最上面（入棧）。

棧通常具有以下幾個(gè)基本操作：

push(element)：將一個(gè)元素壓入棧頂。
pop()：彈出棧頂元素并返回它。
peek()：查看棧頂元素，但不彈出它。
isEmpty()：判斷棧是否為空。

二、在 JavaScript 中實(shí)現(xiàn)棧

以下是用 JavaScript 實(shí)現(xiàn)一個(gè)簡單棧的代碼：

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;
    }
}

三、棧的實(shí)際運(yùn)用

（一）表達(dá)式求值

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式在計(jì)算機(jī)科學(xué)中，將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式是棧的一個(gè)重要應(yīng)用。中綴表達(dá)式是我們通常使用的算術(shù)表達(dá)式形式，如(2 + 3) * 4。后綴表達(dá)式則是將運(yùn)算符放在操作數(shù)之后，例如2 3 + 4 *。

算法步驟如下：

初始化一個(gè)空棧用于存儲(chǔ)運(yùn)算符。
從左到右遍歷中綴表達(dá)式。
如果遇到操作數(shù)，直接輸出。
如果遇到左括號(hào)，將其壓入棧。
如果遇到右括號(hào)，彈出棧中的運(yùn)算符并輸出，直到遇到左括號(hào)，然后丟棄左括號(hào)。
如果遇到運(yùn)算符，根據(jù)其優(yōu)先級(jí)進(jìn)行處理。如果棧頂運(yùn)算符的優(yōu)先級(jí)高于或等于當(dāng)前運(yùn)算符，則彈出棧頂運(yùn)算符并輸出；否則，將當(dāng)前運(yùn)算符壓入棧。
遍歷結(jié)束后，將棧中的剩余運(yùn)算符依次彈出并輸出。

以下是用 JavaScript 實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的代碼：

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(); // 彈出左括號(hào)
        } else {
            while (!stack.isEmpty() && precedence[stack.peek()] >= precedence[char]) {
                postfix += stack.pop();
            }
            stack.push(char);
        }
    }
    while (!stack.isEmpty()) {
        postfix += stack.pop();
    }
    return postfix;
}

后綴表達(dá)式求值一旦將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，就可以很容易地對(duì)后綴表達(dá)式進(jìn)行求值。

算法步驟如下：

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

以下是用 JavaScript 實(shí)現(xiàn)后綴表達(dá)式求值的代碼：

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)一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)時(shí)，會(huì)在內(nèi)存中創(chuàng)建一個(gè)稱為調(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)用時(shí)，它的執(zhí)行上下文被壓入調(diào)用棧。當(dāng)functionA調(diào)用functionB時(shí)，functionB的執(zhí)行上下文也被壓入調(diào)用棧。當(dāng)functionB執(zhí)行完畢后，它的執(zhí)行上下文從調(diào)用棧中彈出。然后，functionA繼續(xù)執(zhí)行，直到它也執(zhí)行完畢，其執(zhí)行上下文也從調(diào)用棧中彈出。

這種機(jī)制確保了函數(shù)的正確執(zhí)行順序和變量的作用域管理。

（三）深度優(yōu)先搜索（DFS）

深度優(yōu)先搜索是一種圖遍歷算法，它可以使用棧來實(shí)現(xiàn)。

以下是用 JavaScript 實(shí)現(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');

在這個(gè)例子中，深度優(yōu)先搜索從給定的起始頂點(diǎn)開始，使用棧來存儲(chǔ)待訪問的頂點(diǎn)。每次從棧中彈出一個(gè)頂點(diǎn)，訪問它，并將其未訪問過的鄰居頂點(diǎn)壓入棧。

（四）括號(hào)匹配

檢查一個(gè)字符串中的括號(hào)是否匹配是棧的另一個(gè)常見應(yīng)用。

算法步驟如下：

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

以下是用 JavaScript 實(shí)現(xiàn)括號(hào)匹配的代碼：

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é)

棧是一種強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，在 JavaScript 中有許多實(shí)際應(yīng)用。從表達(dá)式求值到函數(shù)調(diào)用棧，從圖的遍歷到括號(hào)匹配，棧都發(fā)揮了重要作用。理解棧的概念和操作，以及如何在 JavaScript 中實(shí)現(xiàn)和應(yīng)用棧，對(duì)于編寫高效的代碼和解決各種編程問題非常有幫助。

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

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

您可能感興趣的文章: