JavaScript TDD Deque 雙向佇列

tags: JavaScript Testing

category: 資料結構與演算法

description: JavaScript Deque 雙向佇列

created_at: 2024/11/28 16:00:00

released_at: 2024/11/29

前言

這一篇文章將會介紹如何在 JavaScript 中實作雙向佇列（Deque），其實也是順便測試部落格的新功能(預定發布)，所以如果有看到這篇文章的內容，基本上就是成功了

至於為什麼選擇這個主題?

因為今天 Leetcode Daily 題目可以使用雙向佇列來優化，所以就順便來寫一篇文章來記錄一下 Deque (因為 Leetcode 上的 JavaScript 似乎沒有 Deque 的實作)。

而 TDD 只是寫到一半心血來潮加上去的，所以後面的實作會扯上 TDD 的部分。

預備知識

在開始之前，你可能需要先知道以下的知識：

• 基礎資料結構(例如: Array, Map, Stack, Queue)
• 基礎演算法(例如時間複雜度)
• 基礎 JavaScript 語法
• 測試(Testing)的基本觀念 (雖然也可以跳過，寫完之後發現好像不好跳過)
• 裝好 Node.js 環境

就算沒有也沒關係，這篇的內容應該不會太難。

什麼是雙向佇列（Deque）?

老樣子因為如果純粹定義的話已經有很多資源，所以我就簡單的說明一下。

在講雙向佇列之前，我們先來看看 Stack 與 Queue 的特性：

• Stack 是一種後進先出（LIFO）的資料結構
• Queue 是一種先進先出（FIFO）的資料結構

嗯... Copilot 生成的果然很文謅謅，所以舉個範例來看:

• Stack: 像是你生活中疊盤子，最後疊的盤子會在最上面，所以第一個拿的也是最後一個疊的盤子(不考慮你是不是從中間拿的)
• Queue: 像是你生活中排隊買東西，先來的人先買，後來的人後買

這兩個範例應該就能夠理解，然後以 Array 來舉例的話也不難

• Stack:
  • const stack = [1, 2, 3]
  • stack.push(4) 後 stack 變成 [1, 2, 3, 4]
  • stack.pop() 後 stack 變成 [1, 2, 3]
• Queue:
  • const queue = [1, 2, 3]
  • queue.push(4) 後 queue 變成 [1, 2, 3, 4]
  • queue.shift() 後 queue 變成 [2, 3, 4]

而 Deque 則是一種同時具有 Stack 與 Queue 的特性，也就是可以在兩端進行操作，所以可以想像成是一個可以從兩端進出的一種資料結構。

這時就可以正名一下，Deque 的全名是 Double-Ended Queue，也就是雙向佇列，這樣才不用死記 Deque 是什麼意思，至於念法是 Deck。

雙向佇列的操作

在了解了 Deque 是什麼之後，接下來就是要了解 Deque 的操作了，通常會有以下:

• pushFront: 在佇列的前端新增一個元素
• pushBack: 在佇列的後端新增一個元素
• popFront: 移除佇列的前端元素
• popBack: 移除佇列的後端元素
• peekFront: 查看佇列的前端元素
• peekBack: 查看佇列的後端元素
• size: 查看佇列的大小
• isEmpty: 查看佇列是否為空

有沒有覺得很熟悉，因為這些操作基本上就是 Stack 與 Queue 的操作，只是多了一個方向而已。

除非你用現成的 library，不然你自己實作，其實也可以根據需求做你要的功能就好，例如我在今天 Daily 就只實作了 pushFront, pushBack, popFront 這三個操作以及 size 一個屬性。

除非未來打算要重複利用他，或是今天是考題，必須實作完整，不然你可能不需要他(YAGNI)(?)。

實作雙向佇列之前

在開始實作之前，我們可以先來看看例子，這樣比較容易理解。

舉個例子，假設我們有一個空的 Deque，然後我們依序執行以下操作:

1. pushBack(1)
   • Deque: [1]
2. pushBack(2)
   • Deque: [1, 2]
3. pushFront(3)
   • Deque: [3, 1, 2]
4. pushFront(4)
   • Deque: [4, 3, 1, 2]
