Stack 堆疊

Stack 資料結構的學習

-5 min read

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： 把最上層的元素移除

function Node(value) {  return {    value,    next: null  }}function Stack() {  let head = null  let length = 0  // 在最上層新增元素  const push = (value) => {    const 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) {      const node = head      head = null      length = 0      return node    }    let currentNode = head    while (currentNode.next.next !== null)      currentNode = currentNode.next    const 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  }}const 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

Table of Contents