这篇文章是展示通过 PHP 语言实现一种带 尾指针 的链表，然后通过链表来实现队列，其中链表的头元素 head 是用于列队 出队 的，它的时间复杂度 O(1) ，若在 head 的基础上实现链表尾部 入队 时间度为 O(n)，为了降低入队操作的时间复杂度，可以给链表维护一个带有尾指针的变量 tail ，这样每次入队的时候直接操作 tail ，出队的时候直接操作 head ，这样可以使得 入队 和 出队 时间复杂度都是 O(1)。

1.output_queue_by_liked_list.php

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

1. <?php 
2. require 'QueueByLinkedList.php'; 
3. $queue = new QueueByLinkedList(); 
4. $queue->enqueue("rr"); //入队 
5. $queue->enqueue("tt"); //入队 
6. $queue->enqueue("yy"); //入队 
7. $queue->enqueue("uu"); //入队 
8. $queue->enqueue("ii"); //入队 
9. $queue->enqueue("oo"); //入队 
10. echo $queue->toString(); //打印 rr->tt->yy->uu->ii->oo->null 
11. echo "<br>"; 
12. echo $queue->dequeue(); //出队 打印 rr 
13. echo "<br>"; 
14. echo $queue->dequeue(); //出队 打印 tt 
15. echo "<br>"; 
16. echo $queue->dequeue(); //出队 打印 yy 
17. echo "<br>"; 
18. echo $queue->toString(); //打印 uu->ii->oo->null 
19. echo "<br>"; 
20. $queue->enqueue("11"); //入队 
21. $queue->enqueue("22"); //入队 
22. $queue->enqueue("33"); //入队 
23. $queue->enqueue("44"); //入队 
24. $queue->enqueue("55"); //入队 
25. $queue->enqueue("66"); //入队 
26. echo "<br>"; 
27. echo $queue->toString(); //打印 uu->ii->oo->11->22->33->44->55->66->null 

2.QueueByLinkedList 类

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

1. <?php 
2. require 'Queue.php'; 
3. /** 
4.  * 带有尾指针的链表 
5.  * Class LinkedListTail 
6.  */ 
7. class QueueByLinkedList implements Queue 
8. { 
9.   private $head; //链表头部 
10.   private $tail; //链表尾部 
11.   private $size; //链表大小 
12.   /** 
13.    * 构造函数 初始化链表 
14.    * QueueByLinkedList constructor. 
15.    */ 
16.   public function __construct() { 
17.     $this->head = null; 
18.     $this->tail = null; 
19.     $this->size = 0; 
20.   } 
21.   /** 
22.    * 入队操作 
23.    * @param $e 
24.    */ 
25.   public function enqueue($e): void { 
26.     if ($this->tail == null) { 
27.       $this->tail = $this->head = new Node($e, null); 
28.     } else { 
29.       $node = new Node($e, null); 
30.       $this->tail->next = $node; 
31.       $this->tail = $node; 
32.     } 
33.     $this->size++; 
34.   } 
35.   /** 
36.    * 出队操作 
37.    * @return mixed 
38.    */ 
39.   public function dequeue() { 
40.     if ($this->size == 0) { 
41.       return "队列已经是空的"; 
42.     } 
43.     $node = $this->head; 
44.     $this->head = $node->next; 
45.     $this->size--; 
46.     if ($node->next == null) { 
47.       $this->tail = null; 
48.     } 
49.     return $node->e; 
50.   } 
51.   public function getFront() { 
52.     if ($this->size == 0) { 
53.       return "队列已经是空的"; 
54.     } 
55.     return $this->head->e; 
56.   } 
57.   public function getSize() { 
58.     return $this->size; 
59.   } 
60.   /** 
61.    * 判断队列是否为空 
62.    * @return bool 
63.    */ 
64.   public function isEmpty(): bool { 
65.     return $this->size == 0; 
66.   } 
67.   public function toString() { 
68.     $str = ""; 
69.     for ($node = $this->head; $node != null; $node = $node->next) { 
70.       $str .= $node->e . "->"; 
71.     } 
72.     $str .= "null"; 
73.     return $str; 
74.   } 
75. } 
76. class Node 
77. { 
78.   public $e;//节点元素 
79.   public $next; //下个节点信息 
80.   /** 
81.    * 构造函数 设置节点信息 
82.    * Node constructor. 
83.    * @param $e 
84.    * @param $next 
85.    */ 
86.   public function __construct($e, $next) { 
87.     $this->e = $e; 
88.     $this->next = $next; 
89.   } 
90. } 

3.interface Queue

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

1. <?php 
2. interface Queue 
3. { 
4.   public function enqueue($e): void;//入队 
5.   public function dequeue();//出队 
6.   public function getFront();//获取前端元素 
7.   public function getSize();//获取队列大小 
8.   public function isEmpty();//判断队列是否为空 
9. }

Tags: PHP带尾指针 PHP队列

分享到：