PHP如何通過帶尾指針的鏈表實現(xiàn)'隊列'

更新時間：2020年10月22日 11:07:47 作者：愛因詩賢

這篇文章主要介紹了PHP如何通過帶尾指針的鏈表實現(xiàn)'隊列'，幫助大家更好的理解和使用php，感興趣的朋友可以了解下

這篇文章是展示通過 PHP 語言實現(xiàn)一種帶 尾指針 的鏈表，然后通過鏈表來實現(xiàn)隊列，其中鏈表的頭元素 head 是用于列隊 出隊 的，它的時間復雜度 O(1) ，若在 head 的基礎上實現(xiàn)鏈表尾部 入隊 時間度為 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 類

這是通過帶尾指針鏈表實現(xiàn)的 隊列 類，它里面有 入隊(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;//節(jié)點元素
  public $next; //下個節(jié)點信息
  /**
   * 構造函數 設置節(jié)點信息
   * Node constructor.
   * @param $e
   * @param $next
   */
  public function __construct($e, $next) {
    $this->e = $e;
    $this->next = $next;
  }
}

3.interface Queue

這里是 隊列 類一個實現(xiàn)接口，里面定義了一些函數，繼承它之后，必須重構里面的所有方法：

<?php
interface Queue
{
  public function enqueue($e): void;//入隊
  public function dequeue();//出隊
  public function getFront();//獲取前端元素
  public function getSize();//獲取隊列大小
  public function isEmpty();//判斷隊列是否為空
}

以上就是PHP如何通過帶尾指針的鏈表實現(xiàn)'隊列'的詳細內容，更多關于PHP 實現(xiàn)隊列的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: