今天要來介紹的資料結構是堆疊。
我們可以用一疊書來做比喻堆疊，最一開始被放在桌上的書會被壓在最下面，而最後被放在書堆的書本則在書堆最上面。而當要拿書離開時，不能從中間抽書出來，必須從最上面的書開始拿取。

我們再用圖片來解釋一次:

我們可以把A~E的資料看成一本本書，A雖然最先被放入書堆，但是會等到最後才會被拿出來，這就是堆疊 先入後出(FILO, First-in-Last-out) 的特性。
而E最後被放入書堆，但會被最先拿出來，此為堆疊 後入先出(LIFO, Last-in-First-out) 的特性。

接著來介紹幾個堆疊的常見操作方法，待會我們將會實做這些函式：

• 推入 push()：將資料放入堆疊頂端，堆疊頂端移到新放入的資料。
• 彈出 pop()：將堆疊頂端資料移除，堆疊頂端移到移除後的下一筆資料。
• peek(): 查出堆疊最上方的元素
• size(): 查出堆疊共有幾個元素
• isEmpty(): 是否堆疊內無元素

常見應用:

• 網頁瀏覽器的「回到前一頁」功能，最先瀏覽的頁面會在最後一此點到前一頁按鈕時才出現
• 河內塔(搭配遞迴)
• 可以用 Stack 寫深度優先搜尋演算法（Depth-First-Search，DFS）

看完前面的介紹後，我們來實作堆疊吧!
我們使用linked list來做出堆疊。

先寫出基本結構，建立LinkedStack的類別，並用new 建立stack物件

class StackNode {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = 0
  }

  // 判斷空堆疊
  isEmpty() {

  }

  // 堆疊長度
  length() {

  }

  // 新增堆疊元素
  push(value) {

  }

  // 刪除堆疊元素
  pop() {

  }

  // 查看堆疊最上面元素
  peek() {

  }
}

let stack = new LinkedStack()

完成 isEmpty() 方法:

top為堆疊最上面的元素，如果它不存在就代表堆疊為空

isEmpty() {
  return this.top === null
}

完成 push() 方法:

將要新增的值變成節點，讓新節點的指標指向原本的top節點，再讓新節點變成top節點，堆疊size加一

push(value) {
  let node = new StackNode(value)
  node.next = this.top
  this.top = node
  this.size++
}

完成 pop() 方法:

邏輯相當簡單，將top下的那個元素換成堆疊的top就可以了，最後這個函式會回傳被pop出的值，堆疊size減一

pop() {
  let result = this.top
  this.top = this.top.next
  this.size--
  return result.data
}

完成 peek() 方法:

回傳top的值即可

peek() {
  return this.top.data
}

完成 length() 方法:

由於我們在建立LinkedStack類別時已經讓之後產生的物件有size大小的屬性，因此直接回傳此size值即可。

length() {
  return this.size
}

堆疊的時間複雜度

也可以參考: Time and Space Complexity of Stack

• push: O(1)
• pop: O(1)
• search: O(n)
• peek: O(1)

Priority Queue 優先權佇列

和一般的 queue 差別在它每一個 element 都額外帶有優先值，愈優先的放在愈前面。分為最大優先佇列（max-priority Queue）與最小優先佇列（min-priority Queue）兩種。

應用:

• 動態尋找最佳或最差的元素
• Huffman Coding，資料壓縮

本次實作的程式碼在此:
https://github.com/a90100/javascript-data-structure/blob/master/day6-stack-linked-list.js

堆疊的介紹就到這邊結束，明天我們將會運用學到的堆疊解決一個問題!