5. popFront()
   • 輸出: 4，Deque: [3, 1, 2]
6. popBack()
   • 輸出: 2，Deque: [3, 1]

這樣應該就能夠理解 Deque 的操作了，不過我們再看一個邊界情況再來開始實作:

假設今天 Deque 是 [1]，那麼你不管是 popFront 還是 popBack 都會輸出 1，然後 Deque 就會變成 []。

所以其實 Deque 也是一個環狀的資料結構，只是你可以從兩端進出而已。

實作雙向佇列

這次我們測試先行(Test-Frist)，所以我們先來寫測試，這樣比較容易理解(?)。

然後為了簡化，這邊不打算使用任何測試套件，純粹使用原生的語法來測試，希望可以降低門檻。

所以這邊先建立一些東西:

• 負責做 Assertion 的函數: 負責判斷測試是否通過，如果沒有通過就拋出錯誤
• 存測試的物件: 用來存放測試的函數，之後給迴圈執行
• 迴圈: 負責執行每一個測試

假設檔案名稱為: test.js

function assert(condition, message) {
    if (!condition) {
        throw message || 'Assertion failed';
    }
}

const testSuite = {

}

for (const key in testSuite) {
    testSuite[key]();
}

接著只要把測試寫在 testSuite 裡面就好，例如:

假設實作的檔案名稱為: deque.js

const Deque = require('./deque.js');

const testSuite = {
    'init deque is empty': function() {
        const deque = new Deque();
        assert(deque.isEmpty(), 'deque should be empty');
    },
}

接著執行 node test.js 就可以看到結果了。

只是這時候會發現 deque.js 還不存在，執行測試也會失敗，接著建立他。

建立好之後再執行測試，會發現 Deque 不是 constructor，所以失敗了，所以這時要去 deque.js 當中實作 Deque 並 export 出去。

先寫最基本的 class 定義

module.exports = class {}

這時會發現 isEmpty 不是一個函數，所以這時你要實現他:

module.exports = class {
    isEmpty() {
        return true;
    }
}

這樣就可以通過第一個測試了，接著就可以繼續實作其他的操作。

實作雙向佇列 - pushFront 與 pushBack

我們可以從 pushFront 開始，一樣先寫測試:(接下來外面的 object 我會省略)

    'push front makes deque not empty': function() {
        const deque = new Deque();
        deque.pushFront(1);
        assert(deque.isEmpty() === false, 'deque should not be empty');
    },

這時他會先說 pushFront 不存在，所以我們要去 deque.js 實作他:

module.exports = class {
    pushFront(item) {

    }

    isEmpty() {
        return true;
    }
}

這時測試不會通過，因為你塞了一個元素進去他還是輸出空的，所以這時要用最笨的方式來實作:

module.exports = class {
    #isEmpty
    constructor() {
        this.#isEmpty = true
    }

    pushFront(item) {
        this.#isEmpty = false;
    }

    isEmpty() {
        return this.#isEmpty;
    }
}

這樣就可以通過測試了，接著就可以繼續實作 pushBack:

    'push back makes deque not empty': function() {
        const deque = new Deque();
        deque.pushBack(1);
        assert(deque.isEmpty() === false, 'deque should not be empty');
    },

然後一樣去 deque.js 實作他:(略過其他部分)

    pushBack(item) {
        this.#isEmpty = false;
    }

這時這個測試也通過了，接著我們需要更多測試去滿足 pushFront 與 pushBack 的需求，例如我們可以開始測試 peekFront 與 peekBack。

實作雙向佇列 - peekFront 與 peekBack

一樣測試先行:

    'peek front will return last pushed front element': function() {
        const deque = new Deque();
        deque.pushFront(1);
        assert(deque.peekFront() === 1, 'front element should be 1');
    },

然後去 deque.js 實作他:

    peekFront() {
        return 1;
    }

接著就可以繼續實作 peekBack:

    'peek back will return last pushed back element': function() {
        const deque = new Deque();
        deque.pushBack(1);
        assert(deque.peekBack() === 1, 'back element should be 1');
    },

然後去 deque.js 實作他:

    peekBack() {
        return 1;
    }

我知道很笨..但再忍耐一下...

接著我們可以再測一些 peek 相關的邊界情況，例如 peekFront 與 peekBack 在 Deque 是空的時候應該要回傳 null。

    'peek front will return null when deque is empty': function() {
        const deque = new Deque();
        assert(deque.peekFront() === null, 'front element should be null');
    },

然後去 deque.js 實作他:

    peekFront() {
        return null;
    }

這時你會發現這種笨方法似乎不可行了，這時你必須做出一點改變，得將他的 push 的結果存起來，這樣才能夠回傳正確的值。

然後...你知道的，又是以最笨的方式來實作: (一樣只保留修改的部分)

module.exports = class {
    #isEmpty
    #front
    constructor() {
        this.#isEmpty = true
        this.#front = null
    }

    pushFront(item) {
        this.#isEmpty = false;
        this.#front = item;
    }

    peekFront() {
        return this.#front;
    }
}

這時測試又通過了，然後為了節省之後的篇幅，我先以單向來 Demo，其他之後需要再補上，所以為了後面流程順利，可以先將 back 相關的程式碼移除。

接著來做 popFront:

    'push front and pop front will make deque empty': function() {
        const deque = new Deque();
        deque.pushFront(1);
        deque.popFront();
        assert(deque.isEmpty() === true, 'deque should be empty');
    },

然後又是最笨的實作:

    popFront() {
        this.#isEmpty = true;
    }

這時我們把測試再加強一下，pop 需要能夠取得最後一個 push 進去的元素:

    'push front and pop front will return the last pushed front element': function() {
        const deque = new Deque();
        deque.pushFront(1);
        assert(deque.popFront() === 1, 'front element should be 1');
    },

這時你的實作會再小改一行:

    popFront() {
        this.#isEmpty = true;
        return this.#front;
    }

然後我們來稍微做一個微小的重構，把剛剛那兩個測試合併一下:

    'push front and pop front will make deque empty and return the last pushed front element': function() {
        const deque = new Deque();
        deque.pushFront(1);
        assert(deque.popFront() === 1, 'front element should be 1');
        assert(deque.isEmpty() === true, 'deque should be empty');
    },

這時你的測試還是會通過，接著我們來加強 pushFront ，讓我們不得不做出稍微 聰明的實作。

    'push 2 front elements and pop 2 front elements will sequentially return the last pushed front elements': function() {
        const deque = new Deque();
        deque.pushFront(1);
        deque.pushFront(2);
        assert(deque.popFront() === 2, 'front element should be 2');
        assert(deque.popFront() === 1, 'front element should be 1');
    },

這時終於要有記憶的功能了，這時你可以用 Array 來存放，然後 pop 的時候就可以直接取出最後一個元素。

module.exports = class {
    #isEmpty
    #items
    constructor() {
        this.#isEmpty = true
        this.#front = []
    }

    pushFront(item) {
        this.#isEmpty = false;
        this.#items.unshift(item);
    }

    popFront() {
        this.#isEmpty = true;
        return this.#items.shift();
    }

    peekFront() {
        return this.#items[0];
    }
}

這時你會發現，新的測試過了，但舊的 peek front will return null when deque is empty - front element should be null 壞了，這時你就要再做一點小修改，好讓測試通過。

先用最笨的方式改他:

    peekFront() {
        if (this.isEmpty()) {
            return null;
        }
        return this.#items[0];
    }

這時我們也補上 popFront 如果 Deque 是空的時候，應該要回傳 null:

    'pop front will return null when deque is empty': function() {
        const deque = new Deque();
        assert(deque.popFront() === null, 'front element should be null');
    },

以及對應的實現:

    popFront() {
        if (this.isEmpty()) {
            return null;
        }
        return this.#items.shift();
    }

