這篇文章是展示通過 PHP 語言實現一種帶 尾指針 的鏈表，然后通過鏈表來實現隊列，其中鏈表的頭元素 head 是用于列隊 出隊 的，它的時間復雜度 O(1) ，若在 head 的基礎上實現鏈表尾部 入隊 時間度為 O(n)，為了降低入隊操作的時間復雜度，可以給鏈表維護一個帶有尾指針的變量 tail ，這樣每次入隊的時候直接操作 tail ，出隊的時候直接操作 head ，這樣可以使得 入隊 和 出隊 時間復雜度都是 O(1)。
1.output_queue_by_liked_list.php
這是一個演示打印輸出結果的文件：
?php
require '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->null
echo "br>";
echo $queue->dequeue(); //出隊 打印 rr
echo "br>";
echo $queue->dequeue(); //出隊 打印 tt
echo "br>";
echo $queue->dequeue(); //出隊 打印 yy
echo "br>";
echo $queue->toString(); //打印 uu->ii->oo->null
echo "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) 方法 :
?php
require '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
這里是 隊列 類一個實現接口，里面定義了一些函數，繼承它之后，必須重構里面的所有方法：
?php
interface Queue
{
public function enqueue($e): void;//入隊
public function dequeue();//出隊
public function getFront();//獲取前端元素
public function getSize();//獲取隊列大小
public function isEmpty();//判斷隊列是否為空
}
以上就是PHP如何通過帶尾指針的鏈表實現'隊列'的詳細內容，更多關于PHP 實現隊列的資料請關注腳本之家其它相關文章！
您可能感興趣的文章:- PHP7生產環境隊列Beanstalkd用法詳解
- PHP Beanstalkd消息隊列的安裝與使用方法實例詳解
- PHP+RabbitMQ實現消息隊列的完整代碼
- 詳解PHP隊列的實現
- php基于Redis消息隊列實現的消息推送的方法
- PHP隊列場景以及實現代碼實例詳解
