PHP数据结构链表与栈队列实现

PHP数据结构链表与栈队列实现

PHP的数组功能很强大，但有些场景自己实现数据结构能加深理解。今天用PHP实现链表、栈和队列。

链表的实现。

```php
class ListNode
{
public function __construct(
public mixed $data = null,
public ?ListNode $next = null
) {}
}

class LinkedList
{
private ?ListNode $head = null;
private int $size = 0;

public function addFirst(mixed $data): void
{
$this->head = new ListNode($data, $this->head);
$this->size++;
}

public function addLast(mixed $data): void
{
$node = new ListNode($data);
if ($this->head === null) {
$this->head = $node;
} else {
$current = $this->head;
while ($current->next !== null) $current = $current->next;
$current->next = $node;
}
$this->size++;
}

public function remove(mixed $data): bool
{
if ($this->head === null) return false;
if ($this->head->data === $data) {
$this->head = $this->head->next;
$this->size--;
return true;
}
$current = $this->head;
while ($current->next !== null) {
if ($current->next->data === $data) {
$current->next = $current->next->next;
$this->size--;
return true;
}
$current = $current->next;
}
return false;
}

public function toArray(): array
{
$result = [];
$current = $this->head;
while ($current !== null) {
$result[] = $current->data;
$current = $current->next;
}
return $result;
}
}

$list = new LinkedList();
$list->addLast(10);
$list->addLast(20);
$list->addFirst(5);
$list->remove(10);
print_r($list->toArray());
?>
>

栈的实现。后进先出。

```php
class Stack
{
private array $items = [];

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

public function pop(): mixed
{
if ($this->isEmpty()) throw new UnderflowException("栈为空");
return array_pop($this->items);
}

public function peek(): mixed
{
if ($this->isEmpty()) throw new UnderflowException("栈为空");
return $this->items[count($this->items) - 1];
}

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

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

$stack = new Stack();
$stack->push(10);
$stack->push(20);
$stack->push(30);
echo $stack->pop() . "\n";
echo $stack->peek() . "\n";
echo $stack->size() . "\n";
?>
>

队列的实现。先进先出。

```php
class Queue
{
private array $items = [];

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

public function dequeue(): mixed
{
if ($this->isEmpty()) throw new UnderflowException("队列为空");
return array_shift($this->items);
}

public function front(): mixed
{
if ($this->isEmpty()) throw new UnderflowException("队列为空");
return $this->items[0];
}

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

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

$queue = new Queue();
$queue->enqueue("A");
$queue->enqueue("B");
$queue->enqueue("C");
echo $queue->dequeue() . "\n";
echo $queue->front() . "\n";
echo $queue->size() . "\n";
?>
>

PHP的SplStack和SplQueue是内置的栈和队列实现，性能更好。但自己实现一遍能更清楚地理解数据结构的原理。数组配合array_push和array_pop可以模拟栈，array_push和array_shift可以模拟队列。