PHP算法与数据结构：实用指南

PHP算法与数据结构：实践

在Web开发领域，PHP依然是最流行的语言之一。然而，许多熟悉语法的开发者常常忽略了基础概念——算法与数据结构。理解这些主题不仅能提升代码质量，还能让你在面试中更具竞争力。在本文中，我们将通过实际代码示例，解析PHP中的关键算法与数据结构，你可以立即将其应用到自己的项目中。

1. 基础数据结构：栈与队列

栈和队列是实际应用中常用的线性数据结构。栈遵循LIFO（后进先出）原则，而队列遵循FIFO（先进先出）原则。在PHP中，可以使用内置数组函数来实现它们。

栈的实现

<?php\nclass Stack {\n    private $stack = [];\n\n    public function push($item) {\n        array_push($this->stack, $item);\n    }\n\n    public function pop() {\n        if ($this->isEmpty()) {\n            return null;\n        }\n        return array_pop($this->stack);\n    }\n\n    public function peek() {\n        return end($this->stack);\n    }\n\n    public function isEmpty() {\n        return empty($this->stack);\n    }\n}\n\n// 使用示例\n$stack = new Stack();\n$stack->push("第一个");\n$stack->push("第二个");\n$stack->push("第三个");\necho $stack->pop(); // 第三个\necho $stack->peek(); // 第二个\n?>

队列的实现

<?php\nclass Queue {\n    private $queue = [];\n\n    public function enqueue($item) {\n        array_push($this->queue, $item);\n    }\n\n    public function dequeue() {\n        if ($this->isEmpty()) {\n            return null;\n        }\n        return array_shift($this->queue);\n    }\n\n    public function front() {\n        return reset($this->queue);\n    }\n\n    public function isEmpty() {\n        return empty($this->queue);\n    }\n}\n\n// 使用示例\n$queue = new Queue();\n$queue->enqueue("第一个");\n$queue->enqueue("第二个");\n$queue->enqueue("第三个");\necho $queue->dequeue(); // 第一个\necho $queue->front();    // 第二个\n?>

这些数据结构在实现缓冲区、操作历史（撤销/重做）以及按顺序处理任务时不可或缺。

2. PHP排序算法

排序是编程中最常见的操作之一。我们来探讨两种经典实现：冒泡排序（用于学习）和快速排序（用于实际工作）。

冒泡排序（Bubble Sort）

<?php\nfunction bubbleSort(&$arr) {\n    $n = count($arr);\n    for ($i = 0; $i < $n - 1; $i++) {\n        for ($j = 0; $j < $n - $i - 1; $j++) {\n            if ($arr[$j] > $arr[$j + 1]) {\n                // 交换值\n                $temp = $arr[$j];\n                $arr[$j] = $arr[$j + 1];\n                $arr[$j + 1] = $temp;\n            }\n        }\n    }\n}\n\n$numbers = [64, 34, 25, 12, 22, 11, 90];\nbubbleSort($numbers);\nprint_r($numbers); // [11, 12, 22, 25, 34, 64, 90]\n?>

复杂度：O(n²) —— 不适合大型数组，但能很好地演示原理。

快速排序（Quick Sort）

<?php\nfunction quickSort($arr) {\n    if (count($arr) < 2) {\n        return $arr;\n    }\n\n    $pivot = $arr[0];\n    $left = $right = [];\n\n    for ($i = 1; $i < count($arr); $i++) {\n        if ($arr[$i] < $pivot) {\n            $left[] = $arr[$i];\n        } else {\n            $right[] = $arr[$i];\n        }\n    }\n\n    return array_merge(quickSort($left), [$pivot], quickSort($right));\n}\n\n$numbers = [3, 6, 8, 10, 1, 2, 1];\n$sorted = quickSort($numbers);\nprint_r($sorted); // [1, 1, 2, 3, 6, 8, 10]\n?>