php 栈的实现
栈的基本概念
栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在栈顶进行插入（push）和删除（pop）操作。栈的实现通常基于数组或链表。
基于数组的栈实现
使用数组实现栈时，需维护一个指针（或索引）指向栈顶元素。以下是PHP代码示例：
class Stack {
private $stack;
private $top;
public function __construct() {
$this->stack = array();
$this->top = -1;
}
public function push($value) {
$this->top++;
$this->stack[$this->top] = $value;
}
public function pop() {
if ($this->isEmpty()) {
return null;
}
$value = $this->stack[$this->top];
unset($this->stack[$this->top]);
$this->top--;
return $value;
}
public function peek() {
if ($this->isEmpty()) {
return null;
}
return $this->stack[$this->top];
}
public function isEmpty() {
return $this->top === -1;
}
public function size() {
return $this->top + 1;
}
}基于链表的栈实现
链表实现的栈更灵活，动态分配内存。以下是PHP代码示例：
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($value) {
$newNode = new Node($value);
$newNode->next = $this->top;
$this->top = $newNode;
}
public function pop() {
if ($this->isEmpty()) {
return null;
}
$value = $this->top->data;
$this->top = $this->top->next;
return $value;
}
public function peek() {
if ($this->isEmpty()) {
return null;
}
return $this->top->data;
}
public function isEmpty() {
return $this->top === null;
}
}栈的常见操作
- push($value)：将元素压入栈顶。
- pop()：移除并返回栈顶元素。
- peek()：返回栈顶元素但不移除。
- isEmpty()：检查栈是否为空。
- size()：返回栈中元素数量（仅数组实现需要）。
注意事项
- 数组实现的栈需注意数组越界问题。
- 链表实现的栈需注意内存管理，避免内存泄漏。
- PHP数组本身具备动态扩容特性，简化了数组实现的边界处理。
以上实现可根据实际需求扩展，例如添加异常处理或支持泛型数据。
