佇列(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 'enQueue1 $a->enQueue(1)'.PHP_EOL; $a->enQueue(1); echo 'enQueue2 $a->enQueue(2)'.PHP_EOL; $a->enQueue(2); echo 'enQueue3 $a->enQueue(3)'.PHP_EOL; $a->enQueue(3); echo 'enQueue4 $a->enQueue(4)'.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中文網其他相關文章!