# 介紹
## 特點
棧（Stack）是一種 `后進先出`（英文：LIFO：Last In First Out） 的線性數據結構，并且只能 `從一頭` 進出。
棧主要有兩個操作：
入棧：將數據放到棧頂
出棧：將棧頂數據彈出棧，棧頂向下移一位
練習題：有 abcde 五個元素依次入棧（過程中可以出棧），以下得到的出棧結果是錯誤的是？
a. edcba
b. badec
c. eacbd
d. bcdae
答案：C 選項是錯誤的！根據棧的特點不可能得到 C 這個出棧結果。
練習題：有 abc 三個元素依次入棧（過程中可以出棧），以下得到的出棧結果是錯誤的是？
a. bac
b. cba
c. abc
d. cab
# 實現方式
棧的實現有兩種方式：
- 順序棧（數組實現）
- 鏈式棧（鏈表實現）
## 順序棧
用 `數組` 來實現一個棧結構。
~~~
class Stack {
construct() {
this._stack = [] // 桶中的數據
}
// 入棧操作
push(data) {
this._stack.push(data)
}
// 出棧操作
pop() {
return this._statck.pop()
}
// 清空棧
clear() {
this._stack = []
}
// 獲取棧中元素的數量
count() {
return this._stack.length
}
}
~~~
現實中的面試題：使用 JS 來模擬一個棧。
## 鏈式棧
用 `鏈表` 來實現棧的結構。
~~~
// 定義節點類
class Node {
constructor( data ) {
this.data = data // 節點中的數據
this.next = null // 下一個節點
}
}
// 棧
class LinkedListStack {
constructor() {
this.head = null // 棧頂元素
this.length = 0 // 棧中元素的個數
}
// 入棧
push( data ) {
// 1. 創建一個新的節點
let newNode = new Node(data)
// 2. 讓這個新節點指向原來的棧頂節點
if(this.head === null) {
// 如果是空節點，那么 head 直接指向這個新節點
this.head = newNode
} else {
// 讓新節點指向原棧頂節點
newNode.next = this.head
// 讓新節點變成棧頂
this.head = newNode
}
// 3. 棧中元素數量+1
this.length++
}
// 出棧
pop() {
// 1. 先取出棧頂節點中的數據
let data = this.head.data
// 2. 把 head 指針指向下一個元素（刪除原棧頂元素）
this.head = this.head.next
// 3. 棧中元素的數量-1
this.length--
// 4. 返回原棧頂元素
return data
}
}
~~~
