PHP如何通过带尾指针的链表实现'队列'

这篇文章是展示通过 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

2.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;}}

3.interface Queue

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

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

以上就是PHP如何通过带尾指针的链表实现\’队列\’的详细内容，更多关于PHP 实现队列的资料请关注脚本之家其它相关文章！

您可能感兴趣的文章: