學習資源

https://labuladong.online/algo/data-structure-basic/deque-implement/

學習記錄

今天是學習的第 11 天，主要學習了雙端隊列（Deque）原理及實現：

什麼是雙端隊列？

雙端隊列是一種更靈活的隊列資料結構。與普通隊列相比，它在兩端都支援插入和刪除操作。

• 普通隊列：只能在隊尾插入元素，隊頭刪除元素
• 雙端隊列：隊頭和隊尾都可以插入、刪除元素

雙端隊列提供以下基本操作，且所有操作的時間複雜度都應為 O(1)：

var MyDeque = function() {
    // 從隊頭插入元素，時間複雜度 O(1)
    this.addFirst = function(e) {};

    // 從隊尾插入元素，時間複雜度 O(1)
    this.addLast = function(e) {};

    // 從隊頭刪除元素，時間複雜度 O(1)
    this.removeFirst = function() {};

    // 從隊尾刪除元素，時間複雜度 O(1)
    this.removeLast = function() {};

    // 查看隊頭元素，時間複雜度 O(1)
    this.peekFirst = function() {};

    // 查看隊尾元素，時間複雜度 O(1)
    this.peekLast = function() {};
};

用鏈表實現雙端隊列

使用雙鏈表時，我們可以直接利用鏈表的特性：

• 隊頭操作：對應鏈表頭部的插入和刪除
• 隊尾操作：對應鏈表尾部的插入和刪除

雙鏈表 MyLinkedList 的實現可以參考之前的單元：苦痛之路 Day 06 - 鏈表程式碼實現。

class MyListDeque {
    constructor() {
        // JavaScript 中沒有提供雙鏈表，所以使用之前實現的 `MyLinkedList` 類
        this.list = new MyLinkedList();
    }

    // 從隊頭插入元素，時間複雜度 O(1)
    addFirst(e) {
        this.list.addFirst(e);
    }

    // 從隊尾插入元素，時間複雜度 O(1)
    addLast(e) {
        this.list.addLast(e);
    }

    // 從隊頭刪除元素，時間複雜度 O(1)
    removeFirst() {
        return this.list.removeFirst();
    }

    // 從隊尾刪除元素，時間複雜度 O(1)
    removeLast() {
        return this.list.removeLast();
    }

    // 查看隊頭元素，時間複雜度 O(1)
    peekFirst() {
        return this.list.getFirst();
    }

    // 查看隊尾元素，時間複雜度 O(1)
    peekLast() {
        return this.list.getLast();
    }
}

// 範例
const myDeque = new MyListDeque();

// head <-> 1 <-> tail
myDeque.addFirst(1);

// head <-> 2 <-> 1 <-> tail
myDeque.addFirst(2);

// head <-> 2 <-> 1 <-> 3 <-> tail
myDeque.addLast(3);

// head <-> 2 <-> 1 <-> 3 <-> 4 <-> tail
myDeque.addLast(4);

// head <-> 1 <-> 3 <-> 4 <-> tail
myDeque.removeFirst();

// head <-> 1 <-> 3 <-> tail
myDeque.removeLast();

myDeque.peekFirst(); // 1
myDeque.peekLast();  // 3

用陣列實現雙端對列

使用環形陣列時，我們需要：

• 維護 start 和 end 兩個指標
• 利用取模運算實現環形效果
• 動態調整陣列大小以避免溢出

環形陣列 CycleArray 的實現可以參考之前的單元：苦痛之路 Day 07 - 環形陣列技巧及實現。

var MyArrayQueue = function() {
    this.arr = new CycleArray();

    // 從隊頭插入元素，時間複雜度 O(1)
    this.addFirst = function(e) {
        this.arr.addFirst(e);
    };

    // 從隊尾插入元素，時間複雜度 O(1)
    this.addLast = function(e) {
        this.arr.addLast(e);
    };

    // 從隊頭刪除元素，時間複雜度 O(1)
    this.removeFirst = function() {
        return this.arr.removeFirst();
    };

    // 從隊尾插入元素，時間複雜度 O(1)
    this.removeLast = function() {
        return this.arr.removeLast();
    };

    // 查看隊頭元素，時間複雜度 O(1)
    this.peekFirst = function() {
        return this.arr.getFirst();
    };

    // 查看隊尾元素，時間複雜度 O(1)
    this.peekLast = function() {
        return this.arr.getLast();
    };
};

// 範例
const myArray = new MyArrayQueue();

// {
//   arr: [1],
//   count: 1,
//   start: 0,
//   end: 0,
//   size: 1
// }
myArray.addFirst(1);

// {
//   arr: [1, 2],
//   count: 2,
//   start: 1,
//   end: 1,
//   size: 2
// }
myArray.addFirst(2);

// {
//   arr: [2, 1, 3, _],
//   count: 3,
//   start: 0,
//   end: 3,
//   size: 4
// }
myArray.addLast(3);

// {
//   arr: [2, 1, 3, 4],
//   count: 4,
//   start: 0,
//   end: 0,
//   size: 4
// }
myArray.addLast(4);

// {
//   arr: [_, 1, 3, 4],
//   count: 3,
//   start: 1,
//   end: 0,
//   size: 4
// }
myArray.removeFirst(); // 2

// {
//   arr: [_, 1, 3, _],
//   count: 2,
//   start: 1,
//   end: 3,
//   size: 4
// }
myArray.removeLast();  // 4

myArray.peekFirst();   // 1
myArray.peekLast();    // 3

學習總結

• 雙端隊列是一種更靈活的隊列資料結構。與普通隊列相比，它在兩端都支援插入和刪除操作。
  • 普通隊列：只能在隊尾插入元素，隊頭刪除元素
  • 雙端隊列：隊頭和隊尾都可以插入、刪除元素
• 分別使用雙鏈表和環形陣列實現雙端隊列