从原理到代码：PHP中两个堆栈如何完美模拟队列？一文搞懂！

云游道人 2025-04-10 515 阅读 0评论

队列和堆栈是计算机科学中最基本的数据结构之一。队列遵循先进先出(FIFO)原则，而堆栈遵循后进先出(LIFO)原则。有趣的是，我们可以使用两个堆栈来模拟队列的行为。本文将详细介绍如何在PHP中实现这一概念。

理解基本概念

什么是队列？

队列是一种线性数据结构，按照先进先出的原则操作。常见的操作包括：

enqueue：在队列末尾添加元素
dequeue：移除队列前端的元素
peek：查看队列前端的元素而不移除它

什么是堆栈？

堆栈是另一种线性数据结构，但遵循后进先出的原则。主要操作包括：

push：在堆栈顶部添加元素
pop：移除堆栈顶部的元素
peek：查看堆栈顶部的元素而不移除它

两个堆栈实现队列的原理

使用两个堆栈(S1和S2)实现队列的核心思想是：

enqueue操作：直接将元素推入S1
dequeue操作：

如果S2不为空，从S2弹出元素
如果S2为空，将S1中的所有元素逐个弹出并推入S2，然后从S2弹出元素

这种方法确保了最先进入的元素会位于S2的顶部，从而实现了FIFO行为。

PHP实现

class QueueWithTwoStacks {
    private $stack1;
    private $stack2;
    
    publicfunction __construct() {
        $this->stack1 = new SplStack();
        $this->stack2 = new SplStack();
    }
    
    // 入队操作
    publicfunction enqueue($item) {
        $this->stack1->push($item);
    }
    
    // 出队操作
    publicfunction dequeue() {
        if ($this->stack2->isEmpty()) {
            while (!$this->stack1->isEmpty()) {
                $this->stack2->push($this->stack1->pop());
            }
        }
        
        if ($this->stack2->isEmpty()) {
            thrownew RuntimeException("Queue is empty");
        }
        
        return$this->stack2->pop();
    }
    
    // 查看队首元素
    publicfunction peek() {
        if ($this->stack2->isEmpty()) {
            while (!$this->stack1->isEmpty()) {
                $this->stack2->push($this->stack1->pop());
            }
        }
        
        if ($this->stack2->isEmpty()) {
            thrownew RuntimeException("Queue is empty");
        }
        
        return$this->stack2->top();
    }
    
    // 检查队列是否为空
    publicfunction isEmpty() {
        return$this->stack1->isEmpty() && $this->stack2->isEmpty();
    }
}

使用示例

$queue = new QueueWithTwoStacks();

// 入队操作
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);

echo $queue->dequeue(); // 输出1
echo $queue->dequeue(); // 输出2

$queue->enqueue(4);

echo $queue->dequeue(); // 输出3
echo $queue->dequeue(); // 输出4