Javascript棧是一種常見的數(shù)據(jù)結(jié)構(gòu),它就像是一個(gè)大量盤子堆積成的塔一樣。與塔不同,Javascript棧可以添加和刪除盤子,而且每次添加或刪除都會(huì)在最上面進(jìn)行,在棧中我們使用push()表示添加數(shù)據(jù),使用pop()表示刪除數(shù)據(jù)。
一個(gè)實(shí)例,以下是一個(gè)基本的棧程序,包括了push()和pop()方法。
var stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack);
stack.pop();
console.log(stack);
上面的代碼示例中,定義了一個(gè)棧并使用push()方法向其中添加了三個(gè)數(shù)字。接著再執(zhí)行pop()方法刪除棧頂?shù)囊粋€(gè)數(shù)字,將棧中的元素?cái)?shù)量減1。
棧最常見的用途是解決嵌套的問題,比如很多函數(shù)內(nèi)都有if條件、嵌套for循環(huán)和遞歸等等。Javascript棧的致命優(yōu)點(diǎn)就是它遵循后進(jìn)先出(LIFO)原則,這意味著最后添加到棧中的元素,也就是最近添加的元素,會(huì)被先移除。
以下是一個(gè)嵌套的示例,我們可以看到它使用了遞歸和棧處理:
function recursive(item) {
if (item === 3) {
return console.log(item);
}
console.log(item);
item++;
recursive(item);
console.log(item);
}
recursive(1);
如上述代碼所示,輸入1后,每次遞歸將item加1,而在其中兩次通過console.log(item)輸出。當(dāng)item為3時(shí)程序結(jié)束。遞歸函數(shù)方法的執(zhí)行到底過程如下圖所示:
在執(zhí)行遞歸函數(shù)時(shí),壓入一個(gè)item的值和返回地址,當(dāng)遞歸執(zhí)行結(jié)束后,彈出棧上的item和返回地址。由于LIFO這個(gè)后進(jìn)先出原則,因此遞歸棧的輸出反向。
在Javascript中,棧有一個(gè)重要的用處是實(shí)現(xiàn)函數(shù)的調(diào)用堆棧。每當(dāng)一個(gè)函數(shù)被調(diào)用時(shí),當(dāng)前函數(shù)的上下文被推入到一個(gè)棧中,并在返回前彈出,以便執(zhí)行調(diào)用函數(shù)。
下面的代碼展示了如何使用棧來生成 Fibonacci數(shù)列:
function fibonacci(n) {
var stack = [];
if (n<= 0) {
return [];
}
if (n === 1) {
return [1];
}
if (n === 2) {
return [1, 1];
}
stack.push(1, 1);
while (stack.length< n) {
var prev = stack[stack.length - 2];
var next = stack[stack.length - 1];
stack.push(prev + next);
}
return stack;
}
console.log(fibonacci(10));
以上的代碼中使用了while循環(huán)向棧中添加Fibonacci數(shù)列的元素,同時(shí)遵循LIFO的原則從棧中刪除元素。這種算法更在大型數(shù)據(jù)集上保持良好的性能并避免棧推入太多的上下文。
事實(shí)上,Javascript棧有各種各樣的用途,從數(shù)據(jù)結(jié)構(gòu)到中小型項(xiàng)目的實(shí)現(xiàn)都非常適用。作為一名Javascript開發(fā)人員,我們需要掌握它的基本原理和實(shí)際應(yīng)用場(chǎng)景,才能在工作中真正發(fā)揮自己的優(yōu)勢(shì)。