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 实现队列的资料请关注我们其它相关文章!

(0)

相关推荐

  • php数组指针操作详解

    数组指针的操作: 移动数组指针的操作: Next() 向下 同时会获得当前元素的值. Prev() 向上同时会获得当前元素的值. End() 移动到最后一个元素单元 获得最后一个元素的值 Reset() 移动到第一个单元 获得第一个元素的值. 如果移动不成功,返回false. 参数都为需要操作的数组,并且是引用传递. 获得指针指向的元素的信息: Key();//获得当前数组指针指向的元素下标 Current();//获得当前数组指针指向的元素 只获取数据 不移动指针 还有一个混合的操作: 即可以

  • PHP实现链表的定义与反转功能示例

    本文实例讲述了PHP实现链表的定义与反转功能.分享给大家供大家参考,具体如下: PHP定义链表及添加.移除.遍历等操作: <?php class Node { private $Data;//节点数据 private $Next;//下一节点 public function setData($value){ $this->Data=$value; } public function setNext($value){ $this->Next=$value; } public functio

  • php+redis实现消息队列功能示例

    本文实例讲述了php+redis实现消息队列功能.分享给大家供大家参考,具体如下: 个人理解在项目中使用消息队列一般是有如下几个原因: 把瞬间服务器的请求处理换成异步处理,缓解服务器的压力 实现数据顺序排列获取 redis实现消息队列步骤如下: 1).redis函数rpush,lpop 2).建议定时任务入队列 3)创建定时任务出队列 文件:demo.php插入数据到redis队列 <?php $redis = new Redis(); $redis->connect('127.0.0.1',

  • php数组和链表的区别总结

    PHP中数组和链表的区别 从逻辑结构来看 1..数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况.当数据增加时,可能超出原先定义的元素个数:当数据减少时,造成内存浪费:数组可以根据下标直接存取. 2.链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入.删除数据项.(数组中插入.删除数据项时,需要移动其它数据项,非常繁琐)链表必须根据next指针找到下一个元素. 从内存存储来看 1.(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小. 2.链表从

  • php使用redis的有序集合zset实现延迟队列应用示例

    本文实例讲述了php使用redis的有序集合zset实现延迟队列.分享给大家供大家参考,具体如下: 延迟队列就是个带延迟功能的消息队列,相对于普通队列,它可以在指定时间消费掉消息. 延迟队列的应用场景: 1.新用户注册,10分钟后发送邮件或站内信. 2.用户下单后,30分钟未支付,订单自动作废. 我们通过redis的有序集合zset来实现简单的延迟队列,将消息数据序列化,作为zset的value,把消息处理时间作为score,每次通过zRangeByScore获取一条消息进行处理. <?php

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • PHP双向链表定义与用法示例

    本文实例讲述了PHP双向链表定义与用法.分享给大家供大家参考,具体如下: 由于需要对一组数据多次进行移动操作,所以写个双向链表.但对php实在不熟悉,虽然测试各个方法没啥问题,就是不知道php语言深层的这些指针和unset有什么注意的地方,贴出来让大家教育吧.效率没测试....求谅解- <?php /** * **双向链表 * @author zhiyuan12@ */ /** * 链表元素结点类 */ class Node_Element { public $pre = NULL; // 前驱

  • php each 返回数组中当前的键值对并将数组指针向前移动一步实例

    each函数返回数组中当前的键/值对并将数组指针向前移动一步 基本语法 array each ( array &$array ) 在执行 each() 之后,数组指针将停留在数组中的下一个单元或者当碰到数组结尾时停留在最后一个单元.如果要再用 each 遍历数组,必须使用 reset() . 参数介绍: 参数 描述 array 必需.规定要使用的数组. each() 函数生成一个由数组当前内部指针所指向的元素的键名和键值组成的数组,并把内部指针向前移动. 返回值: 返回 array 数组中当前指

  • PHP7生产环境队列Beanstalkd用法详解

    应用场景 为什么要用呢,有什么好处?这应该放在最开头说,一件东西你只有了解它是干什么的,适合干什么,才能更好的与自己的项目相结合,用到哪里学到哪里,学了不用等于不会,我们平时就应该多考虑一些这样的问题:自己做个什么项目功能能跟 xx 技术相结合呢?这个 xx 技术放在这种业务场景下行不行呢?而不是 "学了这个 xx 技术能干嘛呢,公司现在也没有用这个的呀,学了也没用啊",带着这样心情去学习 xx 技术,肯定很痛苦. 队列大家都知道是将一些耗时的操作先不去做,先埋点,再异步去处理,这样对

  • php数据结构之顺序链表与链式线性表示例

    本文实例讲述了php数据结构之顺序链表与链式线性表.分享给大家供大家参考,具体如下: 链表操作 1.     InitList(L):初始化链表 2.     DestroyList(L):删除连接 3.     ClearList(L):清空链表 4.     ListEmpty(L):判断是否为空 5.     ListLength(L):链表长度 6.     getElem(L,i):取出元素 7.     LocateElem(L,e):判断e是否在链表中 8.     PriorEl

随机推荐