Stack 堆疊

Stack 堆疊 與 Queue 列隊 通常會放在一起講，兩種都是屬於抽象的資料類型，只是一種概念，在軟體工程中被廣泛運用。

可用任何方式實現 stack & queue，如: 連結串列（Linked List）、陣列（Array）。

stack 堆疊

像在堆石頭的一樣，只能從上方一直疊上去，要讓石頭變少，也是上方移除。

特性

1. 後進先出 LIFO(Last in first out)
2. 元素沒有 index
3. 元素的新增與移除只能從 stack 的上方

使用 Linked List 實作 Stack

如果不了解 Linked List 的，可以參考這一篇 Linked List(連結串列)。

在 Stack 的概念中，我們建立的 Linked List 只能使用 push, pop 方法，不能使用 shift, unshift, insertAt, removeAt。

要實作的方法：
push： 在最上層新增元素
pop： 把最上層的元素移除

const Node = (value) => {
  return {
    value,
    next: null
  }
}

const Stack = () => {
  let head = null
  let length = 0
  // 在最上層新增元素
  const push = (value) => { 
    let newNode = Node(value)
    if (head === null) head = newNode
    else {
      let currentNode = head
      while (currentNode.next !== null) {
        currentNode = currentNode.next
      }
      currentNode.next = newNode
    }

    length++
  }  
  // 把最上層的元素移除
  const pop = () => {
    if (head === null) return null
    if (length === 1) {
      let node = head
      head = null
      length = 0
      return node
    }
    let currentNode = head
    while (currentNode.next.next !== null) {
      currentNode = currentNode.next
    }
    let popNode = currentNode.next
    currentNode.next = null
    length--
    return popNode
  }

  const printAll = () => {
    if (head === null) {
      console.log('Nothing in this linked list')
      return
    }

    let currentNode = head
    while (currentNode !== null) {
      console.log(currentNode.value)
      currentNode = currentNode.next
    }
  }

  return {
    head,
    length,
    push,
    pop,
    printAll
  }
}


let myStack = Stack()
myStack.push('Mike')
myStack.push('Harry')
myStack.push('James')
myStack.pop()
myStack.printAll()

印出結果：
Mike
Harry

Stack 觀念練習題

以下會提供一系列的運算，請試著回答問題：

1. 當運算都結束後，stack 內還有幾個項目？
2. stack 的最上方（top）是什麼？

push flour
push milk
push eggs
pop 
push leavening
push sugar
pop
pop

答案

最後 stack 會剩下兩個元素

milk(top)
flour

2 個
milk

LeetCoode 練習題

20. Valid Parentheses

155. Min Stack

1047. Remove All Adjacent Duplicates In String