Stack 堆疊
Stack 資料結構的學習
· 2 min read
Stack 堆疊 與 Queue 列隊 通常會放在一起講，兩種都是屬於抽象的資料類型，只是一種概念，在軟體工程中被廣泛運用。
可用任何方式實現 stack & queue，如: 連結串列（Linked List）、陣列（Array）。
stack 堆疊
像在堆石頭的一樣，只能從上方一直疊上去，要讓石頭變少，也是上方移除。
特性
- 後進先出 LIFO(Last in first out)
- 元素沒有 index
- 元素的新增與移除只能從 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 觀念練習題
以下會提供一系列的運算，請試著回答問題：
- 當運算都結束後，stack 內還有幾個項目？
- stack 的最上方（top）是什麼？
push flour
push milk
push eggs
pop
push leavening
push sugar
pop
pop答案
最後 stack 會剩下兩個元素
milk(top) flour
2 個
milk