Pair / Stack / Queue / PriorityQueue

概述

DS 扩展还提供了四种专用的数据结构：Pair（键值对）、Stack（栈/LIFO）、Queue（队列/FIFO）和 PriorityQueue（优先级队列）。本章详细讲解这四种数据结构的用法和适用场景。

基础概念

数据结构对比

结构	特点	时间复杂度	适用场景
`Pair`	固定两个值（key, value）	O(1)	Map 遍历返回值
`Stack`	后进先出（LIFO）	push/pop O(1)	撤销操作、DFS
`Queue`	先进先出（FIFO）	push/pop O(1)	任务调度、BFS
`PriorityQueue`	按优先级出队	insert O(log n)	任务调度

语法与代码

Pair — 键值对

php

<?php

declare(strict_types=1);

use Ds\Pair;

// 创建 Pair
$pair = new Pair('name', 'Alice');

// 访问
echo $pair->key;    // name
echo $pair->value;  // Alice

// 修改
$pair->value = 'Bob';

// Pair 是 Map 遍历时每个元素的类型
$map = new \Ds\Map(['name' => 'Alice', 'age' => 30]);
foreach ($map as $pair) {
    echo "{$pair->key}: {$pair->value}\n";
}

// toArray
$arr = $pair->toArray();
// ['name' => 'Alice']

// copy
$copy = $pair->copy();

Stack — 栈（LIFO）

php

<?php

declare(strict_types=1);

use Ds\Stack;

// 创建
$stack = new Stack();
// 或从数组创建
$stack = new Stack([1, 2, 3]);

// push - 压入
$stack->push('a');
$stack->push('b', 'c');

// pop - 弹出
echo $stack->pop();  // c
echo $stack->pop();  // b

// peek - 查看栈顶（不移除）
echo $stack->peek(); // a

// 统计
echo $stack->count();   // 1
echo $stack->isEmpty(); // false

// toArray
$arr = $stack->toArray();
// ['a']

// copy
$copy = $stack->copy();

Queue — 队列（FIFO）

php

<?php

declare(strict_types=1);

use Ds\Queue;

// 创建
$queue = new Queue();
// 或从数组创建
$queue = new Queue([1, 2, 3]);

// push - 入队
$queue->push('task1');
$queue->push('task2', 'task3');

// pop - 出队
echo $queue->pop();  // 1（先入先出）
echo $queue->pop();  // 2

// peek - 查看队首（不移除）
echo $queue->peek(); // 3

// 统计
echo $queue->count();   // 1
echo $queue->isEmpty(); // false

// toArray
$arr = $queue->toArray();
// [3]

PriorityQueue — 优先级队列

php

<?php

declare(strict_types=1);

use Ds\PriorityQueue;

// 创建（第二个参数指定排序方式）
$queue = new PriorityQueue();
// PriorityQueue::MIN = 最小优先级先出（默认）
// PriorityQueue::MAX = 最大优先级先出

// push(value, priority)
$queue->push('low', 3);      // 优先级 3（低）
$queue->push('critical', 1); // 优先级 1（高）
$queue->push('medium', 2);   // 优先级 2（中）

// pop - 按优先级弹出
echo $queue->pop();  // critical（优先级 1 最先）
echo $queue->pop();  // medium
echo $queue->pop();  // low

// peek - 查看最高优先级元素
$queue->push('task1', 1);
$queue->push('task2', 2);
echo $queue->peek(); // task1

// 统计
echo $queue->count();   // 2
echo $queue->isEmpty(); // false

详细说明

Stack 实现细节

Stack 内部使用 Vector 实现，push 和 pop 操作在末尾进行，时间复杂度为 O(1)。

php

<?php

declare(strict_types=1);

use Ds\Stack;

$stack = new Stack();

// Stack 的 push 等同于 Vector 的 push
// Stack 的 pop 等同于 Vector 的 pop
// Stack 只暴露栈相关的操作，限制了访问方式
// 这使得 Stack 的语义更清晰

Queue 实现细节

Queue 内部使用 Deque 实现，push 在末尾添加，pop 从首部移除，两者都是 O(1)。

php

<?php

declare(strict_types=1);

use Ds\Queue;

$queue = new Queue();

// Queue 的 push 等同于 Deque 的 push（末尾）
// Queue 的 pop 等同于 Deque 的 shift（首部）
// Queue 不允许在中间操作，语义更清晰

