本教學用 PCBA 測試流程作為情境,示範如何用堆疊(stack)在 O(n) 時間內:
- 建立每個節點的父子關係(parent_index、children_count)
- 生成章節式階層編號(如 1、1.2、2.1.3)
並以 collections.namedtuple 讓堆疊元素更易讀。
你會學到
- 為什麼用堆疊處理階層資料
- 如何用 namedtuple 優雅表達堆疊項目
- 兩段小工具:建立父子關係、產生階層編號
示例資料:PCBA 測試流程
每個 heading 只有兩個欄位:
- level:整數層級(1 是最高層)
- title:標題文字
headings = [
    {"level": 1, "title": "PCBA 測試流程"},
    {"level": 2, "title": "目視檢查"},
    {"level": 2, "title": "上電前測試"},
    {"level": 1, "title": "功能測試"},
    {"level": 2, "title": "ICT(在線測試)"},
    {"level": 3, "title": "開路/短路檢查"},
    {"level": 3, "title": "元件值量測"},
    {"level": 2, "title": "FCT(功能測試)"},
    {"level": 3, "title": "通訊介面驗證"},
    {"level": 3, "title": "電源時序檢查"},
    {"level": 2, "title": "ATE(自動化設備測試)"},
]為什麼用堆疊
- 堆疊維護「從根到目前節點的路徑」。
- 處理新節點時: - pop 掉所有層級 >= 當前層級的項目(它們不會是你的祖先)
- 此時堆疊頂端就是你的父節點
- push 當前節點進堆疊,供後續節點使用
 
- 每個節點最多入堆一次、出堆一次,時間 O(n)。
用 namedtuple 表示堆疊項目
from collections import namedtuple
from typing import List, Optional
StackItem = namedtuple("StackItem", ["level", "index"])常見陷阱與備註
- 欄位名稱需要是有效的 Python 識別字,不能以數字開頭、不能有空白、不能與關鍵字衝突;否則在定義時就會報錯。
- 欄位數與實例化傳入的參數數量必須一致。
- namedtuple 預設是不可變的(immutable);若需要可變欄位,考慮 dataclass。
namedtuple?
一、建立父子關係與 children_count
from collections import namedtuple
from typing import List, Optional
StackItem = namedtuple("StackItem", ["level", "index"])
def build_parent_child_relations(headings: List[dict]) -> None:
    """
    為每個 heading 建立:
      - parent_index:父節點在列表中的索引(根為 None)
      - children_count:子節點數
    原地修改;Time: O(n),Space: O(d)(d 為最大深度)
    """
    stack: List[StackItem] = []
    # 初始化欄位
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0
    for idx, h in enumerate(headings):
        lvl = h.get("level")
        if lvl is None:
            continue
        # 移除所有層級 >= 當前層級的項目
        while stack and stack[-1].level >= lvl:
            stack.pop()
        # 剩下頂端即父節點
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx
        # 父節點子數 +1
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1
        # 當前節點入堆疊
        stack.append(StackItem(lvl, idx))二、產生章節式階層編號 full_num_path
思路
- 維護一個數字堆疊 path,例如 [2, 1, 3] 代表「2.1.3」。
- 當前層比 path 長:補零再 +1
- 當前層比 path 淺:pop 到同層再 +1
- 同層:頂端 +1
實作
from typing import List
def assign_numbering(headings: List[dict]) -> None:
    """
    為每個 heading 產生 full_num_path(例如 1、1.2、2.1.3)。
    原地修改。
    """
    path: List[int] = []
    for h in headings:
        level = h.get("level")
        if level is None:
            h["full_num_path"] = ""
            continue
        # 補齊深度
        while len(path) < level:
            path.append(0)
        # 回退到目標層
        while len(path) > level:
            path.pop()
        # 目前層級計數 +1
        path[-1] += 1
        h["full_num_path"] = ".".join(str(x) for x in path)完整示範:套用在 PCBA 測試流程
from collections import namedtuple
from typing import List, Optional
StackItem = namedtuple("StackItem", ["level", "index"])
def build_parent_child_relations(headings: List[dict]) -> None:
    stack: List[StackItem] = []
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0
    for idx, h in enumerate(headings):
        lvl = h.get("level")
        if lvl is None:
            continue
        while stack and stack[-1].level >= lvl:
            stack.pop()
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1
        stack.append(StackItem(lvl, idx))
