php实现栈实现
PHP 实现栈数据结构
栈是一种遵循 LIFO（后进先出）原则的数据结构，可以通过数组或链表实现。以下是两种常见的 PHP 栈实现方式。
基于数组的栈实现
PHP 数组天然支持栈操作，结合 array_push() 和 array_pop() 函数即可实现：
class ArrayStack {
private $stack;
public function __construct() {
$this->stack = [];
}
public function push($item) {
array_push($this->stack, $item);
}
public function pop() {
if ($this->isEmpty()) {
return null;
}
return array_pop($this->stack);
}
public function peek() {
if ($this->isEmpty()) {
return null;
}
return $this->stack[count($this->stack) - 1];
}
public function isEmpty() {
return empty($this->stack);
}
public function size() {
return count($this->stack);
}
}基于链表的栈实现
通过链表节点实现栈，避免数组动态扩容的开销：
class Node {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class LinkedListStack {
private $top;
public function __construct() {
$this->top = null;
}
public function push($data) {
$newNode = new Node($data);
$newNode->next = $this->top;
$this->top = $newNode;
}
public function pop() {
if ($this->isEmpty()) {
return null;
}
$popped = $this->top->data;
$this->top = $this->top->next;
return $popped;
}
public function peek() {
return $this->isEmpty() ? null : $this->top->data;
}
public function isEmpty() {
return $this->top === null;
}
}栈的基本操作复杂度
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek | O(1) | O(1) |
| isEmpty | O(1) | O(1) |
实际应用示例
检查字符串中的括号是否匹配：
function isBalanced($expression) {
$stack = new ArrayStack();
$pairs = [')' => '(', '}' => '{', ']' => '['];
for ($i = 0; $i < strlen($expression); $i++) {
$char = $expression[$i];
if (in_array($char, ['(', '{', '['])) {
$stack->push($char);
} elseif (in_array($char, [')', '}', ']'])) {
if ($stack->isEmpty() || $stack->pop() != $pairs[$char]) {
return false;
}
}
}
return $stack->isEmpty();
}性能优化建议
- 预分配数组空间：若已知栈最大容量，可用
SplFixedArray替代普通数组 - 避免频繁扩容：数组实现时，当容量不足时按固定比例（如 2 倍）扩容
- 内存管理：链表实现需注意及时解除无用节点的引用
两种实现方式的选择取决于具体场景：数组实现适合频繁随机访问，链表实现适合动态大小和内存敏感场景。
