php双向队列实例讲解

1、双向队列是指一种具有队列和栈的性质的数据结构。

2、双向队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。

双向队列就像是一个队列,但是你可以在任何一端添加或移除元素。

实例

<?php
class DoubleQueue
{
    public $queue = array();
    /**(尾部)入队  **/
    public function addLast($value)
    {
        return array_push($this->queue,$value);
    }
    /**(尾部)出队**/
    public function removeLast()
    {

        return array_pop($this->queue);

    }

    /**(头部)入队**/

    public function addFirst($value)

    {
        return array_unshift($this->queue,$value);

    }

    /**(头部)出队**/
    public function removeFirst()
    {
        return array_shift($this->queue);
    }
    /**清空队列**/
    public function makeEmpty()
    {
        unset($this->queue);
    }
    /**获取列头**/
    public function getFirst()
    {
        return reset($this->queue);
    }
    /** 获取列尾 **/
    public function getLast()
    {
        return end($this->queue);
    }
    /** 获取长度 **/
    public function getLength()
    {
        return count($this->queue);
    }
}

实例扩展:

(deque,全名double-ended queue)是一种具有队列和栈的性质的数据结构。双向队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。

在实际使用中,还可以有输出受限的双向队列(即一个端点允许插入和删除,另一个端点只允许插入的双向队列)和输入受限的双向队列(即一个端点允许插入和删除,另一个端点只允许删除的双向队列)。而如果限定双向队列从某个端点插入的元素只能从该端点删除,则该双向队列就蜕变为两个栈底相邻的栈了。

DEQue.class.php类文件如下:

<?php
/** php 双向队列。支持限定队列长度,输入受限,输出受限,及输出必须与输入同端几种设置
*  Date:  2014-04-30
*  Author: fdipzone
*  Ver:  1.0
*
*  Func:
*  public frontAdd   前端入列
*  public frontRemove 前端出列
*  public rearAdd   后端入列
*  pulbic rearRemove  后端出列
*  public clear    清空对列
*  public isFull    判断对列是否已满
*  private getLength  获取对列长度
*  private setAddNum  记录入列,输出依赖输入时调用
*  private setRemoveNum 记录出列,输出依赖输入时调用
*  private checkRemove 检查是否输出依赖输入
*/ 

class DEQue{ // class start 

  private $_queue = array(); // 对列
  private $_maxLength = 0;  // 对列最大长度,0表示不限
  private $_type = 0;    // 对列类型
  private $_frontNum = 0;  // 前端插入的数量
  private $_rearNum = 0;   // 后端插入的数量 

  /** 初始化
  * @param $type    对列类型
  *          1:两端均可输入输出
  *          2:前端只能输入,后端可输入输出
  *          3:前端只能输出,后端可输入输出
  *          4:后端只能输入,前端可输入输出
  *          5:后端只能输出,前端可输入输出
  *          6:两端均可输入输出,在哪端输入只能从哪端输出
  * @param $maxlength 对列最大长度
  */
  public function __construct($type=1, $maxlength=0){
    $this->_type = in_array($type, array(1,2,3,4,5,6))? $type : 1;
    $this->_maxLength = intval($maxlength);
  } 

  /** 前端入列
  * @param Mixed  $data 数据
  * @return boolean
  */
  public function frontAdd($data=null){ 

    if($this->_type==3){ // 前端输入限制
      return false;
    } 

    if(isset($data) && !$this->isFull()){ 

      array_unshift($this->_queue, $data); 

      $this->setAddNum(1); 

      return true;
    }
    return false;
  } 

  /** 前端出列
  * @return Array
  */
  public function frontRemove(){ 

    if($this->_type==2){ // 前端输出限制
      return null;
    } 

    if(!$this->checkRemove(1)){ // 检查是否依赖输入
      return null;
    } 

    $data = null; 

    if($this->getLength()>0){ 

      $data = array_shift($this->_queue); 

      $this->setRemoveNum(1);
    }
    return $data;
  } 

  /** 后端入列
  * @param Mixed  $data 数据
  * @return boolean
  */
  public function rearAdd($data=null){ 

    if($this->_type==5){ // 后端输入限制
      return false;
    } 

    if(isset($data) && !$this->isFull()){ 

      array_push($this->_queue, $data); 

      $this->setAddNum(2); 

      return true;
    }
    return false;
  } 

  /** 后端出列
  * @return Array
  */
  public function rearRemove(){ 

    if($this->_type==4){ // 后端输出限制
      return null;
    } 

    if(!$this->checkRemove(2)){ // 检查是否依赖输入
      return null;
    } 

    $data = null; 

    if($this->getLength()>0){ 

      $data = array_pop($this->_queue); 

      $this->setRemoveNum(2);
    }
    return $data;
  } 

  /** 清空对列
  * @return boolean
  */
  public function clear(){
    $this->_queue = array();
    $this->_frontNum = 0;
    $this->_rearNum = 0;
    return true;
  } 

  /** 判断对列是否已满
  * @return boolean
  */
  public function isFull(){
    $bIsFull = false;
    if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){
      $bIsFull = true;
    }
    return $bIsFull;
  } 

  /** 获取当前对列长度
  * @return int
  */
  private function getLength(){
    return count($this->_queue);
  } 

  /** 记录入列,输出依赖输入时调用
  * @param int $endpoint 端点 1:front 2:rear
  */
  private function setAddNum($endpoint){
    if($this->_type==6){
      if($endpoint==1){
        $this->_frontNum ++;
      }else{
        $this->_rearNum ++;
      }
    }
  } 

  /** 记录出列,输出依赖输入时调用
  * @param int $endpoint 端点 1:front 2:rear
  */
  private function setRemoveNum($endpoint){
    if($this->_type==6){
      if($endpoint==1){
        $this->_frontNum --;
      }else{
        $this->_rearNum --;
      }
    }
  } 

  /** 检查是否输出依赖输入
  * @param int $endpoint 端点 1:front 2:rear
  */
  private function checkRemove($endpoint){
    if($this->_type==6){
      if($endpoint==1){
        return $this->_frontNum>0;
      }else{
        return $this->_rearNum>0;
      }
    }
    return true;
  }
} // class end
?>

demo.php示例代码如下:

<?php 

require "DEQue.class.php"; 

// 例子1 

$obj = new DEQue(); // 前后端都可以输入,无限长度 

$obj->frontAdd('a'); // 前端入列
$obj->rearAdd('b'); // 后端入列
$obj->frontAdd('c'); // 前端入列
$obj->rearAdd('d'); // 后端入列 

// 入列后数组应为 cabd 

$result = array(); 

$result[] = $obj->rearRemove(); // 后端出列
$result[] = $obj->rearRemove(); // 后端出列
$result[] = $obj->frontRemove(); // 前端出列
$result[] = $obj->frontRemove(); // 前端出列 

print_r($result); // 出列顺序应为 dbca 

// 例子2
$obj = new DEQue(3, 5); // 前端只能输出,后端可输入输出,最大长度5 

$insert = array();
$insert[] = $obj->rearAdd('a');
$insert[] = $obj->rearAdd('b');
$insert[] = $obj->frontAdd('c'); // 因前端只能输出,因此这里会返回false
$insert[] = $obj->rearAdd('d');
$insert[] = $obj->rearAdd('e');
$insert[] = $obj->rearAdd('f');
$insert[] = $obj->rearAdd('g'); // 超过长度,返回false 

var_dump($insert); 

// 例子3
$obj = new DEQue(6); // 输出依赖输入 

$obj->frontAdd('a');
$obj->frontAdd('b');
$obj->frontAdd('c');
$obj->rearAdd('d'); 

$result = array();
$result[] = $obj->rearRemove();
$result[] = $obj->rearRemove(); // 因为输出依赖输入,这个会返回NULL
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove(); 

var_dump($result); 

?>

以上就是php双向队列实例讲解的详细内容,更多关于php双向队列如何理解的资料请关注我们其它相关文章!

时间: 2021-11-02

js最简单的双向绑定实例讲解

把代码复制放到页面里面运行看一下效果就好了 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> </head> <body> <input type="text" id="myinput" > <sc

php实现的双向队列类实例

