PHP小码农

Appearance

Deque ​

概述 ​

Ds\Deque（Double-Ended Queue，双端队列）是一种在两端都支持高效插入和删除的数据结构。与 Vector 相比，Deque 的首尾操作（push、pop、shift、unshift）都是 O(1) 时间复杂度，非常适合实现栈、队列和缓冲区等场景。

基础概念 ​

特性 ​

特性说明
双端操作push/pop/shift/unshift 都是 O(1)
有序元素按插入顺序排列
自动索引从 0 开始的整数索引
可遍历支持 foreach

时间复杂度对比 ​

操作DequeVector原生数组
末尾 push/popO(1)O(1)O(1)
首部 unshift/shiftO(1)O(n)O(n)
索引访问O(1)*O(1)O(1)

*Deque 在两端操作时最优，中间插入/删除仍为 O(n)。

语法与代码 ​

创建 Deque ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

// 从数组创建
$deque = new Deque([1, 2, 3]);

// 空双端队列
$empty = new Deque();

首尾操作（O(1)） ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

$deque = new Deque();

// push - 末尾追加
$deque->push('a', 'b', 'c');
// ['a', 'b', 'c']

// unshift - 开头插入
$deque->unshift('x', 'y');
// ['x', 'y', 'a', 'b', 'c']

// pop - 移除末尾
$deque->pop();  // 'c'
// ['x', 'y', 'a', 'b']

// shift - 移除开头
$deque->shift();  // 'x'
// ['y', 'a', 'b']

读写操作 ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

$deque = new Deque([10, 20, 30, 40, 50]);

// 索引访问
echo $deque->get(0);     // 10
echo $deque->get(-1);    // 50
echo $deque->first();    // 10
echo $deque->last();     // 50

// 修改
$deque->set(2, 99);
// [10, 20, 99, 40, 50]

// 查找
echo $deque->contains(30);  // false（已被修改为 99）
echo $deque->find(40);     // 3

// 统计
echo $deque->count();  // 5
echo $deque->isEmpty(); // false

函数式操作 ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

$deque = new Deque([1, 2, 3, 4, 5]);

// map
$doubled = $deque->map(fn(int $n): int => $n * 2);
// [2, 4, 6, 8, 10]

// filter
$gt3 = $deque->filter(fn(int $n): bool => $n > 3);
// [4, 5]

// reduce
$sum = $deque->reduce(fn(int $c, int $n): int => $c + $n, 0);
// 15

// sort / reverse
$sorted = $deque->copy()->sort();
$reversed = $deque->copy()->reverse();

详细说明 ​

Deque vs Vector vs 原生数组 ​

php
<?php

declare(strict_types=1);

// 首部操作性能对比
// 原生 array_unshift/array_shift 是 O(n)（需要重建索引）
// Deque 的 unshift/shift 是 O(1)

// 适合使用 Deque 的场景：
// 1. 消息队列
// 2. 滑动窗口
// 3. LRU 缓存
// 4. 任务调度

选择建议

需要频繁在首尾操作时使用 Deque。只需末尾操作时 Vector 更轻量。

实战示例 ​

实现栈（LIFO） ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

class Stack
{
    private Deque $deque;

    public function __construct()
    {
        $this->deque = new Deque();
    }

    public function push(mixed $value): void
    {
        $this->deque->push($value);
    }

    public function pop(): mixed
    {
        return $this->deque->pop();
    }

    public function peek(): mixed
    {
        return $this->deque->last();
    }

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

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

$stack = new Stack();
$stack->push('a');
$stack->push('b');
$stack->push('c');
echo $stack->pop();  // c
echo $stack->pop();  // b
echo $stack->peek(); // a

实现队列（FIFO） ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

class MessageQueue
{
    private Deque $deque;

    public function __construct()
    {
        $this->deque = new Deque();
    }

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

    public function dequeue(): string
    {
        return $this->deque->shift();
    }

    public function peek(): ?string
    {
        return $this->deque->isEmpty() ? null : $this->deque->first();
    }

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

$queue = new MessageQueue();
$queue->enqueue('task1');
$queue->enqueue('task2');
$queue->enqueue('task3');
echo $queue->dequeue();  // task1
echo $queue->dequeue();  // task2
echo $queue->peek();     // task3

滑动窗口 ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

function slidingMax(array $nums, int $k): array
{
    $deque = new Deque();
    $result = [];

    foreach ($nums as $i => $num) {
        // 移除窗口外的索引
        while (!$deque->isEmpty() && $deque->first() <= $i - $k) {
            $deque->shift();
        }
        // 移除比当前值小的索引
        while (!$deque->isEmpty() && $nums[$deque->last()] < $num) {
            $deque->pop();
        }
        $deque->push($i);
        if ($i >= $k - 1) {
            $result[] = $nums[$deque->first()];
        }
    }

    return $result;
}

print_r(slidingMax([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

Deque 的高级用法 ​

php
<?php

declare(strict_types=1);

use Ds\Deque;

// Deque 作为环形缓冲区
class CircularBuffer
{
    private Deque $buffer;
    private int $capacity;

    public function __construct(int $capacity)
    {
        $this->capacity = $capacity;
        $this->buffer = new Deque();
    }

    public function add(mixed $item): void
    {
        if ($this->buffer->count() >= $this->capacity) {
            $this->buffer->shift();
        }
        $this->buffer->push($item);
    }

    public function toArray(): array
    {
        return $this->buffer->toArray();
    }

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

$buffer = new CircularBuffer(3);
$buffer->add('a');
$buffer->add('b');
$buffer->add('c');
print_r($buffer->toArray()); // ['a', 'b', 'c']
$buffer->add('d');           // 溢出，移除 'a'
print_r($buffer->toArray()); // ['b', 'c', 'd']

Deque 与 Vector 的性能对比 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;
use Ds\Deque;

$n = 10000;

// 首部插入对比
$start = microtime(true);
$deque = new Deque();
for ($i = 0; $i < $n; $i++) {
    $deque->unshift($i);
}
$dequeTime = microtime(true) - $start;

$start = microtime(true);
$vector = new Vector();
for ($i = 0; $i < $n; $i++) {
    $vector->unshift($i);
}
$vectorTime = microtime(true) - $start;

echo "Deque unshift {$n} items: {$dequeTime}s\n";
echo "Vector unshift {$n} items: {$vectorTime}s\n";
// Deque 应该显著快于 Vector（O(1) vs O(n)）

Deque 使用建议

如果需要在数组两端频繁插入和删除，Deque 是最佳选择。Vector 在首部操作时需要移动所有元素，而 Deque 不需要。

注意事项 ​

中间操作性能

Deque 的中间插入 insert() 和删除 remove() 仍然是 O(n)。频繁的中间操作请考虑其他数据结构。

最佳实践 ​

  1. 首尾频繁操作用 Deque：替代 array_shift/array_unshift
  2. 实现栈用 push/pop：LIFO 场景
  3. 实现队列用 push/shift：FIFO 场景
  4. 滑动窗口用 Deque：高效的首尾操作
  5. 不需要序列化时直接使用：避免 toArray() 开销

参考链接 ​