DIV CSS 佈局教程網

用 JS 陣列實作佇列與堆疊:unshift、push 與 pop 的搭配
編輯:關於JavaScript     

在物件導向語言中,佇列與堆疊通常有現成的集合類別可用;JavaScript 沒有,但由於陣列本身就提供了足夠的方法,只要組合得當就能完成同樣的資料結構。

先釐清兩者的性質

性質決定了使用場合,這是理解一切的前提。

佇列(Queue):先進先出(FIFO)。先被放進去的資料,會先被取出來。

堆疊(Stack):後進先出(LIFO)。最後被放進去的資料,會先被取出來。

實作程式碼

// 先進先出:從前端加入,從後端取出
var a = new Array();
a.unshift(1);
a.unshift(2);
a.unshift(3);
a.unshift(4);
console.log("先進先出");
a.pop();

// 後進先出:從後端加入,從後端取出
var a = new Array();
a.push(1);
a.push(2);
a.push(3);
a.push(4);
console.log("後進先出");
a.pop();

關鍵在於「進」與「出」是否同一端

把上面兩段程式碼放在一起對照,就能看出重點:pop 都是從尾端取資料,唯一不同的是加入的方式。用 unshift 從頭端放,尾端取,先放的自然在尾端,於是形成先進先出;用 push 從尾端放,尾端取,最後放的最先被拿走,於是形成後進先出。

換句話說,堆疊就是「同一端進出」,佇列就是「兩端各走一邊」。理解這個對稱關係,就不必死記哪個方法對應哪個結構。

運行結果

常見應用場景

堆疊的典型用途包括:函式呼叫的返回位址管理、運算式的括號配對檢查、瀏覽器的前後頁紀錄、以及 Undo 功能。佇列則常見於:任務排程、訊息佇列、廣播或事件的分批處理,以及樹狀或圖形結構的廣度優先搜尋。

效能上的提醒

值得注意的是,unshift 與 shift 需要搬移整個陣列的元素,其成本是 O(n)。若實作的是資料量龐大的佇列,考慮改用「頭指標」搭配 push/pop 的方式,或是直接宣告一個指標記錄讀取位置,避免每次都搬動陣列。

小結

用陣列模擬佇列與堆疊只需幾行程式碼,卻是理解資料結構的一條捷徑。把進出端的方向想清楚,並留意 unshift 的效能代價,實務上就能用得游刃有餘。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved