返回
热门搜索

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

IT博客 开发工具 intellij idea 点击量 535

基本信息 收藏 - 举报 - 海报

详细介绍

这篇文章是展示通过 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 "
"; echo $queue->dequeue(); //出队 打印 rr echo "
"; echo $queue->dequeue(); //出队 打印 tt echo "
"; echo $queue->dequeue(); //出队 打印 yy echo "
"; echo $queue->toString(); //打印 uu->ii->oo->null echo "
"; $queue->enqueue("11"); //入队 $queue->enqueue("22"); //入队 $queue->enqueue("33"); //入队 $queue->enqueue("44"); //入队 $queue->enqueue("55"); //入队 $queue->enqueue("66"); //入队 echo "
"; 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 实现队列的资料请关注IT博客社区其它相关文章!

没有更多内容。

用户评价(0)

好评度100%
  • 还没有人评论此条信息!
+ 加载更多

联系方式

提示:联系我时,请说明在巅云php学苑看到的,谢谢!
  • 联系人:
  • 地  区:
  • 电  话: 共发布信息(2004)条 所在地:未填写
看了又看
加载中
首页 首页 收藏 收藏

电话联系