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

 更新时间:2020-11-19 10:26:30   作者:佚名   我要评论(0)

这篇文章是展示通过 PHP 语言实现一种带 尾指针 的链表,然后通过链表来实现队列,其中链表的头元素 head 是用于列队 出队 的,它的时间复杂度 O(1) ,若在 head 的

这篇文章是展示通过 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 实现队列的资料请关注脚本之家其它相关文章!

您可能感兴趣的文章:
  • php数组和链表的区别总结
  • PHP实现链表的定义与反转功能示例
  • PHP双向链表定义与用法示例
  • php数据结构之顺序链表与链式线性表示例
  • PHP实现合并两个排序链表的方法
  • php数组指针操作详解
  • php each 返回数组中当前的键值对并将数组指针向前移动一步实例
  • PHP7生产环境队列Beanstalkd用法详解
  • php使用redis的有序集合zset实现延迟队列应用示例
  • php+redis实现消息队列功能示例

相关文章

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

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

    这篇文章是展示通过 PHP 语言实现一种带 尾指针 的链表,然后通过链表来实现队列,其中链表的头元素 head 是用于列队 出队 的,它的时间复杂度 O(1) ,若在 head 的
    2020-11-19
  • php redis setnx分布式锁简单原理解析

    php redis setnx分布式锁简单原理解析

    我就废话不多说了,大家还是直接看代码吧~ <&#63;php //高并发分布式锁 header("Content-type:text/html;charset=utf-8"); $redis = new Redis(); $redis->connec
    2020-11-19
  • 如何运行/调试你的PHP代码

    如何运行/调试你的PHP代码

    前言 没有任何一名程序员可以一气呵成、完美无缺的在不用调试的情况下完成一个功能或模块。调试实际分很多种情况。本篇文章我分享下自己在实际开发工作中的经验,我
    2020-11-19
  • 数据结构之利用PHP实现二分搜索树

    数据结构之利用PHP实现二分搜索树

    前言 这篇文章是介绍 二叉树 和 二分搜索树,然后通过 PHP 代码定义一下 二分搜索树 的节点,使用递归思想操作向二分搜索树添加元素,然后实现了递归判断二分搜索树
    2020-11-19
  • THINKPHP5分页数据对象处理过程解析

    THINKPHP5分页数据对象处理过程解析

    在用到THINKPHP5的分页的时候,我们可以发现获取的数据是对象,如果我们要对数据进行循环增加数据就实现不了 今天用此方法解决,以做记录方便以后忘了查看 // 查询
    2020-11-19
  • Laravel 自动转换长整型雪花 ID 为字符串的实现

    Laravel 自动转换长整型雪花 ID 为字符串的实现

    在设计 API 时,出于安全性等因素考虑,有时需要放弃使用自增 ID,使 ID 非连续且不可猜测。通常可以使用 Hash id,UUID,雪花 ID 等来实现。 在最近的一个项目中,我
    2020-11-19
  • 基于PHP实现邮箱验证激活过程详解

    基于PHP实现邮箱验证激活过程详解

    我们在很多网站注册会员时,注册完成后,系统会自动向用户的邮箱发送一封邮件,这封邮件的内容就是一个URL链接,用户需要点击打开这个链接才能激活之前在该网站注册
    2020-11-19
  • ThinkPHP 5 AJAX跨域请求头设置实现过程解析

    ThinkPHP 5 AJAX跨域请求头设置实现过程解析

    最近用thinkphp做项目,在测试环境时,存在接口的测试问题。在tp官网也没能找到相关的解决方法。自已看了一下源码,有如下的解决方案。 在项目目录下面,创建common
    2020-11-19
  • PHP常量DIRECTORY_SEPARATOR原理及用法解析

    PHP常量DIRECTORY_SEPARATOR原理及用法解析

    DIRECTORY_SEPARATOR在php是什么意思呢,在什么时候使用DIRECTORY_SEPARATOR最合理呢&#63;下面来给各位介绍一下php DIRECTORY_SEPARATOR常量。 我们知道DIRECTORY_S
    2020-11-19
  • 解决PHPstudy Apache无法启动的问题【亲测有效】

    解决PHPstudy Apache无法启动的问题【亲测有效】

    phpStudy启动失败,网上总结了基本就是下面的三种方法: 原因一是防火墙拦截,关闭防火墙。 二是80端口已经被别的程序占用,如IIS,迅雷等; 三是没有安装VC9运行库
    2020-11-19

最新评论