PriorityQueue 排序方式

php

<?php

declare(strict_types=1);

use Ds\PriorityQueue;

// MIN 模式（默认）- 优先级值小的先出
$minQueue = new PriorityQueue();
$minQueue->push('A', 3);
$minQueue->push('B', 1);
echo $minQueue->pop();  // B（优先级 1）

// MAX 模式 - 优先级值大的先出
$maxQueue = new PriorityQueue(PriorityQueue::MAX);
$maxQueue->push('A', 3);
$maxQueue->push('B', 1);
echo $maxQueue->pop();  // A（优先级 3）

选择建议

Pair 通常是 Map 遍历的副产品，不需要单独创建
Stack 用于需要 LIFO 语义的场景（撤销、回溯、表达式求值）
Queue 用于需要 FIFO 语义的场景（消息队列、任务调度）
PriorityQueue 用于需要优先级的任务调度

实战示例

撤销/重做系统

php

<?php

declare(strict_types=1);

use Ds\Stack;

class UndoManager
{
    private Stack $undoStack;
    private Stack $redoStack;

    public function __construct()
    {
        $this->undoStack = new Stack();
        $this->redoStack = new Stack();
    }

    public function execute(string $action, callable $callback): void
    {
        $callback();
        $this->undoStack->push($action);
        $this->redoStack->clear();
    }

    public function undo(): ?string
    {
        if ($this->undoStack->isEmpty()) {
            return null;
        }
        $action = $this->undoStack->pop();
        $this->redoStack->push($action);
        return $action;
    }

    public function redo(): ?string
    {
        if ($this->redoStack->isEmpty()) {
            return null;
        }
        $action = $this->redoStack->pop();
        $this->undoStack->push($action);
        return $action;
    }
}

$um = new UndoManager();
$um->execute('type', fn() => null);
$um->execute('delete', fn() => null);
echo $um->undo();  // delete
echo $um->redo();   // delete

任务调度器

php

<?php

declare(strict_types=1);

use Ds\PriorityQueue;

class TaskScheduler
{
    private PriorityQueue $queue;

    public function __construct()
    {
        $this->queue = new PriorityQueue();
    }

    public function addTask(string $task, int $priority): void
    {
        $this->queue->push($task, $priority);
    }

    public function nextTask(): ?string
    {
        if ($this->queue->isEmpty()) {
            return null;
        }
        return $this->queue->pop();
    }

    public function pendingCount(): int
    {
        return $this->queue->count();
    }
}

$scheduler = new TaskScheduler();
$scheduler->addTask('send_email', 5);
$scheduler->addTask('generate_report', 2);
$scheduler->addTask('backup_db', 10);

echo $scheduler->nextTask();  // generate_report（优先级 2）
echo $scheduler->nextTask();  // send_email（优先级 5）
echo $scheduler->nextTask();  // backup_db（优先级 10）

消息队列（BFS 模式）

php

<?php

declare(strict_types=1);

use Ds\Queue;

class MessageQueue
{
    private Queue $queue;

    public function __construct()
    {
        $this->queue = new Queue();
    }

    public function send(string $message): void
    {
        $this->queue->push($message);
    }

    public function receive(): ?string
    {
        if ($this->queue->isEmpty()) {
            return null;
        }
        return $this->queue->pop();
    }

    public function pending(): int
    {
        return $this->queue->count();
    }
}

$mq = new MessageQueue();
$mq->send('hello');
$mq->send('world');
echo $mq->receive();  // hello
echo $mq->receive();  // world
echo $mq->receive();  // null

Pair 的高级用法

php

<?php

declare(strict_types=1);

use Ds\Pair;

// Pair 是不可变的（没有 setter）
$pair = new Pair('key', 'value');
echo $pair->key;    // key
echo $pair->value;  // value

// toArray
$arr = $pair->toArray();
// ['key' => 'value']

// Pair 实现了 ArrayAccess
echo $pair['key'];    // key
echo $pair['value'];  // value

// jsonSerialize
echo json_encode($pair);  // {"key":"value"}

// copy
$copy = $pair->copy();

Stack 的高级用法

php

<?php

declare(strict_types=1);

use Ds\Stack;