本文实例讲述了php实现的双向队列类及其用法,对于PHP数据结构与算法的学习有不错的参考价值.分享给大家供大家参考.具体分析如下: (deque,全名double-ended queue)是一种具有队列和栈的性质的数据结构.双向队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行. 在实际使用中,还可以有输出受限的双向队列(即一个端点允许插入和删除,另一个端点只允许插入的双向队列)和输入受限的双向队列(即一个端点允许插入和删除,另一个端点只允许删除的双向队列).而如果限定双向队列从某个

python队列通信:rabbitMQ的使用(实例讲解)

(一).前言 为什么引入消息队列? 1.程序解耦 2.提升性能 3.降低多业务逻辑复杂度 (二).python操作rabbit mq rabbitmq配置安装基本使用参见上节文章,不再复述. 若想使用python操作rabbitmq,需安装pika模块,直接pip安装: pip install pika 1.最简单的rabbitmq producer端与consumer端对话: producer: #Author :ywq import pika auth=pika.PlainCredentia

Node.js学习之TCP/IP数据通讯(实例讲解)

1.使用net模块实现基于TCP的数据通讯 提供了一个net模块,专用于实现TCP服务器与TCP客户端之间的通信 1.1创建TCP服务器 在Node.js利用net模块创建TCP服务器 var server = net.createServer([options],[connectionListener]) //options:false当TCP服务器接收到客户端发送的一个FIN包时将会回发一个FIN包 true当TCP服务器接收到客户端发送的一个FIN包时将不会回发FIN包,这使得TCP服务器

JavaWeb文件上传下载实例讲解(酷炫的文件上传技术)

一.课程概述 在Web应用系统开发中,文件上传功能是非常常用的功能,今天来主要讲讲JavaWeb中的文件上传功能的相关技术实现,并且随着互联网技术的飞速发展,用户对网站的体验要求越来越高,在文件上传功能的技术上也出现许多创新点,例如异步上传文件,拖拽式上传,黏贴上传,上传进度监控,文件缩略图,大文件断点续传,大文件秒传等等. 本课程需要的基础知识: 了解基本的Http协议内容 基本IO流操作技术 Servlet基础知识 javascript/jQuery技术基础知识 二.文件上传的基础 对于文件

基于python select.select模块通信的实例讲解

要理解select.select模块其实主要就是要理解它的参数, 以及其三个返回值. select()方法接收并监控3个通信列表, 第一个是所有的输入的data,就是指外部发过来的数据,第2个是监控和接收所有要发出去的data(outgoing data),第3个监控错误信息在网上一直在找这个select.select的参数解释, 但实在是没有, 哎...自己硬着头皮分析了一下. readable, writable, exceptional = select.select(inputs, ou

vue父组件中获取子组件中的数据(实例讲解)

如下所示: <FormItem label="上传头像" prop="image"> <uploadImg :width="150" :height="150" :name="'avatar'" size="150px*150px" ref="avatar"></uploadImg> </FormItem> <Fo

Android Studio应用开发集成百度语音合成使用方法实例讲解

首先,语音合成是指将文本信息转换成声音.意思就是将文本转化为声音,让你的应用开口说话.国内在业内比较有名的第三方语音合成平台有百度语音和科大讯飞. 本文集成的是百度语音合成,其主要特点是: 完全永久免费 业界首创完全永久免费新形式,为开发者提供最流畅最自然的语音合成服务.完全免费,永久使用,彻底摆脱限制. 离线在线融合模式 SDK可以根据当前网络状况,自动判断使用本地引擎还是云端引擎进行语音合成,再也不用担心流量消耗! 多语言多音色可选 中文普通话.中英文混读.男声.女声任你选,更支持语速.音调

SPFA 算法实例讲解

适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便 派上用场了. 我们约定有向加权图G不存在负权回路,即最短路径一定存在.当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重 点. 算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G.我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的 结点,优化时每次取出队首结点u,并且用u点当前的最短路

Queue 实现生产者消费者模型(实例讲解)

Python中,队列是线程间最常用的交换数据的形式. Python Queue模块有三种队列及构造函数: 1.Python Queue模块的FIFO队列先进先出. class Queue.Queue(maxsize) 2.LIFO类似于堆,即先进后出. class Queue.LifoQueue(maxsize) 3.还有一种是优先级队列级别越低越先出来. class Queue.PriorityQueue(maxsize) 此包中的常用方法(q = Queue.Queue()): q.qsiz