[TOC] # 隊列 定義： * 隊列是一種線性結構，來自線性表數據結構，“操作受限”的線性表 * 是先進先出的線性表，隊列只允許在隊首出隊，隊尾入隊  # 隊列的類型 * 用數組實現 * 用鏈表實現 # 隊列的應用 ## 通過數組實現隊列 ~~~ class Queue { private $queue;//隊列 private $size;//隊列的長度 /** * 構造方法 */ public function __construct() { $this->queue = array(); $this->size = 0; } /** * 入隊操作 * @param $data 入隊數據 * @return object 返回對象本身 */ public function enqueue($data){ $this->queue[$this->size++] = $data; return $this; } /** * 出隊操作 * @return 空隊列時返回false，否則返回出隊元素 */ public function dequeue(){ if (!$this->isEmpty()){ --$this->size; return array_shift($this->queue); } return false; } /** * 獲取整個隊列 * @return array 返回整個隊列 */ public function getAllQueue(){ return $this->queue; } /** * 判斷隊列是否為空 * @return 為空返回true，否則返回false */ public function isEmpty(){ return 0===$this->size; } /** * 獲取隊頭元素 * @return 空隊列時返回false，否則返回隊頭元素 */ public function getFirst(){ if (!$this->isEmpty()){ return $this->queue[0]; } return false; } /** * 獲取隊列的長度 * @return 返回隊列的長度 */ public function getSize(){ return $this->size; } } ~~~ ## 循環隊列的使用 說明：上面定義的隊列，隊列元素出列以后，數組會重新排序，所有的元素向前移動一位，這樣時間復雜度是O(n)     代碼實現： ``` 需要注意是PHP中的數組沒有長度限制，比java中的數組高級多了 /** * 循環隊列，順序存儲 * Class LoopQueue */ class LoopQueue { public $data;//隊列 private $front;//頭元素指針 private $tail;//尾元素后一個位置指針 private $size;//隊列元素大小 const MAX = 8;//定義最大容量 public function __construct() { $this->data = array(); $this->front = 0; $this->tail = 0; $this->size = 0; } /** * 查看隊列長度 * @return int 返回隊列長度 */ public function queueLength(){ //return ($this->tail - $this->front + self::MAX)%self::MAX; return $this->size; } /** * 入隊列 * @param $e 入隊列的元素 * @return 如果隊列已滿，返回false，如果入隊成功，返回入隊元素 */ public function enQueue($e){ //查看隊列是否已滿 if (($this->tail + 1)%self::MAX == $this->front){ return false; } $this->data[$this->tail] = $e; $this->tail = ($this->tail + 1)%self::MAX; $this->size++; return $e; } /** * 出隊 * @return bool|mixed 隊列為空，返回false；出隊成功，返回出隊元素 */ public function deQueue(){ //判斷隊列是否為空 if ($this->tail == $this->front){ return false; } $e = $this->data[$this->front]; // $this->data[$this->front] = null; unset($this->data[$this->front]); $this->front = ($this->front + 1)%self::MAX; $this->size--; return $e; } } ```