學習資源

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

學習記錄

今天是學習的第 10 天，主要學習了用陣列實現隊列 / 棧：

用陣列實現棧

將陣列的尾部作為棧頂，利用動態陣列的 API 實現所有棧操作。陣列尾部的增刪操作的時間複雜度為 O(1)，符合棧的要求。

// 用陣列作為底層資料結構實現棧
class MyArrayStack {
    constructor() {
        this.list = [];
    }

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

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

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

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

用陣列實現隊列

用陣列實現隊列的挑戰

如果將尾部作為隊尾（入隊 O(1)），頭部作為隊頭，則出隊需要使用 shift() 方法，JavaScript 的 shift() 方法時間複雜度為 O(n)，因為需要移動所有元素

解決方案：使用環形陣列技巧，讓頭尾操作都達到 O(1) 的時間複雜度，下面是環形陣列的程式碼實現：

class CycleArray {
    constructor(size = 1) {
        this.size = size;
        this.arr = new Array(size);
        // start 指向第一個有效元素的索引，閉區間
        this.start = 0;
        // end 指向最後一個有效元素的下一個索引位置，開區間
        this.end = 0;
        this.count = 0;
    }

    resize(newSize) {
        // 創建新的陣列
        var newArr = new Array(newSize);
        // 將舊的陣列元素複製到新陣列中
        for (var i = 0; i < this.count; i++) {
            newArr[i] = this.arr[(this.start + i) % this.size];
        }
        this.arr = newArr;
        // 重置 start 和 end 指針
        this.start = 0;
        this.end = this.count;
        this.size = newSize;
    }

    // 在陣列頭部添加元素，時間複雜度 O(1)
    addFirst(val) {
        // 當陣列滿時，擴容為原來的兩倍
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // 因為 start 是閉區間，所以先左移，在賦值
        this.start = (this.start - 1 + this.size) % this.size;
        this.arr[this.start] = val;
        this.count++;
    }

    // 刪除陣列頭部元素，時間複雜度 O(1)
    removeFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // 因為 start 是閉區間，所以先賦值，再右移
        this.arr[this.start] = null;
        this.start = (this.start + 1) % this.size;
        this.count--;
        // 如果陣列元素數量減少到原大小的四分之一，則減小陣列大小為一半
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // 在陣列尾部添加元素，時間複雜度 O(1)
    addLast(val) {
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // 因為 end 是開區間，所以是先賦值，再右移
        this.arr[this.end] = val;
        this.end = (this.end + 1) % this.size;
        this.count++;
    }

    // 刪除陣列尾部元素，時間複雜度 O(1)
    removeLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // 因為 end 是開區間，所以先左移，再賦值
        this.end = (this.end - 1 + this.size) % this.size;
        this.arr[this.end] = null;
        this.count--;
        // 縮容
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // 獲取陣列頭部元素，時間複雜度 O(1)
    getFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        return this.arr[this.start];
    }

    // 獲取陣列尾部元素，時間複雜度 O(1)
    getLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // end 是開區間，指向的是下一個元素的位置，所以要減 1
        return this.arr[(this.end - 1 + this.size) % this.size];
    }

    isFull() {
        return this.count === this.size;
    }

    size() {
        return this.count;
    }

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

class MyArrayQueue {
    constructor() {
        this.arr = new CycleArray();
    }

    push(t) {
        this.arr.addLast(t);
    }

    pop() {
        return this.arr.removeFirst();
    }

    peek() {
        return this.arr.getFirst();
    }

    size() {
        return this.arr.size();
    }
}

學習總結

• 用陣列實作的棧，所有操作的時間複雜度都是 O(1)：push()、pop()、peek()、size()
• 用陣列實作隊列會遇到一個問題是 shift() 的時間複雜度是 O(n)，可以改用環形陣列來解決