這篇文章是展示通過 PHP 語言實(shí)現(xiàn)一種帶 尾指針 的鏈表，然后通過鏈表來實(shí)現(xiàn)隊(duì)列，其中鏈表的頭元素 head 是用于列隊(duì) 出隊(duì) 的，它的時(shí)間復(fù)雜度 O(1) ，若在 head 的基礎(chǔ)上實(shí)現(xiàn)鏈表尾部 入隊(duì) 時(shí)間度為 O(n)，為了降低入隊(duì)操作的時(shí)間復(fù)雜度，可以給鏈表維護(hù)一個(gè)帶有尾指針的變量 tail ，這樣每次入隊(duì)的時(shí)候直接操作 tail ，出隊(duì)的時(shí)候直接操作 head ，這樣可以使得 入隊(duì) 和 出隊(duì) 時(shí)間復(fù)雜度都是 O(1)。
1.output_queue_by_liked_list.php
這是一個(gè)演示打印輸出結(jié)果的文件：
?php
require 'QueueByLinkedList.php';
$queue = new QueueByLinkedList();
$queue->enqueue("rr"); //入隊(duì)
$queue->enqueue("tt"); //入隊(duì)
$queue->enqueue("yy"); //入隊(duì)
$queue->enqueue("uu"); //入隊(duì)
$queue->enqueue("ii"); //入隊(duì)
$queue->enqueue("oo"); //入隊(duì)
echo $queue->toString(); //打印 rr->tt->yy->uu->ii->oo->null
echo "br>";
echo $queue->dequeue(); //出隊(duì) 打印 rr
echo "br>";
echo $queue->dequeue(); //出隊(duì) 打印 tt
echo "br>";
echo $queue->dequeue(); //出隊(duì) 打印 yy
echo "br>";
echo $queue->toString(); //打印 uu->ii->oo->null
echo "br>";
$queue->enqueue("11"); //入隊(duì)
$queue->enqueue("22"); //入隊(duì)
$queue->enqueue("33"); //入隊(duì)
$queue->enqueue("44"); //入隊(duì)
$queue->enqueue("55"); //入隊(duì)
$queue->enqueue("66"); //入隊(duì)
echo "br>";
echo $queue->toString(); //打印 uu->ii->oo->11->22->33->44->55->66->null
2.QueueByLinkedList 類
這是通過帶尾指針鏈表實(shí)現(xiàn)的 隊(duì)列 類，它里面有 入隊(duì)(enqueue) 方法和 出隊(duì)(dequque) 方法 :
?php
require 'Queue.php';
/**
* 帶有尾指針的鏈表
* Class LinkedListTail
*/
class QueueByLinkedList implements Queue
{
private $head; //鏈表頭部
private $tail; //鏈表尾部
private $size; //鏈表大小
/**
* 構(gòu)造函數(shù) 初始化鏈表
* QueueByLinkedList constructor.
*/
public function __construct() {
$this->head = null;
$this->tail = null;
$this->size = 0;
}
/**
* 入隊(duì)操作
* @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++;
}
/**
* 出隊(duì)操作
* @return mixed
*/
public function dequeue() {
if ($this->size == 0) {
return "隊(duì)列已經(jīng)是空的";
}
$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 "隊(duì)列已經(jīng)是空的";
}
return $this->head->e;
}
public function getSize() {
return $this->size;
}
/**
* 判斷隊(duì)列是否為空
* @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;//節(jié)點(diǎn)元素
public $next; //下個(gè)節(jié)點(diǎn)信息
/**
* 構(gòu)造函數(shù) 設(shè)置節(jié)點(diǎn)信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next) {
$this->e = $e;
$this->next = $next;
}
}
3.interface Queue
這里是 隊(duì)列 類一個(gè)實(shí)現(xiàn)接口，里面定義了一些函數(shù)，繼承它之后，必須重構(gòu)里面的所有方法：
?php
interface Queue
{
public function enqueue($e): void;//入隊(duì)
public function dequeue();//出隊(duì)
public function getFront();//獲取前端元素
public function getSize();//獲取隊(duì)列大小
public function isEmpty();//判斷隊(duì)列是否為空
}
以上就是PHP如何通過帶尾指針的鏈表實(shí)現(xiàn)'隊(duì)列'的詳細(xì)內(nèi)容，更多關(guān)于PHP 實(shí)現(xiàn)隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:- PHP7生產(chǎn)環(huán)境隊(duì)列Beanstalkd用法詳解
- PHP Beanstalkd消息隊(duì)列的安裝與使用方法實(shí)例詳解
- PHP+RabbitMQ實(shí)現(xiàn)消息隊(duì)列的完整代碼
- 詳解PHP隊(duì)列的實(shí)現(xiàn)
- php基于Redis消息隊(duì)列實(shí)現(xiàn)的消息推送的方法
- PHP隊(duì)列場(chǎng)景以及實(shí)現(xiàn)代碼實(shí)例詳解
