學習資源

https://labuladong.online/algo/data-structure-basic/linked-queue-stack/

學習記錄

今天是學習的第 9 天，主要學習了用鏈表實現隊列 / 棧：

由於棧和隊列都是「操作受限」的資料結構，它們的實現其實非常簡單 – 直接調用雙鏈表的 API 即可，下面是在單元 苦痛之路 Day 06 - 鏈表程式碼實現 的雙鏈表程式碼：

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class MyLinkedList {
    // 虛擬頭尾節點
    constructor() {
        this.head = new Node(null);
        this.tail = new Node(null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    // ***** 增 *****

    addLast(e) {
        const x = new Node(e);
        const temp = this.tail.prev;
        temp.next = x;
        x.prev = temp;
        // temp <-> x

        x.next = this.tail;
        this.tail.prev = x;
        // temp <-> x <-> tail
        this.size++;
    }

    addFirst(e) {
        const x = new Node(e);
        const temp = this.head.next;
        // head <-> temp
        temp.prev = x;
        x.next = temp;

        this.head.next = x;
        x.prev = this.head;
        // head <-> x <-> temp
        this.size++;
    }

    add(index, element) {
        this.checkPositionIndex(index);
        if (index === this.size) {
            this.addLast(element);
            return;
        }

        // 找到 index 對應的 Node
        const p = this.getNode(index);
        const temp = p.prev;
        // temp <-> p

        // 要插入的新 Node
        const x = new Node(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        this.size++;
    }

    // ***** 刪 *****

    removeFirst() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        // 虛擬節點的存在是我們不用考慮空指針的問題
        const x = this.head.next;
        const temp = x.next;
        // head <-> x <-> temp
        this.head.next = temp;
        temp.prev = this.head;

        // head <-> temp

        this.size--;
        return x.val;
    }

    removeLast() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        const x = this.tail.prev;
        const temp = x.prev;
        // temp <-> x <-> tail

        this.tail.prev = temp;
        temp.next = this.tail;

        // temp <-> tail

        this.size--;
        return x.val;
    }

    remove(index) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const x = this.getNode(index);
        const prev = x.prev;
        const next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;

        this.size--;

        return x.val;
    }

    // ***** 查 *****

    get(index) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const p = this.getNode(index);

        return p.val;
    }

    getFirst() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.head.next.val;
    }

    getLast() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.tail.prev.val;
    }

    // ***** 改 *****

    set(index, val) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const p = this.getNode(index);

        const oldVal = p.val;
        p.val = val;

        return oldVal;
    }

    // ***** 其他工具函式 *****

    size() {
        return this.size;
    }

    isEmpty() {
        return this.size === 0;
    }

    getNode(index) {
        this.checkElementIndex(index);
        let p = this.head.next;
        // TODO: 可以優化，通過 index 判斷從 head 還是 tail 開始遍歷
        for (let i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    isElementIndex(index) {
        return index >= 0 && index < this.size;
    }

    isPositionIndex(index) {
        return index >= 0 && index <= this.size;
    }

    // 檢查 index 索引位置是否可以存在元素
    checkElementIndex(index) {
        if (!this.isElementIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    // 檢查 index 索引位置是否可以添加元素
    checkPositionIndex(index) {
        if (!this.isPositionIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    display() {
        console.log(`size = ${this.size}`);
        let p = this.head.next;
        let str = "";
        while (p !== this.tail) {
            str += `${p.val} <-> `;
            p = p.next;
        }
        console.log(str + "null\n");
    }
}

用雙鏈表實現隊列

將雙鏈表的尾部作為隊尾，頭部作為隊頭，利用雙鏈表頭尾增刪元素都是 O(1) 的特性。

// 用雙鏈表實現隊列
class MyLinkedQueue {
  constructor() {
    this.list = new MyLinkedList();
  }

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

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

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

  // 返回隊列中的元素個數，時間複雜度 O(1)
  size() {
    return this.list.getSize();
  }
}

// 測試
const queue = new MyLinkedQueue();

queue.push(1);
queue.push(2);
queue.push(3);
// 現在鏈表變成了 1 <-> 2 <-> 3

// 查看隊頭元素 1
console.log(queue.peek());

// 從隊頭刪除元素 1，現在鏈表變成了 2 <-> 3
console.log(queue.pop());

// 從隊頭刪除元素 2，現在鏈表變成了 3
console.log(queue.pop());

// 查看隊頭元素 3
console.log(queue.peek());

用雙鏈表實現棧

將雙鏈表的尾部作為棧頂，利用雙鏈表尾部增刪元素時間複雜度為 O(1) 的特性。

// 用雙鏈表實現棧
class MyLinkedStack {
  constructor() {
    this.list = new MyLinkedList();
  }

  // 向棧頂加入元素，時間複雜度 O(1)
  push(e) {
    this.list.addLast(e);
  }

  // 從棧頂彈出元素，時間複雜度 O(1)
  pop() {
    return this.list.removeLast();
  }

  // 查看棧頂元素，時間複雜度 O(1)
  peek() {
    return this.list.getLast();
  }

  // 返回棧中的元素個數，時間複雜度 O(1)
  size() {
    return this.list.getSize();
  }
}

// 測試
const stack = new MyLinkedStack();

stack.push(1);
stack.push(2);
stack.push(3);
// 現在鏈表變成了 1 <-> 2 <-> 3

// 查看棧頂元素 3
console.log(stack.peek());

// 從棧頂彈出元素 3，現在鏈表變成了 1 <-> 2
console.log(stack.pop());

// 從棧頂彈出元素 2，現在鏈表變成了 1
console.log(stack.pop());

// 查看棧頂元素 1
console.log(stack.peek());

學習總結

• 用雙鏈表實現棧和隊列，直接調用前面實現的雙鏈表 API 即可
• 隊列：尾部作隊尾，頭部作隊頭，實現 FIFO 特性
• 棧：尾部作棧頂，實現 LIFO 特性
• 所有操作時間複雜度都是 O(1)