DIV CSS 佈局教程網

JavaScript 資料結構入門:用陣列實作堆疊 Stack
編輯:關於JavaScript     

資料結構系列就從堆疊(Stack)開始。

堆疊是一種遵循後進先出原則(LIFO,Last In First Out)的有序集合,堆疊頂永遠是最新加入的元素。

最貼切的比喻是一疊放在箱子裡的書:要拿最底下那本,得先把上面的書一本本移開。你不能跳過上面的直接拿底下那本。

建立建構函式

用陣列來模擬堆疊是最省事的做法,因為陣列本身就有 push 與 pop:

 /**
 * 堆疊的建構函式
 */
function Stack() {
    // 用陣列來模擬堆疊
    var items = [];
}

注意 items 宣告在閉包內部而非 this 上,這樣外部就無法直接存取,達到封裝的效果。

需要哪些方法

  • push(element):添加一個元素到堆疊頂
  • pop():移除並回傳堆疊頂元素
  • peek():回傳堆疊頂元素(不移除)
  • isEmpty():檢查堆疊是否為空
  • clear():移除堆疊中所有元素
  • size():回傳堆疊中元素個數
  • print():以字串形式顯示堆疊內容

push:入堆疊

新元素放在陣列的最後一位,直接用陣列的 push 即可:

 /**
 * 將元素送入堆疊,置於陣列的最後一位
 * @param {Any} element 可接受任意型別
 */
this.push = function(element) {
    items.push(element);
};

pop:出堆疊

把堆疊頂元素彈出並回傳其值,同樣直接借用陣列的 pop:

 /**
 * 彈出堆疊頂元素
 * @return {Any} 回傳被彈出的值
 */
this.pop = function() {
    return items.pop();
};

peek:查看堆疊頂

只讀不取,用陣列長度定位最後一個元素:

 /**
 * 查看堆疊頂元素
 * @return {Any} 回傳堆疊頂元素
 */
this.peek = function() {
    return items[items.length - 1];
}

其餘方法

前三者是堆疊的核心,其餘一次列出。因為接下來要談的佇列(Queue)會與這部分有大量重疊:

 /**
 * 確認堆疊是否為空
 * @return {Boolean} 為空回傳 true,否則 false
 */
this.isEmpty = function() {
    return items.length === 0;
};

/** 清空堆疊中所有內容 */
this.clear = function() {
    items = [];
};

/**
 * 回傳堆疊的長度
 * @return {Number}
 */
this.size = function() {
    return items.length;
};

/** 以字串顯示堆疊中所有內容 */
this.print = function() {
    console.log(items.toString());
};

實際應用:十進位轉二進位

書中有個經典範例:把十進位數字轉成二進位。原理是反覆除以 2 並取餘數,得到的餘數序列剛好是「由低位到高位」,因此用堆疊反轉一次就能得到正確結果——這正是堆疊最典型的用途。

 /**
 * 將 10 進位數字轉為 2 進位數字
 * @param {Number} decNumber 要轉換的 10 進位數字
 * @return {String} 轉換後的 2 進位字串
 */
function divideBy2(decNumber) {
    var remStack = new Stack(),
        rem,
        binaryString = '';

    while (decNumber > 0) {
        rem = Math.floor(decNumber % 2);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / 2);
    }

    while (!remStack.isEmpty()) {
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

補充:這個實作的兩個細節

一、ES6 可以用 class 寫得更清楚。上面的寫法刻意用 var items 藏在閉包裡來模擬私有成員,這是 ES6 之前的通用手法。今天可以改用 class 搭配 # 私有欄位:

 class Stack {
    #items = [];

    push(element) { this.#items.push(element); }
    pop()         { return this.#items.pop(); }
    peek()        { return this.#items[this.#items.length - 1]; }
    get isEmpty() { return this.#items.length === 0; }
    get size()    { return this.#items.length; }
    clear()       { this.#items = []; }
}

二、clear() 有一個隱藏問題。items = [] 會讓 items 指向一個新陣列,若外部曾經透過閉包持有舊陣列的參照,兩者就會分離。改用 items.length = 0 則會原地清空,語意更準確,也避免了這個潛在的混淆。

三、邊界情況值得處理。空堆疊呼叫 pop() 會回傳 undefined,peek() 同理。若呼叫方未做檢查,錯誤會延後到很遠的地方才爆發。實務上可以選擇拋出錯誤,或明確回傳 undefined 並在文件註明。

堆疊在實際開發中應用很廣:函式呼叫的呼叫堆疊、瀏覽器的後退紀錄、運算式的括號配對檢查、縮排(undo)機制、深度優先搜尋,都是堆疊的場景。掌握它的核心只有三個操作——push、pop、peek,而其餘一切都建立在「後進先出」這個簡單約束上。

到此堆疊的學習告一段落,希望對你的 JavaScript 資料結構學習有所幫助。

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