当前位置：首页 > PHP

PHP 实现循环队列

2026-02-15 08:59:15PHP

循环队列的概念

循环队列是一种线性数据结构，通过数组实现，利用头尾指针的循环移动来避免数据搬移，提高空间利用率。当队列尾部到达数组末尾时，会从数组头部重新开始存储。

PHP 实现循环队列

PHP 实现循环队列的关键点

使用固定大小的数组存储元素。
维护两个指针 front 和 rear，分别指向队首和队尾。
通过取模运算实现指针的循环移动。
区分队列满和队列空的条件。

代码实现

class CircularQueue {
    private $queue;
    private $front;
    private $rear;
    private $capacity;

    public function __construct($capacity) {
        $this->capacity = $capacity + 1; // 预留一个空位用于区分满和空
        $this->queue = array_fill(0, $this->capacity, null);
        $this->front = 0;
        $this->rear = 0;
    }

    // 入队
    public function enqueue($item) {
        if ($this->isFull()) {
            throw new RuntimeException("Queue is full");
        }
        $this->queue[$this->rear] = $item;
        $this->rear = ($this->rear + 1) % $this->capacity;
    }

    // 出队
    public function dequeue() {
        if ($this->isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        $item = $this->queue[$this->front];
        $this->front = ($this->front + 1) % $this->capacity;
        return $item;
    }

    // 检查队列是否为空
    public function isEmpty() {
        return $this->front == $this->rear;
    }

    // 检查队列是否已满
    public function isFull() {
        return ($this->rear + 1) % $this->capacity == $this->front;
    }

    // 获取队首元素
    public function peek() {
        if ($this->isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return $this->queue[$this->front];
    }

    // 获取队列大小
    public function size() {
        return ($this->rear - $this->front + $this->capacity) % $this->capacity;
    }
}

使用示例

$queue = new CircularQueue(3);
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
echo $queue->dequeue(); // 输出 1
$queue->enqueue(4);
echo $queue->size();    // 输出 3