PHP 算法与数据结构：从基础到实现

PHP中的算法与数据结构：从基础到实现

在现代Web开发中，掌握算法与数据结构不仅是学术技能，更是构建快速、可扩展且可靠应用程序的实用工具。PHP尽管被冠以"简单网站语言"的名号，但它提供了实现复杂计算任务所需的一切工具。本文将解析关键的数据结构与算法，更重要的是，展示如何用纯PHP实现它们并附上代码示例。

1. PHP中的基础数据结构

PHP内置类型（数组、对象）已能满足多数需求，但为了深入理解和优化，建议手动实现经典结构。

1.1. 栈（Stack）

栈遵循LIFO（后进先出）原则。用于撤销操作（undo）、括号解析、深度优先图遍历。

<?phpclass Stack {    private array $items = [];

    public function push($item): void {        array_push($this->items, $item);    }

    public function pop() {        if ($this->isEmpty()) {            throw new UnderflowException('Stack is empty');        }        return array_pop($this->items);    }

    public function peek() {        return end($this->items);    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// 示例：检查括号是否平衡function isBalanced(string $expression): bool {    $stack = new Stack();    $pairs = ['(' => ')', '{' => '}', '[' => ']'];

    for ($i = 0; $i < strlen($expression); $i++) {        $char = $expression[$i];        if (isset($pairs[$char])) {            $stack->push($char);        } elseif (in_array($char, $pairs)) {            if ($stack->isEmpty() || $pairs[$stack->pop()] !== $char) {                return false;            }        }    }    return $stack->isEmpty();}

echo isBalanced("({[]})") ? "已平衡" : "未平衡"; // 已平衡?>

1.2. 队列（Queue）

队列遵循FIFO（先进先出）原则。应用于任务队列系统、BFS（广度优先搜索）、数据缓冲。

<?phpclass Queue {    private array $items = [];

    public function enqueue($item): void {        $this->items[] = $item;    }

    public function dequeue() {        if ($this->isEmpty()) {            throw new UnderflowException('Queue is empty');        }        return array_shift($this->items);    }

    public function peek() {        return $this->items[0] ?? null;    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// 示例：模拟打印队列$printQueue = new Queue();$printQueue->enqueue("document1.pdf");$printQueue->enqueue("photo.jpg");$printQueue->enqueue("report.docx");

while (!$printQueue->isEmpty()) {    echo "正在打印: " . $printQueue->dequeue() . "";}?>

1.3. 二叉搜索树（BST）

树结构提供快速的查找、插入和删除操作（平均O(log n)）。

<?phpclass TreeNode {    public $value;    public ?TreeNode $left = null;    public ?TreeNode $right = null;

    public function __construct($value) {        $this->value = $value;    }}

class BinarySearchTree {    public ?TreeNode $root = null;

    public function insert($value): void {        $this->root = $this->insertNode($this->root, $value);    }

    private function insertNode(?TreeNode $node, $value): TreeNode {        if ($node === null)