本文就是展示如何通过PHP语言实现一个带有尾指针的链表，然后通过链表实现队列。链表的头元素用于入队和出队。它的时间复杂度是O(1)。在头的基础上，链表尾部加入队列的时间为O(n)。为了降低入队操作的时间复杂度，可以为链表维护一个带有尾指针的变量tail，这样每次入队都可以直接操作尾，出队时直接操作head，这样入队和出队的时间复杂度都是O(1)。1.output_queue_by_liked_list.php这是一个演示打印输出结果的文件：enqueue("rr");//入队$queue->enqueue("tt");//加入$queue->enqueue("yy");//加入$queue->enqueue("uu");//加入$queue->enqueue("ii");//加入$queue->enqueue("oo");//加入echo$queue->toString();//打印rr->tt->yy->uu->ii->oo->nullecho"
";echo$queue->dequeue();//打印rrecho"
";echo$queue->dequeue();//打印ttecho"
";echo$queue->dequeue();//打印出yyecho"
";echo$queue->toString();//打印uu->ii->oo->nullecho"
";$queue->enqueue("11");//加入$queue->enqueue("22");//加入$queue->enqueue("33");//加入$queue->enqueue("44");//加入$queue->enqueue("55");//加入$queue->enqueue("66");//加入echo"
";echo$queue->toString();//打印uu->ii->oo->11->22->33->44->55->66->null3.QueueByLinkedList这是一个用尾指针链表实现的队列类，它有enqueue方法和dequque方法：head=null;$this->tail=null;$this->size=0;}/***入队操作*@param$e*/publicfunctionenqueue($e):void{if($this->tail==null){$this->tail=$this->head=newNode($e,null);}else{$node=newNode($e,null);$this->tail->next=$node;$this->tail=$node;}$this->size++;}/***出队操作*@returnmixed*/publicfunctiondequeue(){if($this->size==0){return"队列已经为空";}$node=$this->head;$this->head=$node->next;$这个->大小--;如果($node->next==null){$this->tail=null;}返回$node->e;}publicfunctiongetFront(){if($this->size==0){return"队列已经为空";}返回$this->head->e;}publicfunctiongetSize(){return$this->size;}/***判断队列是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->size==0;}publicfunctiontoString(){$str="";对于($node=$this->head;$node!=null;$node=$node->next){$str.=$node->e.“->”；}$海峡。=“空”；返回$str;}}类ssNode{public$e;//节点元素public$next;//下一个节点信息/***构造函数设置节点信息*节点构造函数。*@param$e*@param$next*/publicfunction__construct($e,$next){$this->e=$e;$this->next=$next;}}4.interfaceQueue这里是Queue类的实现接口，定义了一些函数。继承之后，必须重构里面的所有方法：endelementspublicfunctiongetSize();//获取队列大小publicfunctionisEmpty();//判断队列是否为空}代码仓库：https://gitee.com/love-for-po...扫一扫代码跟随爱世贤
