快捷導(dǎo)航

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

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

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

這篇文章是展示通過 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)文章！

您可能感興趣的文章: