当前位置：首页 > PHP

php环行队列实现

2026-02-16 03:00:15PHP

环形队列的实现原理

环形队列（Circular Queue）是一种基于数组的先进先出（FIFO）数据结构，通过维护头尾指针实现循环利用空间。当尾部到达数组末尾时，会绕回到数组开头，避免普通队列的假溢出问题。

环形队列的关键操作

初始化
定义队列大小、头指针（front）、尾指针（rear）和存储数组。初始时 front 和 rear 均为 0。

入队（enqueue）
检查队列是否已满，若未满则将元素放入 rear 位置，并更新 rear = (rear + 1) % capacity。

出队（dequeue）
检查队列是否为空，若不为空则取出 front 位置的元素，并更新 front = (front + 1) % capacity。

判空与判满

空队列条件：front == rear
满队列条件：(rear + 1) % capacity == front（需预留一个空位避免歧义）

PHP 实现代码示例

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

    public function __construct($size) {
        $this->capacity = $size + 1; // 预留一个空位
        $this->queue = array_fill(0, $this->capacity, null);
        $this->front = $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;
    }
}

// 使用示例
$queue = new CircularQueue(3);
$queue->enqueue(1);
$queue->enqueue(2);
echo $queue->dequeue(); // 输出 1
$queue->enqueue(3);