資料結構 part 1: Stack & queue 堆疊與佇列
===

---

###### tags: `data strcuture`, `資料結構`

這裡的筆記來自於《JavaScript 資料結構及演算法》和 Wilson Ren 的課程。

# Stack 堆疊 (LIFO)

- **LIFO 即 Last In first Out**，生活實例：書，或任何由下往上堆疊的，為了要拿中間或是最後的東西，必須先把最上方的逐一拿走。
- 宣告堆疊的資料結構：[] 陣列，例如：`let arr = [1, 3, 5]` (1 是最底層，5是最頂層)。
- 方法：
- push(): 將元素增加到陣列最頂層。
- pop(): 移除最頂層的元素。
- peek(): 返回最頂層的元素，但不修改。
- isEmpty(): Boolean，若沒有元素就返回 `true`，有就返回 `false` 。
- clear(): 清除堆疊。
- size(): 返回堆疊元素個數

### 增加或刪除
使用 `push()` 和 `pop()` 來新增或刪除資料，是符合 `LIFO` 的原則，因為 `push()` 會把新的資料放在最頂層(最後一項)，而 `pop()` 則是會刪除頂層(最後一項)資料。

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(ele) {
        this.items.push(ele);
    }
    pop() {
        return this.items.pop();
    }
}

### 額外輔助的方法，例如想知道最頂層新增元素是什麼
假設長度為 k, 要存取最後的元素：`k-1`

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(ele) {
        this.items.push(ele);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
}


### 完整程式碼

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(ele) {
        this.items.push(ele);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return this.items === 0;
    }
    size() {
        return this.items.length;
    }
    clear() {
        this.items = [];
    }
    print() {
        console.log(this.items);
    }
}

const stack = new Stack();

stack.push(3);
stack.push(5);
stack.push(7);
stack.printAll(); // [ 3, 5, 7 ]
stack.pop();
stack.printAll(); // [3, 5]
console.log(stack.peek()); // 5
console.log(stack.isEmpty()); // false
console.log(stack.size()); // 2