PHP如何通过带尾指针的链表实现'队列'

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

1.output_queue_by_liked_list.php

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

<?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) 方法 :

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

<?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

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

?

1 2 3 4 5 6 7 8 9

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

以上就是PHP如何通过带尾指针的链表实现'队列'的详细内容，更多关于PHP 实现队列的资料请关注服务器之家其它相关文章！

原文链接：https://segmentfault.com/a/1190000037557689?utm_source=tuicool&utm_medium=referral