当前位置：首页 > PHP

php实现栈实现

2026-02-28 05:26:47PHP

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();
}