这篇文章是展现通过 PHP 语言实现一种带尾指针的链表，而后通过链表来实现队列，其中链表的头元素 head 是用于列队出队的，它的工夫复杂度 O(1)，若在 head 的根底上实现链表尾部入队工夫度为 O(n)，为了升高入队操作的工夫复杂度，能够给链表保护一个带有尾指针的变量 tail，这样每次入队的时候间接操作 tail，出队的时候间接操作 head，这样能够使得 入队和出队 工夫复杂度都是 O(1)。

1.output_queue_by_liked_list.php

这是一个演示打印输出后果的文件：

<?phprequire 'QueueByLinkedList.php';$queue = new QueueByLinkedList();$queue->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 "<br>";echo $queue->dequeue();  //出队 打印  rrecho "<br>";echo $queue->dequeue();  //出队 打印  ttecho "<br>";echo $queue->dequeue();  //出队 打印  yyecho "<br>";echo $queue->toString(); //打印 uu->ii->oo->nullecho "<br>";$queue->enqueue("11"); //入队$queue->enqueue("22"); //入队$queue->enqueue("33"); //入队$queue->enqueue("44"); //入队$queue->enqueue("55"); //入队$queue->enqueue("66"); //入队echo "<br>";echo $queue->toString(); //打印 uu->ii->oo->11->22->33->44->55->66->null

3.QueueByLinkedList 类

这是通过带尾指针链表实现的 队列 类，它外面有 入队(enqueue) 办法和 出队(dequque) 办法 :

<?phprequire 'Queue.php';/** * 带有尾指针的链表 * Class LinkedListTail */class QueueByLinkedList implements Queue{    private $head; //链表头部    private $tail; //链表尾部    private $size; //链表大小    /**     * 构造函数 初始化链表     * QueueByLinkedList constructor.     */    public function __construct() {        $this->head = null;        $this->tail = null;        $this->size = 0;    }    /**     * 入队操作     * @param $e     */    public function enqueue($e): void {        if ($this->tail == null) {            $this->tail = $this->head = new Node($e, null);        } else {            $node = new Node($e, null);            $this->tail->next = $node;            $this->tail = $node;        }        $this->size++;    }    /**     * 出队操作     * @return mixed     */    public function dequeue() {        if ($this->size == 0) {            return "队列曾经是空的";        }        $node = $this->head;        $this->head = $node->next;        $this->size--;        if ($node->next == null) {            $this->tail = null;        }        return $node->e;    }    public function getFront() {        if ($this->size == 0) {            return "队列曾经是空的";        }        return $this->head->e;    }    public function getSize() {        return $this->size;    }    /**     * 判断队列是否为空     * @return bool     */    public function isEmpty(): bool {        return $this->size == 0;    }    public function toString() {        $str = "";        for ($node = $this->head; $node != null; $node = $node->next) {            $str .= $node->e . "->";        }        $str .= "null";        return $str;    }}class Node{    public $e;//节点元素    public $next; //下个节点信息    /**     * 构造函数 设置节点信息     * Node constructor.     * @param $e     * @param $next     */    public function __construct($e, $next) {        $this->e = $e;        $this->next = $next;    }}

4.interface Queue

这里是 队列 类一个实现接口，外面定义了一些函数，继承它之后，必须重构外面的所有办法：

<?phpinterface Queue{    public function enqueue($e): void;//入队    public function dequeue();//出队    public function getFront();//获取前端元素    public function getSize();//获取队列大小    public function isEmpty();//判断队列是否为空}