PHP SPL SplStack：基於雙向鏈表的堆疊實作與應用

SplStack 繼承 SplDoublyLinkedList，將迭代器模式設為 IT_MODE_LIFO（後進先出），即得標準堆疊行為。

類別結構

SplStack extends SplDoublyLinkedList
    // 繼承所有雙向鏈表方法
    // push() = 入堆
    // pop()  = 出堆
    // top()  = 看堆頂
    // bottom() = 看堆底
    // setIteratorMode(IT_MODE_LIFO | IT_MODE_KEEP/DELETE)

基本操作

<?php
$stack = new SplStack();

// 入堆
$stack->push('a');
$stack->push('b');
$stack->push('c'); // 堆頂為 'c'

// 看堆頂（不移除）
echo $stack->top(); // c

// 出堆
echo $stack->pop(); // c
echo $stack->pop(); // b

// 迭代（預設 LIFO + KEEP，迭代後資料保留）
foreach ($stack as $item) {
    echo $item . PHP_EOL; // a
}

// 設定迭代模式：LIFO + DELETE（迭代時消耗）
$stack->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);
foreach ($stack as $item) {
    echo $item; // a
}
echo $stack->count(); // 0

關鍵差異：SplStack vs SplDoublyLinkedList

實戰應用：表達式求值、括號匹配、歷史記錄

<?php
// 括號匹配驗證
function bracketsOk($str) {
    $stack = new SplStack();
    $pairs = ['('=>')', '['=>']', '{'=>'}'];
    foreach (str_split($str) as $ch) {
        if (isset($pairs[$ch])) {
            $stack->push($ch);
        } elseif (in_array($ch, $pairs)) {
            if ($stack->isEmpty()) return false;
            $open = $stack->pop();
            if ($pairs[$open] !== $ch) return false;
        }
    }
    return $stack->isEmpty();
}

var_dump(bracketsOk('({[]})')); // true
var_dump(bracketsOk('({[})'));  // false

效能特徵

• push/pop/top：**O(1)**，尾部操作無位移開銷
• 記憶體：雙向鏈表節點開銷，單元素約 48-64 bytes（64位元）
• 適合：高頻入出堆、深度不大（<10萬）場景
• 極大深度（百萬級）建議改用 SplFixedArray 模擬堆疊，記憶體更省