什么是队列？队列是另一种遵循先进先出原则的线性数据结构。队列有两端进行操作，一端出队，一端入队。此功能不同于堆栈，其中只能使用一端进行操作。入队总是在后端，出队总是在前端。常用操作enqueue->enqueuedequeue->peekoutofqueue->返回队列前端元素isEmpty->是否为空PHP实现首先我们定义一个QueueInterface。interfaceQueueInterface{publicfunctionenqueue(string$item);公共函数出队（）；公共功能是空的（）；publicfunctionpeek();}来看看基于数组的队列实现classArrQueueimplementsQueueInterface{private$queue;私人$限额；公共函数__construct(int$limit=0){$this->limit=$limit;$this->queue=[];}publicfunctionisEmpty(){returnempty($this->queue);}publicfunctiondequeue(){if($this->isEmpty()){thrownew\UnderflowException('queueisempty');}else{array_shift($this->queue);}}publicfunctionenqueue(string$item){if(count($this->queue)>=$this->limit){thrownew\OverflowException('queueisfull');}else{array_unshift($this->queue,$item);}}publicfunctionpeek(){returncurrent($this->queue);}}得益由于PHP强大的数组结构，我们很容易就写出了队列的基本操作方法。果然，世界上最好的语言名副其实。机智的同学可能已经猜到了。之前定义了一个queue接口，所以queue的实现肯定不止上面一个。下面看一下基于链表的实现。类LinkedListQueue实现QueueInterface{private$limit;私人$队列；公共函数__construct(int$limit=0){$this->limit=$limit;$this->queue=newLinkedList();}publicfunctionisEmpty(){return$this->queue->getSize()==0;}publicfunctionpeek(){return$this->queue->getNthNode(0)->data;}publicfunctionenqueue(string$item){if($this->queue->getSize()<$this->limit){$this->queue->insert($item);}else{thrownew\OverflowException('队列已满');}}publicfunctiondequeue(){if($this->isEmpty()){thrownew\UnderflowException('队列为空');}else{$lastItem=$this->peek();$this->queue->deleteFirst();返回$lastItem；}}}涉及到前面链表的实现。不了解详情的同学可以去这里看看。Spl中的Queue强大的PHP已经内置了queue的实现，可以使用的方法和我们上面自己的实现类似。类SqlQueue{私人$splQueue;公共函数__construct(){$this->splQueue=new\SplQueue();}publicfunctionenqueue(string$data=null){$this->splQueue->enqueue($data);}publicfunctiondequeue(){return$this->splQueue->dequeue();}}优先级队列优先级队列是一种特殊的队列，入队或出队的顺序是根据每个节点的权重来确定的。顺序优先队列可以分为有序优先队列和无序优先队列。有序优先级队列有两种情况，逆序或者顺序。在sequential序列中，我们可以快速找到优先级最大或最小的节点，复杂度为O(1)。但是插入会花费更多的时间，因为我们要检查每个节点的优先级并将其插入到合适的位置。无序序列在无序序列中，我们插入新节点时不需要根据它们的优先级来确定位置。进入队列时，像普通队列一样插入到队列尾部。但是当我们想要移除优先级最高的元素时，我们必须扫描每个节点来确定优先级最高的那个。接下来，我们还是实现一个基于链表的顺序优先队列。类LinkedListPriorityQueue{private$limit;私人$队列；公共函数__construct(int$limit=0){$this->limit=$limit;$this->queue=newLinkedList();}publicfunctionenqueue(string$data=null,int$priority){if($this->queue->getSize()>$this->limit){thrownew\OverflowException('队列已满');}else{$this->queue->insert($data,$priority);}}publicfunctiondequeue():string{if($this->isEmpty()){thrownew\UnderflowException('队列为空');}else{$item=$this->peek();$this->queue->deleteFirst();返回$item->data;}}publicfunctionpeek(){return$this->queue->getNthNode(0);}publicfunctionisEmpty(){return$this->queue->getSize()===0;}}环形队列为充分利使用向空间，克服"假涌出"现形象的做法是：把向量空间想象成一个首尾相接的环，把这种向量称为循环队列，存放向量的队列称为循环队列。循环队列也是数组的一种，只是逻辑上把数组的头和尾连接起来，形成一个循环队列。当数组尾满时，需要判断数组头部是否为空，不为空则继续存储数据。类CircularQueue实现QueueInterface{private$queue;私人$限额；私人$前=0;私人$rear=0;公共函数__construct(int$limit=0){$this->limit=$limit;$this->queue=[];}publicfunctionisEmpty(){return$this->front===$this->rear;}publicfunctionisFull(){$diff=$this->rear-$this->front;如果($diff==-1||$diff==($this->limit-1)){returntrue;}返回假；}publicfunctionpeek(){return$this->queue[$this->front];}publicfunctiondequeue(){if($this->isEmpty()){thrownew\UnderflowException('队列为空');$item=$this->queue[$this->front];$this->queue[$this->front]=null;$this->front=($this->front+1)%$this->limit;返回$项目；}公共functionenqueue(string$item){if($this->isFull()){thrownew\OverflowException('队列已满');$this->queue[$this->rear]=$item;$this->rear=($this->rear+1)%$this->limit;}}双端队列到目前为止，我们实现的队列都是在尾部（rear）入队，在前部（front）出队，特殊情况下，我们希望队头和队尾都可以进入或退出队伍。这种结构称为双端队列。基于我们之前实现的链表结构，我们可以很容易的实现这样的结构。类LinkedListDeQueue{private$limit=0;私人$队列；公共函数__construct(int$limit=0){$this->limit=$limit;$this->queue=new\DataStructure\LinkedList\LinkedList();}publicfunctiondequeueFromFront():string{if($this->isEmpty()){thrownew\UnderflowException('队列为空');}$item=$this->queue->getNthNode(0);$this->queue->deleteFirst();返回$item->data;}publicfunctiondequeueFromBack():string{if($this->isEmpty()){thrownew\UnderflowException('队列为空');$item=$this->queue->getNthNode($this->queue->getSize()-1);$this->queue->deleteLast();返回$item->data;}publicfunctionisFull(){return$this->queue->getSize()>=$this->limit;}公共函数enqueueAtBack(string$data=null){if($this->isFull()){thrownew\OverflowException('队列已满');}$this->queue->insert($data);}publicfunctionenqueueAtFront(string$data=null){if($this->isFull()){thrownew\OverflowException('queueisfull');}$this->queue->insertAtFirst($data);}publicfunctionisEmpty(){return$this->queue->getSize()===0;}publicfunctionpeekFront(){return$this->queue->getNthNode(0)->data;}publicfunctionpeekBack(){return$this->queue->getNthNode($this->queue->getSize()-1)->data;}}里面涉及到前面链表的实现，不了解细节的同学可以去这里看总结栈和队列是我们最常用的数据结构，我们会在其他地方看到这两种抽象数据类型的应用复杂的数据结构。在下一章中，我们将继续学习PHP数据结构的递归，递归是一种将复杂问题简单化的常用方法。专题系列PHP基础数据结构专题系列目录地址：地址主要用PHP语法总结基本数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中规范、部署、优化的一些实用建议，以及对Javascript语言特性的深入研究。
