# 鏈結串列（Linked List）
---
* **學習目標：**
* 理解鏈結串列的基本結構與特性
* 能設計節點類別（Node）與鏈結串類別（LinkedList）
* 比較鏈結串與陣列在插入與刪除的效率差異
---
## 🔖 鏈結串列基本概念
* 鏈結串列是一種**非連續記憶體結構**，節點以指標互相串接而成。
* 每個節點（Node）包含：
* **資料欄位 (data)**
* **指標欄位 (next)**，指向下一個節點。
```cpp
struct Node {
int data;
Node* next;
};
```
---
### Why linked list?
---
---
## 🚩 建立與遍檢鏈結串列
```cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};
Node* cur = head;
while (cur != nullptr) {
cout << cur->data << " ";
cur = cur->next;
}
// 輸出：10 20 30
}
```
---
## 📘 插入與刪除節點
### 🔹 在開頭插入
```cpp
void pushFront(Node*& head, int val) {
Node* newNode = new Node{val, head};
head = newNode;
}
```
### 🔹 在結尾插入
```cpp
void pushBack(Node*& head, int val) {
Node* newNode = new Node{val, nullptr};
if (!head) { head = newNode; return; }
Node* cur = head;
while (cur->next) cur = cur->next;
cur->next = newNode;
}
```
----
### 🔹 刪除指定值
```cpp
void deleteValue(Node*& head, int val) {
if (!head) return;
if (head->data == val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* cur = head;
while (cur->next && cur->next->data != val)
cur = cur->next;
if (cur->next) {
Node* temp = cur->next;
cur->next = temp->next;
delete temp;
}
}
```
---
## 🧙 鏈結串列透過類別封裝
```cpp
class LinkedList {
private:
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* head;
public:
LinkedList() : head(nullptr) {}
void pushBack(int val) {
Node* newNode = new Node(val);
if (!head) { head = newNode; return; }
Node* cur = head;
while (cur->next) cur = cur->next;
cur->next = newNode;
}
void display() {
for (Node* cur = head; cur; cur = cur->next)
cout << cur->data << " ";
cout << endl;
}
};
```
---
## 📗 雙向鏈結串 (Doubly Linked List)
```cpp
struct DNode {
int data;
DNode *prev, *next;
DNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};
```
----
---
## ⚙️ 單向 vs 雙向串列
| 類型 | 優點 | 缺點 |
| ---- | ----------- | ---------- |
| 單向串列 | 結構簡單、記憶體用量小 | 無法反向走路 |
| 雙向串列 | 可反向搜尋、刪除方便 | 多一個指標記憶體開銷 |
---
## 🧰 時間複雜度比較
| 操作 | 陣列 | 鏈結串列 |
| ---- | -------- | -------- |
| 插入開頭 | O(n) | **O(1)** |
| 插入中間 | O(n) | O(n) |
| 插入結尾 | O(1)* | O(n) |
| 随機存取 | **O(1)** | O(n) |
---
### Think
Circular linked list
---
# 🛠️ 堆疊與伏列 (Stack & Queue)
---
* **學習目標：**
* 了解 Stack 與 Queue 的結構特性
* 能用陣列與鏈結串列實作 Stack / Queue
* 瞭解問題適合的結構選擇
---
## 📗 Stack: 堆疊 (LIFO)
* Last-In First-Out：最後進入先被撤出
* 操作：push, pop, top, empty
----
----
### 範例實作
```cpp
#include <stack>
#include <iostream>
using namespace std;
int main() {
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
} // 30 20 10
}
```
---
## 🛃 Queue: 佇列 (FIFO)
* First-In First-Out：最先進入最先撤出
* 操作：push, pop, front, empty
----
----
### 範例實作
```cpp
#include <queue>
#include <iostream>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
} // 10 20 30
}
```
---
## 👉 手動實作 Stack (陣列版)
```cpp
class ArrayStack {
private:
int data[100];
int top = -1;
public:
void push(int x) { data[++top] = x; }
void pop() { if (top >= 0) --top; }
int peek() { return data[top]; }
bool empty() { return top == -1; }
};
```
Note:
- linked list
---
## 👉 手動實作 Queue (陣列版)
```cpp
class ArrayQueue {
private:
int data[100];
int front = 0, rear = 0;
public:
void push(int x) { data[rear++] = x; }
void pop() { if (front < rear) ++front; }
int peek() { return data[front]; }
bool empty() { return front == rear; }
};
```
Note:
- Circular trick
- doubly linked list is useful in queue and stack
---
## 📝 Stack 應用：括號配對檢查
```cpp
bool isValid(string s) {
stack<char> stk;
for (char c : s) {
if (c == '(' || c == '[' || c == '{')
stk.push(c);
else {
if (stk.empty()) return false;
char t = stk.top(); stk.pop();
if ((c == ')' && t != '(') ||
(c == ']' && t != '[') ||
(c == '}' && t != '{'))
return false;
}
}
return stk.empty();
}
```
---
## 🚕 Queue 應用：介紹 BFS (廣平優先搜尋)
* BFS 是用 queue 來緩衝前後等待序列
* 最簡單的例子：[路徑搜尋](https://ithelp.ithome.com.tw/articles/10281404)
---
## ⚖️ Stack vs Queue
| 結構 | 特性 | 應用報表 |
| ----- | ---- | ---------------- |
| Stack | LIFO | 動態循環, 回歸, 連續功能返回 |
| Queue | FIFO | 排統系統, 排序、任務, BFS |
---
### Think
- double-ended queue (deque)
----
- Double Stack Queue → simulate queue with two stacks
---
## 🛠️ 課堂練習 (Lab)
1. 利用 stack 實作計算機程式
2. 用 queue 實作 BFS 搜索
---
## 💡 本週作業
* 使用 stack 實作演算式轉換（infix → postfix）與評估
* 使用 queue 模擬量體利用、排班統計
{"description":"學習目標：","title":"Linked List & stack, queue","contributors":"[{\"id\":\"01487228-6720-47a9-875f-2f01b5d455ad\",\"add\":7066,\"del\":1067,\"latestUpdatedAt\":1760234148564}]"}