[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; } } ```