---
tags: DSA in JavaScript
---
# Ch21. Stack & Queue

Stack 與 Queue 算是比較抽象的資料結構，符合對應的特性：

- stack：資料操作方式為**後進先出**
- queue：資料操作方式為**先進先出**

## Stack

只要符合後進先出的特性就可以被稱為 stack。

### 有使用 stack 的場景

- call stack
- undo / redo
- 上一頁 / 下一頁

### 使用陣列實作 stack

- 使用 push + pop 方法
- 使用 shift + unshift 方法 (時間複雜度較高，不建議)

### 使用串列實作 stack

基本架構與 linked list 大致相同，方法則會使用串列中的 shift 與 unshift，不使用 pop 的原因是時間複雜度較高。

class Node {
  constructor (value) {
    this.value = value
    this.next = null
  }
}

class Stack {
  constructor () {
    this.first = null
    this.last = null
    this.size = 0
  }

  push (value) {
  // 此處的 push，功能等同於單向鏈節串列的 unshift 方法
  // 回傳值為加入節點後的串列長度
    const created = new Node(value)
    if (!this.size) {
      this.first = created
      this.last = this.first
    } else {
      created.next = this.first
      this.first = created
    }
    return ++this.size
  }

  pop () {
  // 此處的 pop 方法，等同於鏈結串列的 shift 方法
  // 完成後會回傳被移除節點的值
    if (!this.size) return null
    const removed = this.first
    if (this.size === 1) {
      this.last = null
    }
    this.first = removed.next
    this.size--
    return removed.value
  }
}

## Queue

> ~~顧名思義，排隊~~

只要符合先進先出的資料結構也可以被稱為 queue

### 使用 queue 的例子

- 背景處理
- 上傳資料
- 程式碼運作

### 使用陣列實作 queue

- 使用 push + shift 方法
- 使用 unshift + pop 方法

以上方法都不建議，因為時間複雜度都比較高。

### 使用串列實作 queue

queue 的節點與 stack 相同，在此不多贅述。其中增加節點的方法稱為 enqueue，可以使用串列的 push 實作，而刪除節點的方法稱為 dequeue，則可以使用 shift 方式實作。

class Queue {
  constructor () {
    this.first = null
    this.last = null
    this.size = 0
  }

  enqueue (value) {
    const created = new Node(value)
    if (!this.first) {
      this.first = created
      this.last = this.first
    } else {
      this.last.next = created
      this.last = created
    }
    return ++this.size
  }

  dequeue () {
    if (!this.first) return null
    const removed = this.first
    if (this.size === 1) {
      this.last = null
    }
    this.first = removed.next
    this.size--
    return removed.value
  }
}