def assign_numbering(headings: List[dict]) -> None:
    path: List[int] = []
    for h in headings:
        level = h.get("level")
        if level is None:
            h["full_num_path"] = ""
            continue
        while len(path) < level:
            path.append(0)
        while len(path) > level:
            path.pop()
        path[-1] += 1
        h["full_num_path"] = ".".join(str(x) for x in path)
# 資料
headings = [
    {"level": 1, "title": "PCBA 測試流程"},
    {"level": 2, "title": "目視檢查"},
    {"level": 2, "title": "上電前測試"},
    {"level": 1, "title": "功能測試"},
    {"level": 2, "title": "ICT(在線測試)"},
    {"level": 3, "title": "開路/短路檢查"},
    {"level": 3, "title": "元件值量測"},
    {"level": 2, "title": "FCT(功能測試)"},
    {"level": 3, "title": "通訊介面驗證"},
    {"level": 3, "title": "電源時序檢查"},
    {"level": 2, "title": "ATE(自動化設備測試)"},
]
build_parent_child_relations(headings)
assign_numbering(headings)
for i, h in enumerate(headings):
    print(f'{i:>2}  L{h["level"]}  {h["full_num_path"]:>6}  '
          f'parent={h["parent_index"]}  children={h["children_count"]}  {h["title"]}')輸出:
可能輸出解讀
- 0 L1 1 parent=None children=2 PCBA 測試流程 - PCBA 測試流程是根,孩子有「目視檢查」「上電前測試」
 
- 3 L1 2 parent=None children=3 功能測試 - 功能測試是另一個根層級,孩子有「ICT」「FCT」「ATE」
 
- 5 L3 2.1.1 等 - 代表「功能測試 > ICT > 開路/短路檢查」
 
常見變體與注意
- 欄位名稱可依需求擴充,例如新增 id、slug。
- 資料若跳級(例:從 level 1 直接到 level 3),請在導入前做資料校驗或補齊策略。
- 若要輸出樹狀結構,可用 parent_index 重建 children 清單或直接在遍歷時建立 adjacency list。
重點總結
- 堆疊法用 push/pop 追蹤階層路徑,處理階層資料直覺且高效。
- namedtuple 讓堆疊項目具名屬性,兼具輕量與可讀性。
- 兩個簡短函式即可完成 PCBA 流程的父子關係與章節式編號。
推薦hahow線上學習python: https://igrape.net/30afN
用一個單一遍歷(單迴圈)同時完成:
- 父子關係(parent_index、children_count)
- 連續的章節號 full_num_path(例如 1、1.2、2.3.1)
做法要點
- 維護兩個結構: - stack: 保存從根到目前節點的路徑(含 level 與索引)。
- path: 章節號數列(如 [2,1,3])。
 
- 對每個 heading: - 依 level pop 掉不再是祖先的節點(更新 stack 與 path 同步回退)。
- 決定父節點(stack 頂端)。
- 對齊 path 長度到當前 level,補 0。
- 將 path[-1] += 1 取得新章節號。
- 設定 full_num_path、parent_index,並讓父節點 children_count += 1。
- 將當前節點 push 進 stack。
 
範例程式(單迴圈 O(n))
from collections import namedtuple
from typing import List, Optional
StackItem = namedtuple("StackItem", ["level", "index"])
def build_all_in_one(headings: List[dict]) -> None:
    stack: List[StackItem] = []
    path: List[int] = []
    # 初始化欄位
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0
        h["full_num_path"] = ""
    for i, h in enumerate(headings):
        level = h.get("level")
        if level is None:
            continue
        # 1) 回退到正確層級:同步調整 stack 與 path
        while stack and stack[-1].level >= level:
            stack.pop()
            path.pop()
        # 2) 決定父節點
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1
        # 3) 對齊 path 長度(處理跳級時會補 0)
        while len(path) < level:
            path.append(0)
        # 4) 目前層 +1,得到連續章節號
        path[-1] += 1
        h["full_num_path"] = ".".join(str(x) for x in path)
        # 5) 當前節點入堆疊
        stack.append(StackItem(level, i))特性
- 單迴圈、每個元素最多入堆一次出堆一次,時間 O(n),空間 O(d)(d 為最大深度)。
- 章節號天然連續:同層自動遞增;變深時從 1 開始(因為先補 0 再 +1);變淺時回退到對應層後再 +1。
- 可選擇在「補 0」處加入跳級校驗(當 level > prev_level + 1 時警告或拒絕)。
推薦hahow線上學習python: https://igrape.net/30afN