php实现环形队列

PHP实现环形队列的方法

环形队列是一种特殊的队列数据结构，它通过固定大小的数组实现，利用模运算实现循环利用空间。以下是PHP实现环形队列的几种方法：

使用数组和指针实现

通过维护队首(front)和队尾(rear)指针以及当前元素数量(count)来实现环形队列：

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

    public function __construct($capacity) {
        $this->queue = array_fill(0, $capacity, null);
        $this->capacity = $capacity;
        $this->front = 0;
        $this->rear = -1;
        $this->count = 0;
    }

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

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

    public function peek() {
        if ($this->isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return $this->queue[$this->front];
    }

    public function isEmpty() {
        return $this->count == 0;
    }

    public function isFull() {
        return $this->count == $this->capacity;
    }

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

使用SplFixedArray优化性能

对于需要更高性能的场景，可以使用SplFixedArray代替普通数组：

class CircularQueueSpl {
    private $queue;
    private $capacity;
    private $front = 0;
    private $rear = -1;
    private $count = 0;

    public function __construct($capacity) {
        $this->queue = new SplFixedArray($capacity);
        $this->capacity = $capacity;
    }

    // 其他方法与前面示例类似
    // ...
}

实现环形缓冲区的变体

对于需要覆盖旧数据的场景，可以修改enqueue方法实现自动覆盖：

public function enqueue($item) {
    $this->rear = ($this->rear + 1) % $this->capacity;
    $this->queue[$this->rear] = $item;
    if ($this->count < $this->capacity) {
        $this->count++;
    } else {
        $this->front = ($this->front + 1) % $this->capacity;
    }
}

使用位运算优化模运算

当队列容量为2的幂次方时，可以使用位运算代替模运算提高性能：

public function __construct($capacity) {
    if (($capacity & ($capacity - 1)) != 0) {
        throw new InvalidArgumentException("Capacity must be a power of 2");
    }
    $this->queue = array_fill(0, $capacity, null);
    $this->capacity = $capacity;
    $this->mask = $capacity - 1;
}

public function enqueue($item) {
    if ($this->isFull()) {
        throw new RuntimeException("Queue is full");
    }
    $this->rear = ($this->rear + 1) & $this->mask;
    $this->queue[$this->rear] = $item;
    $this->count++;
}

以上实现提供了环形队列的基本功能，可以根据具体需求进行扩展和优化。实际应用中，环形队列常用于需要固定大小缓冲区的场景，如音频处理、网络数据包缓冲等。