然後測試全部通過之後，開始重構: (已經用不到 #isEmpty 了)

    isEmpty() {
        return this.#items.length === 0;
    }

這是目前的程式碼:

module.exports = class {
    #items
    constructor() {
        this.#items = []
    }

    pushFront(item) {
        this.#items.unshift(item);
    }

    peekFront() {
        if (this.isEmpty()) {
            return null;
        }
        return this.#items[0];
    }

    popFront() {
        return this.#items.shift();
    }

    isEmpty() {
        return this.#items.length === 0;
    }
}

至少單向目前應該是沒問題，且測試也保證了以下幾個行為:

• 可以建立一個空的 Deque
• 可以在 Deque 的前端新增元素
• 可以在 Deque 的前端 peek 元素
• 可以在 Deque 的前端 pop 元素
• 可以判斷 Deque 是否為空

趁勝追擊，我們可以再實作 size 這個屬性:

    'push front 2 elements and get size should return 2': function() {
        const deque = new Deque();
        deque.pushFront(1);
        deque.pushFront(2);
        assert(deque.size === 2, 'size should be 2');
    },

接著一樣..你懂得..

    get size() {
        return 2;
    }

這時你會發現 size 這個屬性也通過了，這時你可以再加強一下 size 的測試:

    'push front 2 elements and pop 1 element and get size should return 1': function() {
        const deque = new Deque();
        deque.pushFront(1);
        deque.pushFront(2);
        deque.popFront();
        assert(deque.size === 1, 'size should be 1');
    },

接著你不得不開始做一點比較彈性的實作:

    get size() {
        return this.#items.length;
    }

這時你會發現 size 的測試都通過了。

接著讓我們進入的 back 的部分，基本上大同小異，所以類似的地方我就直接略過，只寫不同的部分。

目前的實作已經到下面這樣:

module.exports = class {
    #items
    constructor() {
        this.#items = []
    }

    pushFront(item) {
        this.#items.unshift(item);
    }

    pushBack(item) {
        this.#items.push(item);
    }

    peekFront() {
        if (this.isEmpty()) {
            return null;
        }
        return this.#items[0];
    }

    peekBack() {
        if (this.isEmpty()) {
            return null;
        }
        return this.#items[this.#items.length - 1];
    }

    popFront() {
        return this.#items.shift();
    }

    popBack() {
        return this.#items.pop();
    }

    isEmpty() {
        return this.#items.length === 0;
    }

    get size() {
        return this.#items.length;
    }
}

假設此時所有測試都已經通過，然後我再測一下循環的部分:

    'push front and pop back will return the last pushed front element': function() {
        const deque = new Deque();
        deque.pushFront(1);
        assert(deque.popBack() === 1, 'front element should be 1');
    },

    'push back and pop front will return the last pushed back element': function() {
        const deque = new Deque();
        deque.pushBack(1);
        assert(deque.popFront() === 1, 'back element should be 1');
    },

另外還有一組測試:

    'push front and push back then pop front should sequentially return the front elements': function() {
        const deque = new Deque();
        deque.pushBack(4);
        deque.pushBack(5);
        deque.pushBack(6);
        deque.pushFront(3);
        deque.pushFront(2);
        deque.pushFront(1);
        assert(deque.popFront() === 1, 'front element should be 1');
        assert(deque.popFront() === 2, 'front element should be 2');
        assert(deque.popFront() === 3, 'front element should be 3');
        assert(deque.popFront() === 4, 'front element should be 4');
        assert(deque.popFront() === 5, 'front element should be 5');
        assert(deque.popFront() === 6, 'front element should be 6');
    }

這時你會發現這些測試也通過了，這也保證了你的 Deque 是可以從兩端進出的。

好像哪裡怪怪的

到這邊可能會覺得哪裡怪怪的，這是因為我在這邊犯了一個錯誤，有點類似 過早優化 的概念(也就是過程不夠笨)，所以導致後面的測試都沒有失敗，雖然這邊的測試程式一眼就能看出有效，不過實際情況你可能還是需要看到失敗比較安心(?)

這個罪魁禍首在於我這邊的實作直接使用了 Array 的內建函數，基本上他就已經完成了功能，所以後面的測試也就沒有失敗了。

但這邊還有一個巨大的問題，就是這個 Deque 的時間複雜度，因為他使用了 Array 的內建函數，所以他的時間複雜度是 O(n)，這樣的話就失去了 Deque 的優勢，不過只保留了 Deque 的操作而已。

這種情況在 TDD 確實會遇到，不過既然現在我們有了測試，我們可以很安心的去將他重構為 O(1) 的時間複雜度。

重構雙向佇列

我先使用最單純的 Array 來實作，只是不使用內建函數，這樣也可以保證時間複雜度是 O(1)。

所以我需要一個索引來記錄 front 與 back 的位置，這樣就可以直接取出元素和放置元素。

所以我們先來沙盤推演一下:

• 當 pushFront 的時候，我們只要將元素放在 front 然後索引往前移動一格
• 當 pushBack 的時候，我們只要將元素放在 back 然後索引往後移動一格
• 當 popFront 的時候，我們只要取出 front 後面的元素，然後索引往前移動一格
• 當 popBack 的時候，我們只要取出 back 前面的元素，然後索引往後移動一格
• 當 peekFront 的時候，我們只要取出 front 後面的元素
• 當 peekBack 的時候，我們只要取出 back 前面的元素

這樣就可以保證時間複雜度是 O(1) 了，接著我們來實作他。

然後比較需要注意的是索引值不能為負，所以當 front 或 back 為 0 或上限的時候，需要做一點處理(也就是循環的部分)。

所以這邊容量也不能放太小，如果太小會導致元素被錯誤的覆蓋(除非你有做擴充或 full 的檢查)，不過在這邊先不考慮這些問題，就假設使用安全的數字最大值(Number.MAX_SAFE_INTEGER)。

如同前面所提的，因為這時你有測試，所以你可以很安心的去改，如果測試夠好，你甚至可以無腦的改，這時程式碼就會變成這樣:

module.exports = class {
    #items
    #length
    #front
    #back
    constructor() {
        this.#items = []
        this.#length = 0
        this.#front = 0
        this.#back = 1
    }

    pushFront(item) {
        this.#length++
        this.#items[this.#front] = item;
        this.#front = (this.#front || Number.MAX_SAFE_INTEGER) - 1
    }

    pushBack(item) {
        this.#length++
        this.#items[this.#back] = item;
        this.#back = (this.#back + 1) % Number.MAX_SAFE_INTEGER
    }

    peekFront() {
        if (this.isEmpty()) {
            return null;
        }
        const index = (this.#front + 1) % Number.MAX_SAFE_INTEGER
        return this.#items[index];
    }

    peekBack() {
        if (this.isEmpty()) {
            return null;
        }
        const index = (this.#back || Number.MAX_SAFE_INTEGER) - 1
        return this.#items[index];
    }

    popFront() {
        if (this.isEmpty()) {
            return null;
        }

        this.#length--
        this.#front = (this.#front + 1) % Number.MAX_SAFE_INTEGER
        const item = this.#items[this.#front];
        return item;
    }

    popBack() {
        if (this.isEmpty()) {
            return null;
        }

        this.#length--
        this.#back =  (this.#back || Number.MAX_SAFE_INTEGER) - 1
        const item = this.#items[this.#back];
        return item;
    }

    isEmpty() {
        return this.#length === 0;
    }

    get size() {
        return this.#length;
    }
}

這時你會發現你的測試都通過了，且時間複雜度也是 O(1) 了。

結語

這個範例還可以繼續加強，例如:

• 動態擴充容量
• 檢查是否滿了
• delete 以避免 memory leak

這些都是可以加強的地方，不過這邊只是簡單的實作，所以就不再加強了，最簡單的做法的話應該是把 items 直接改成 Object，然後在相應的地方做 delete 即可，可以練習看看。

這邊的範例也是為了讓你了解 TDD 的概念，是怎麼樣一直讓測試越來越具體，然後實作變得越來越通用，這樣的方式可以讓你的程式碼更加穩定，且可以更加放心的去重構，不再怕改 A 壞 B (至少在你有測試有效的範圍)。

然後也實作了一個 Deque 當作範例。寫著寫著就忘了舉例了，可以去看看今天的 Daily。

2290. Minimum Obstacle Removal to Reach Corner

這題絕對沒有 Hard，不要被難度標籤嚇到了，相信你可以的。