关于php:PHP通过带尾指针的链表实现队列

这篇文章是展现通过 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

3.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;
    }
}

4.interface Queue

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

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