数据结构之队列

介绍

队列是一个有序队列,可以用数组或是链表实现.

遵循先入先出的原则,即:先存入队列的数据,要先取出,后存入的要后取出.

数组模拟队列

1. 需要一个最大容量maxSize.

2. 定义两个变量front和rear,front会随着数据输出而改变,rear会随着数据输入而改变.

将数据存入队列

1. 将尾部指针往后移:$rear+1,放$rear == $front 队列为空;

2. 若尾部指针rear小于队列的最大小标maxSize-1,则将数据存入rear所指的数组元素中.rear == maxSize-1 队列满.

代码实现:

<?php

class ArrayQueue
{
    protected $maxSize;
    protected $front;
    protected $rear;
       
    //初始化   
    public function __construct($maxSize)
    {
        $this->maxSize = $maxSize;
        $this->front = -1;
        $this->rear = -1;
        $this->arr = [];
    }
    
    //显示队列数据
    public function showQueue()
    {
        for ($i = $this->front + 1; $i <= $this->rear; $i++) {
            echo $this->arr[$i].' ';
        }
    }

    //插入数据
    public function push($value)
    {
        if ($this->isFull()) {
            throw new \Exception('队列已满');
        }
        $this->rear++;
        $this->arr[$this->rear] = $value;
    }

    //弹出数据
    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \Exception('队列为空');
        }
        $this->front++;
    }
    
    //判断队列是否为空
    public function isEmpty()
    {
        return $this->front == $this->rear;
    }
    
    //判断队列是否已满
    public function isFull()
    {
        return $this->rear == $this->maxSize - 1;
    }
}

$arr = new ArrayQueue(10);
$arr->push(2);
$arr->push(2);
$arr->push(2);
$arr->push(2);
$arr->pop();
$arr->showQueue();

---

上述的队列是有缺陷的,当队列满后弹出数据,无法再插入数据,所以做一个环形的队列来完善功能.

数组模拟环形队列

思路:

1. rear指向队列尾部的后一个位置,预留一个空间作为约定;

2. front指向队列的头部;

3. 当rear=front时,队列为空;

4. 当front == (rear+1) % maxSize时,队列满;

5. 队列长度为:(rear+maxSize-front)%maxSize;

class CircleArray
{
    protected $maxSize;
    protected $front;
    protected $rear;
    //rear指向最有一个元素的后一个元素
    //front指向第一个元素
    //如果rear=front则队列为空
    //如果(rear+1)%maxSize=front则队列满
    //队列的长度(rear+maxSize-front)%maxSize
    public function __construct($maxSize)
    {
        $this->maxSize = $maxSize;
        $this->front = 0;
        $this->rear = 0;
        $this->arr = [];
    }
    
    //显示队列数据
    public function showQueue()
    {
        if ($this->isEmpty()) {
            throw new \Exception('队列为空');
        }
        for ($i = $this->front; $i <= $this->length(); $i++) {
            echo $this->arr[$i % $this->maxSize] . ' ';
        }
    }
    
    //插入数据
    public function push($value)
    {
        if ($this->isFull()) {
            throw new \Exception('队列已满');
        }
        $this->arr[$this->rear] = $value;
        $this->rear = ($this->rear + 1) % $this->maxSize;
    }

    //弹出数据
    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \Exception('队列为空');
        }
        $this->front = ($this->front + 1) % $this->maxSize;
    }
    
    //判断队列是否为空
    public function isEmpty()
    {
        return $this->front == $this->rear;
    }
    
    //判断队列是否已满
    public function isFull()
    {
        return ($this->rear + 1) % $this->maxSize == $this->front;
    }
    
    //计算队列的长度
    public function length()
    {
        return ($this->rear + $this->maxSize - $this->front) % $this->maxSize;
    }
}

$arr = new CircleArray(5);
$arr->push(2);
$arr->push(2);
$arr->push(2);
$arr->push(2);
$arr->pop();
$arr->push(2);

$arr->showQueue();