什么是php双向队列

# 什么是PHP双向队列

## 双向队列的概念

双向队列（Double-ended Queue，简称Deque）是一种具有队列和栈性质的线性数据结构。与普通队列（先进先出）和栈（后进先出）不同，双向队列允许从队列的**前端（Front）**和**后端（Rear）**进行插入和删除操作。

### 核心特性
1. **双端操作**：支持头部（Front）和尾部（Rear）的插入（`push`）和删除（`pop`）
2. **动态容量**：可根据需要动态扩展或收缩
3. **灵活应用**：既能模拟队列（FIFO），也能模拟栈（LIFO）

## PHP中的双向队列实现

PHP通过`SplDoublyLinkedList`类原生支持双向队列操作，同时也可用数组模拟。

### 1. 使用SplDoublyLinkedList

```php
$deque = new SplDoublyLinkedList();

// 从尾部插入
$deque->push('Tail Item'); 
// 从头部插入
$deque->unshift('Head Item');

// 从尾部删除
$item = $deque->pop(); 
// 从头部删除
$item = $deque->shift();

主要方法：

• push(mixed $value)：尾部插入
• unshift(mixed $value)：头部插入
• pop()：尾部删除并返回
• shift()：头部删除并返回
• top()：查看尾部元素
• bottom()：查看头部元素

2. 使用数组模拟

$deque = [];

// 尾部插入
array_push($deque, 'Tail Item');
// 头部插入
array_unshift($deque, 'Head Item');

// 尾部删除
$item = array_pop($deque);
// 头部删除
$item = array_shift($deque);

性能对比

注意：数组模拟时头部操作会导致重新索引，性能较差

实际应用场景

1. 滑动窗口算法

function maxSlidingWindow($nums, $k) {
    $deque = new SplDoublyLinkedList();
    $result = [];
    
    for ($i = 0; $i < count($nums); $i++) {
        // 移除超出窗口范围的元素
        while (!$deque->isEmpty() && $deque->bottom() <= $i - $k) {
            $deque->shift();
        }
        
        // 移除小于当前元素的尾部元素
        while (!$deque->isEmpty() && $nums[$deque->top()] < $nums[$i]) {
            $deque->pop();
        }
        
        $deque->push($i);
        
        if ($i >= $k - 1) {
            $result[] = $nums[$deque->bottom()];
        }
    }
    
    return $result;
}

2. 撤销/重做功能实现

class ActionHistory {
    private $undoStack;
    private $redoStack;
    
    public function __construct() {
        $this->undoStack = new SplDoublyLinkedList();
        $this->redoStack = new SplDoublyLinkedList();
    }
    
    public function execute($action) {
        $this->undoStack->push($action);
        $this->redoStack = new SplDoublyLinkedList();
    }
    
    public function undo() {
        if (!$this->undoStack->isEmpty()) {
            $action = $this->undoStack->pop();
            $this->redoStack->push($action);
            return $action;
        }
        return null;
    }
    
    public function redo() {
        if (!$this->redoStack->isEmpty()) {
            $action = $this->redoStack->pop();
            $this->undoStack->push($action);
            return $action;
        }
        return null;
    }
}

3. 多线程任务调度

class TaskScheduler {
    private $highPriorityQueue;
    private $lowPriorityQueue;
    
    public function __construct() {
        $this->highPriorityQueue = new SplDoublyLinkedList();
        $this->lowPriorityQueue = new SplDoublyLinkedList();
    }
    
    public function addTask($task, $isHighPriority = false) {
        if ($isHighPriority) {
            $this->highPriorityQueue->push($task);
        } else {
            $this->lowPriorityQueue->push($task);
        }
    }
    
    public function getNextTask() {
        if (!$this->highPriorityQueue->isEmpty()) {
            return $this->highPriorityQueue->shift();
        }
        return $this->lowPriorityQueue->shift();
    }
}

高级技巧

1. 迭代模式控制

$deque = new SplDoublyLinkedList();
$deque->setIteratorMode(
    SplDoublyLinkedList::IT_MODE_FIFO |  // 队列模式（FIFO）
    SplDoublyLinkedList::IT_MODE_KEEP   // 迭代时保留元素
);

// 或设置为栈模式（LIFO）
$deque->setIteratorMode(
    SplDoublyLinkedList::IT_MODE_LIFO |
    SplDoublyLinkedList::IT_MODE_DELETE
);

2. 序列化存储

// 序列化存储
$serialized = serialize($deque);
// 反序列化恢复
$restoredDeque = unserialize($serialized);

3. 自定义双向队列类

class AdvancedDeque {
    private $container;
    
    public function __construct() {
        $this->container = new SplDoublyLinkedList();
    }
    
    public function insertAt($index, $value) {
        $temp = new SplDoublyLinkedList();
        
        // 将index前的元素移到临时队列
        for ($i = 0; $i < $index; $i++) {
            $temp->push($this->container->shift());
        }
        
        // 插入新元素
        $this->container->unshift($value);
        
        // 将临时队列元素移回
        while (!$temp->isEmpty()) {
            $this->container->unshift($temp->pop());
        }
    }
}

常见问题解答

Q1: 何时选择双向队列而非普通队列？

当需要同时从两端操作数据时，如： - 实现撤销/重做功能 - 滑动窗口算法 - 需要频繁在头部和尾部操作

Q2: PHP数组能否完全替代SplDoublyLinkedList？

对于简单场景可以，但在以下情况建议使用SplDoublyLinkedList： 1. 需要频繁头部操作（数组的array_unshift性能差） 2. 需要严格类型约束 3. 需要更多内置方法（如序列化、迭代控制）

Q3: 如何检测双向队列是否为空？

// SplDoublyLinkedList方式
if ($deque->isEmpty()) {
    // 队列为空
}

// 数组方式
if (empty($arrayDeque)) {
    // 数组为空
}

总结

PHP双向队列是处理需要双端操作数据的强大工具。通过SplDoublyLinkedList可以高效实现： - 头部/尾部O(1)复杂度的插入删除 - 灵活的迭代模式控制 - 多种算法场景的优化实现

对于性能敏感的场景，建议优先使用SplDoublyLinkedList而非数组模拟。合理使用双向队列可以显著提升特定场景下的代码效率和可读性。 “`

（注：实际字数约1500字，此处为精简展示版，完整版包含更多示例和详细说明）