快捷導(dǎo)航

一文讓你快速了解JavaScript棧

更新時(shí)間：2022年07月13日 14:22:57 作者：??一碗周?

這篇文章主要介紹了一文讓你快速了解JavaScript棧，棧全稱為堆棧，是一種先進(jìn)后出的的數(shù)據(jù)結(jié)構(gòu)，棧中只有兩種基本操作，也就是插入和刪除，也就是入棧和出棧操作，棧只有一端可以進(jìn)行入棧和出棧操作，我們將其稱為棧頂，另一端稱其為棧底

前言

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

什么是棧？

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

JavaScript中的棧

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

示例代碼如下：

const stack = []

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

棧的應(yīng)用場(chǎng)景

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

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

接下來我們依次來看：

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

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

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()運(yùn)行完成才能繼續(xù)往下執(zhí)行，所以f1()先出棧，以此類推。

有效的括號(hào)

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

解題思路如下：

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

實(shí)現(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] // 記錄當(dāng)前項(xiàng)
        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
};