• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    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

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

    3.interface Queue

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

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

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

    您可能感兴趣的文章:
    • PHP7生产环境队列Beanstalkd用法详解
    • PHP Beanstalkd消息队列的安装与使用方法实例详解
    • PHP+RabbitMQ实现消息队列的完整代码
    • 详解PHP队列的实现
    • php基于Redis消息队列实现的消息推送的方法
    • PHP队列场景以及实现代码实例详解
    上一篇:php使用event扩展的io复用测试的示例
    下一篇:php redis setnx分布式锁简单原理解析
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

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