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();//判断队列是否为空
}
特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。

php介绍

PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。

Tags 标签

php算法程序员

扩展阅读

加个好友,技术交流

1628738909466805.jpg