欧美成人精品手机在线观看_69视频国产_动漫精品第一页_日韩中文字幕网 - 日本欧美一区二区

在 JavaScript 中，棧（Stack）是一種非常有用的數據結構，它遵循后進先出（Last In First Out，LIFO）的原則。在本文中，我們將深入探討棧的概念以及在 JavaScript 中的實際運用。

一、棧的概念

棧是一種線性數據結構，它只能在一端進行插入（稱為入棧或壓棧，push）和刪除（稱為出棧或彈棧，pop）操作。想象一下一摞盤子，你只能從最上面拿盤子（出棧）或者把盤子放在最上面（入棧）。

棧通常具有以下幾個基本操作：

1. push(element)：將一個元素壓入棧頂。

2. pop()：彈出棧頂元素并返回它。

3. peek()：查看棧頂元素，但不彈出它。

4. 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[this.items.length - 1];
    }
    isEmpty() {
        return this.items.length === 0;
    }
    size() {
        return this.items.length;
    }
}

三、棧的實際運用

（一）表達式求值

1. 中綴表達式轉后綴表達式
   在計算機科學中，將中綴表達式轉換為后綴表達式是棧的一個重要應用。中綴表達式是我們通常使用的算術表達式形式，如(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 (/[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;
}

2. 后綴表達式求值
   一旦將中綴表達式轉換為后綴表達式，就可以很容易地對后綴表達式進行求值。

算法步驟如下：

• 從左到右遍歷后綴表達式。

• 如果遇到操作數，將其壓入棧。

• 如果遇到運算符，彈出棧中的兩個操作數，進行相應的運算，然后將結果壓回棧。

• 遍歷結束后，棧中唯一的元素就是表達式的結果。

以下是用 JavaScript 實現后綴表達式求值的代碼：

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

（二）函數調用棧

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

可以使用以下方式調用：

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 中實現和應用棧，對于編寫高效的代碼和解決各種編程問題非常有幫助。

轉自https://www.cnblogs.com/yurui321/p/18552590