前言

前面兩篇文章介紹了數(shù)據(jù)結(jié)構(gòu)和算法的一些前置內(nèi)容，這篇文章開始正式學習常見的數(shù)據(jù)結(jié)構(gòu)，首先學習的就是棧（Stack）。

什么是棧？

棧全稱為堆棧，是一種先進后出的的數(shù)據(jù)結(jié)構(gòu)，棧中只有兩種基本操作，也就是插入和刪除，也就是入棧和出棧操作，棧只有一端可以進行入棧和出棧操作，我們將其稱為棧頂，另一端稱其為棧底；如下圖展示了棧這個數(shù)據(jù)結(jié)構(gòu)：

JavaScript中的棧

JavaScript并沒有棧這個數(shù)據(jù)類型，但是可以通過數(shù)組進行模擬，而且數(shù)組中提供的push()和pop()選項，正好實現(xiàn)先入后出的的操作，

示例代碼如下：

const stack = []

// 入棧
stack.push(1)
stack.push(2)
// 出棧
const v1 = stack.pop() // 2
const v2 = stack.pop() // 1

棧的應(yīng)用場景

棧是算法和程序中最常用的輔助結(jié)構(gòu)，其的應(yīng)用十分廣泛，凡是需要先進后出場景都有棧的身影，比如：

• 函數(shù)調(diào)用堆棧
• 判斷字符串括號是否有效

接下來我們依次來看：

函數(shù)調(diào)用堆棧

JavaScript中的函數(shù)調(diào)用堆棧就是一個應(yīng)用棧的一個典型例子，比如下面這段代碼：

function f1() {}
function f2() {
  f1()
}
function f3() {
  f2()
}
f3()

如下圖：

執(zhí)行過程如下：

• 調(diào)用函數(shù)f3()，將f3壓入堆棧；
• 在f3()中調(diào)用了f2()，將f2壓入堆棧；
• 在f2()中又調(diào)用了f1()，將f1壓入堆棧；
• 只有f1()運行完成才能繼續(xù)往下執(zhí)行，所以f1()先出棧，以此類推。

有效的括號

有效的括號是力扣中的一個關(guān)于棧的算法題目，題目大意就是判斷給定字符串中的括號是否匹配，匹配返回true，否則返回false。

解題思路如下：

• 判斷字符串的長度是否為偶數(shù)，不為偶數(shù)直接返回false，因為括號都是成對出現(xiàn)的；
• 新建一個棧；
• 遍歷字符串，遍歷到每一項時如果時左括號，將其壓入棧；如果是右括號，與棧頂對比，如果相匹配則出棧，不匹配則返回false。

實現(xiàn)代碼如下：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    const stack = []
    for(let i = 0; i<s.length; i++) {
        const c = s[i] // 記錄當前項
        if (c === '(' || c === '[' || c==='{') {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1] // 獲取棧頂元素
            if (
                (t === '(' && c === ')') ||
                (t === '[' && c === ']') ||
                (t === '{' && c === '}')
            ) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    // 如果為0表示全部匹配，有剩余則表示不匹配
    return stack.length === 0
};

肯有還有更優(yōu)的寫法，這里直接使用的暴力解法。

總結(jié)

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