// 括号匹配检查
function checkBrackets(string $input): bool
{
    $stack = new Stack();
    $pairs = ['(' => ')', '[' => ']', '{' => '}'];

    for ($i = 0; $i < strlen($input); $i++) {
        $char = $input[$i];

        if (in_array($char, ['(', '[', '{'])) {
            $stack->push($char);
        } elseif (in_array($char, [')', ']', '}'])) {
            if ($stack->isEmpty()) return false;
            $top = $stack->pop();
            if ($pairs[$top] !== $char) return false;
        }
    }

    return $stack->isEmpty();
}

echo checkBrackets('(a + b) * [c - d]');  // true
echo checkBrackets('(a + b * [c - d)');   // false

// 目录路径解析
function resolvePath(string $path): string
{
    $parts = new Stack();
    foreach (explode('/', $path) as $part) {
        if ($part === '..') {
            if (!$parts->isEmpty()) $parts->pop();
        } elseif ($part !== '.' && $part !== '') {
            $parts->push($part);
        }
    }
    return '/' . implode('/', $parts->toArray());
}

echo resolvePath('a/b/../c/d/./e');  // /a/c/d/e

Queue 的高级用法

php

<?php

declare(strict_types=1);

use Ds\Queue;

// 广度优先搜索（BFS）
function bfs(array $graph, string $start): array
{
    $visited = [$start];
    $queue = new Queue([$start]);

    while (!$queue->isEmpty()) {
        $current = $queue->pop();
        foreach ($graph[$current] ?? [] as $neighbor) {
            if (!in_array($neighbor, $visited, true)) {
                $visited[] = $neighbor;
                $queue->push($neighbor);
            }
        }
    }

    return $visited;
}

$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D', 'E'],
    'C' => ['A', 'F'],
    'D' => ['B'],
    'E' => ['B', 'F'],
    'F' => ['C', 'E'],
];

print_r(bfs($graph, 'A'));
// ['A', 'B', 'C', 'D', 'E', 'F']

PriorityQueue 的自定义比较

php

<?php

declare(strict_types=1);

use Ds\PriorityQueue;

// 自定义任务优先级
class Task implements \Ds\Heapable
{
    public function __construct(
        public string $name,
        public int $priority,
        public string $createdAt
    ) {}

    public function compare(\Ds\Heapable $other): int
    {
        // 优先级数字小的先出
        return $this->priority <=> $other->priority;
    }
}

$queue = new PriorityQueue();
$queue->push(new Task('low', 10, '10:00'));
$queue->push(new Task('high', 1, '10:05'));
$queue->push(new Task('medium', 5, '10:02'));

while (!$queue->isEmpty()) {
    $task = $queue->pop();
    echo "[P{$task->priority}] {$task->name} ({$task->createdAt})\n";
}
// [P1] high (10:05)
// [P5] medium (10:02)
// [P10] low (10:00)

注意事项

Stack/Queue/Pair 不能索引访问

Stack、Queue 和 Pair 不支持数字索引访问。只能通过 push/pop、peek 等专用方法操作。

PriorityQueue 修改后重排

PriorityQueue 的 push 操作会触发内部堆重排（O(log n)）。大量频繁插入可能影响性能。

最佳实践

Stack 用于 LIFO 场景：撤销操作、括号匹配、DFS
Queue 用于 FIFO 场景：消息队列、BFS、任务调度
PriorityQueue 用于优先级调度：任务优先级、事件排序
Pair 作为 Map 遍历元素：foreach ($map as $pair)
isEmpty() 检查空状态：避免 pop 空 Stack/Queue 异常
peek 查看不移除：检查下一个元素而不弹出

Pair / Stack / Queue / PriorityQueue ​

概述 ​

基础概念 ​

数据结构对比 ​

语法与代码 ​

Pair — 键值对 ​

Stack — 栈（LIFO） ​

Queue — 队列（FIFO） ​

PriorityQueue — 优先级队列 ​

详细说明 ​

Stack 实现细节 ​

Queue 实现细节 ​

PriorityQueue 排序方式 ​

实战示例 ​

撤销/重做系统 ​

任务调度器 ​

消息队列（BFS 模式） ​

Pair 的高级用法 ​

Stack 的高级用法 ​

Queue 的高级用法 ​

PriorityQueue 的自定义比较 ​

注意事项 ​

最佳实践 ​

参考链接 ​