首頁  >  文章  >  後端開發  >  php實作佇列

php實作佇列

炎欲天舞
炎欲天舞原創
2018-05-10 14:28:3411351瀏覽

佇列(Queue): 滿足先進先出(FIFO)的規則;

下面使用php實作一個簡單的循環佇列模型;

初始狀態的佇列,佇列長度為0 ,隊頭和隊尾的指針相同均位於隊列的開始;

入隊操作:隊尾指針向後移動,長度加一;

出隊操作:隊頭指針向後移動,長度減一;

循環隊列特點:隊列大小固定,隊列所開闢的內存空間可循環使用,指針的移動是靠與queueSize取餘運算移動;

下面的例子是利用數組實現隊列存儲,數組下標作為指針;

<?php


/**
 * Class Queue
 */
class Queue
{
    /**
     * @var int 队头指针
     */
    private $_front;

    /**
     * @var int 队尾指针
     */
    private $_rear;

    /**
     * @var array 队列数组
     */
    private $_queue;

    /**
     * @var int 队列实际长度
     */
    private $_queueLength;

    /**
     * @var int 队列容量;
     */
    private $_queueSize;

    /**
     * Queue constructor.初始化队列
     * @param int $capacity 容量(循环队列的最大长度)
     */
    public function __construct($size)
    {
        $this->_queue = [];
        $this->_queueSize = $size;
        $this->_front = 0;
        $this->_rear = 0;
        $this->_queueLength = 0;
    }

    /**
     * 销毁队列;
     */
    public function __destruct()
    {
        unset($this->_queue);
    }

    /**
     * @method 入队
     * @param mixed $elem 入队的元素
     * @return bool
     */
    public function enQueue($elem)
    {
        if (!$this->isFull()) {
            $this->_queue[$this->_rear] = $elem;
            $this->_rear++;
            $this->_rear = $this->_rear % $this->_queueCapacity;
            $this->_queueLength++;
            return true;
        }
        return false;
    }

    /**
     * @method 出队
     * @return mixed|null
     */
    public function deQueue()
    {
        if (!$this->isEmpty()) {
            $elem = $this->_queue[$this->_front];
            //unset($this->_queue[$this->_front]);
            $this->_front++;
            $this->_front %= $this->_queueCapacity;
            $this->_queueLength--;
            return $elem;
        }
        return null;
    }

    /**
     * @method 判断队列是否为空;
     * @return bool
     */
    public function isEmpty()
    {
        return $this->_queueLength === 0;
    }

    /**
     * @method 判断队列是否饱和;
     * @return bool
     */
    public function isFull()
    {
        return $this->_queueLength === $this->_queueCapacity;
    }

    /**
     * @method 遍历队列并输出(测试队列)
     */
    public function outputQueue()
    {
        for ($i = $this->_front; $i < $this->_queueLength + $this->_front; $i++) {
            echo $this->_queue[$i % $this->_queueCapacity].PHP_EOL;
        }
    }

    /**
     * @method 清空队列
     */
    public function clearQueue()
    {
        $this->_queue = [];
        $this->_front = 0;
        $this->_rear = 0;
        $this->_queueLength = 0;
    }
}

測試隊列類,講道理是沒什麼大問題的,優化就靠真實的業務場景了;

$a = new Queue(3);
echo &#39;enQueue1 $a->enQueue(1)&#39;.PHP_EOL;
$a->enQueue(1);
echo &#39;enQueue2 $a->enQueue(2)&#39;.PHP_EOL;
$a->enQueue(2);
echo &#39;enQueue3 $a->enQueue(3)&#39;.PHP_EOL;
$a->enQueue(3);
echo &#39;enQueue4 $a->enQueue(4)&#39;.PHP_EOL;
$a->enQueue(4);     //讲道理是失败的;
$a->outputQueue();      //输出 1 2 3
echo PHP_EOL;
echo PHP_EOL;
echo $a->deQueue();     //输出 1  队列 2 3
echo PHP_EOL;
echo PHP_EOL;
echo $a->deQueue();     //输出 2  队列 3
$a->enQueue(5);         //队列 3 5
echo PHP_EOL;
echo PHP_EOL;
$a->outputQueue();      //输出 3 5
$a->clearQueue();       //队列空;

以上是php實作佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn