当前位置:首页 > PHP教程 > php高级应用 > 列表

php双向队列实例讲解

发布:smiling 来源: PHP粉丝网  添加日期:2022-05-17 15:21:04 浏览: 评论:0 

在本篇文章里小编给大家整理的是一篇关于php双向队列如何理解的相关内容及实例,需要的朋友们可以跟着学习下。

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

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

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

实例:

  1. <?php 
  2. class DoubleQueue 
  3.     public $queue = array(); 
  4.     /**(尾部)入队  **/ 
  5.     public function addLast($value
  6.     { 
  7.         return array_push($this->queue,$value); 
  8.     } 
  9.     /**(尾部)出队**/ 
  10.     public function removeLast() 
  11.     { 
  12.    
  13.         return array_pop($this->queue); 
  14.    
  15.     } 
  16.    
  17.     /**(头部)入队**/ 
  18.    
  19.     public function addFirst($value
  20.    
  21.     { 
  22.         return array_unshift($this->queue,$value); 
  23.    
  24.     } 
  25.    
  26.     /**(头部)出队**/ 
  27.     public function removeFirst() 
  28.     { 
  29.         return array_shift($this->queue); 
  30.     } 
  31.     /**清空队列**/ 
  32.     public function makeEmpty() 
  33.     { 
  34.         unset($this->queue); 
  35.     } 
  36.     /**获取列头**/ 
  37.     public function getFirst() 
  38.     { 
  39.         return reset($this->queue); 
  40.     } 
  41.     /** 获取列尾 **/ 
  42.     public function getLast() 
  43.     { 
  44.         return end($this->queue); 
  45.     } 
  46.     /** 获取长度 **/ 
  47.     public function getLength() 
  48.     { 
  49.         return count($this->queue); 
  50.     } 

实例扩展:

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

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

DEQue.class.php类文件如下:

  1. <?php  
  2. /** php 双向队列。支持限定队列长度,输入受限,输出受限,及输出必须与输入同端几种设置  
  3. *  Date:  2014-04-30  
  4. *  Author: fdipzone  
  5. *  Ver:  1.0  
  6.  
  7. *  Func:  
  8. *  public frontAdd   前端入列  
  9. *  public frontRemove 前端出列  
  10. *  public rearAdd   后端入列  
  11. *  pulbic rearRemove  后端出列  
  12. *  public clear    清空对列  
  13. *  public isFull    判断对列是否已满  
  14. *  private getLength  获取对列长度  
  15. *  private setAddNum  记录入列,输出依赖输入时调用  
  16. *  private setRemoveNum 记录出列,输出依赖输入时调用  
  17. *  private checkRemove 检查是否输出依赖输入  
  18. */ 
  19.    
  20. class DEQue{ // class start  
  21.    
  22.   private $_queue = array(); // 对列  
  23.   private $_maxLength = 0;  // 对列最大长度,0表示不限  
  24.   private $_type = 0;    // 对列类型  
  25.   private $_frontNum = 0;  // 前端插入的数量  
  26.   private $_rearNum = 0;   // 后端插入的数量  
  27.    
  28.    
  29.   /** 初始化  
  30.   * @param $type    对列类型  
  31.   *          1:两端均可输入输出  
  32.   *          2:前端只能输入,后端可输入输出  
  33.   *          3:前端只能输出,后端可输入输出  
  34.   *          4:后端只能输入,前端可输入输出  
  35.   *          5:后端只能输出,前端可输入输出  
  36.   *          6:两端均可输入输出,在哪端输入只能从哪端输出  
  37.   * @param $maxlength 对列最大长度  
  38.   */ 
  39.   public function __construct($type=1, $maxlength=0){  
  40.     $this->_type = in_array($typearray(1,2,3,4,5,6))? $type : 1;  
  41.     $this->_maxLength = intval($maxlength);  
  42.   }  
  43.    
  44.    
  45.   /** 前端入列  
  46.   * @param Mixed  $data 数据  
  47.   * @return boolean  
  48.   */ 
  49.   public function frontAdd($data=null){  
  50.    
  51.     if($this->_type==3){ // 前端输入限制  
  52.       return false;  
  53.     }  
  54.    
  55.     if(isset($data) && !$this->isFull()){  
  56.    
  57.       array_unshift($this->_queue, $data);  
  58.    
  59.       $this->setAddNum(1);  
  60.    
  61.       return true;  
  62.     }  
  63.     return false;  
  64.   }  
  65.    
  66.   /** 前端出列  
  67.   * @return Array  
  68.   */ 
  69.   public function frontRemove(){  
  70.    
  71.     if($this->_type==2){ // 前端输出限制  
  72.       return null;  
  73.     }  
  74.    
  75.     if(!$this->checkRemove(1)){ // 检查是否依赖输入  
  76.       return null;  
  77.     }  
  78.    
  79.     $data = null;  
  80.    
  81.     if($this->getLength()>0){  
  82.    
  83.       $data = array_shift($this->_queue);  
  84.    
  85.       $this->setRemoveNum(1);  
  86.     }  
  87.     return $data;  
  88.   }  
  89.    
  90.   /** 后端入列  
  91.   * @param Mixed  $data 数据  
  92.   * @return boolean  
  93.   */ 
  94.   public function rearAdd($data=null){  
  95.    
  96.     if($this->_type==5){ // 后端输入限制  
  97.       return false;  
  98.     }  
  99.    
  100.     if(isset($data) && !$this->isFull()){  
  101.    
  102.       array_push($this->_queue, $data);  
  103.    
  104.       $this->setAddNum(2);  
  105.    
  106.       return true;  
  107.     }  
  108.     return false;  
  109.   }  
  110.    
  111.   /** 后端出列  
  112.   * @return Array  
  113.   */ 
  114.   public function rearRemove(){  
  115.    
  116.     if($this->_type==4){ // 后端输出限制  
  117.       return null;  
  118.     }  
  119.    
  120.     if(!$this->checkRemove(2)){ // 检查是否依赖输入  
  121.       return null;  
  122.     }  
  123.    
  124.     $data = null;  
  125.    
  126.     if($this->getLength()>0){  
  127.    
  128.       $data = array_pop($this->_queue);  
  129.    
  130.       $this->setRemoveNum(2);  
  131.     }  
  132.     return $data;  
  133.   }  
  134.    
  135.   /** 清空对列  
  136.   * @return boolean  
  137.   */ 
  138.   public function clear(){  
  139.     $this->_queue = array();  
  140.     $this->_frontNum = 0;  
  141.     $this->_rearNum = 0;  
  142.     return true;  
  143.   }  
  144.    
  145.   /** 判断对列是否已满  
  146.   * @return boolean  
  147.   */ 
  148.   public function isFull(){  
  149.     $bIsFull = false;  
  150.     if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){  
  151.       $bIsFull = true;  
  152.     }  
  153.     return $bIsFull;  
  154.   }  
  155.    
  156.   /** 获取当前对列长度  
  157.   * @return int  
  158.   */ 
  159.   private function getLength(){  
  160.     return count($this->_queue);  
  161.   }  
  162.    
  163.   /** 记录入列,输出依赖输入时调用  
  164.   * @param int $endpoint 端点 1:front 2:rear  
  165.   */ 
  166.   private function setAddNum($endpoint){  
  167.     if($this->_type==6){  
  168.       if($endpoint==1){  
  169.         $this->_frontNum ++;  
  170.       }else{  
  171.         $this->_rearNum ++;  
  172.       }  
  173.     }  
  174.   }  
  175.    
  176.   /** 记录出列,输出依赖输入时调用  
  177.   * @param int $endpoint 端点 1:front 2:rear  
  178.   */ 
  179.   private function setRemoveNum($endpoint){  
  180.     if($this->_type==6){  
  181.       if($endpoint==1){  
  182.         $this->_frontNum --;  
  183.       }else{  
  184.         $this->_rearNum --;  
  185.       }  
  186.     }  
  187.   }  
  188.    
  189.   /** 检查是否输出依赖输入  
  190.   * @param int $endpoint 端点 1:front 2:rear  
  191.   */ 
  192.   private function checkRemove($endpoint){  
  193.     if($this->_type==6){  
  194.       if($endpoint==1){  
  195.         return $this->_frontNum>0;  
  196.       }else{  
  197.         return $this->_rearNum>0;  
  198.       }  
  199.     }  
  200.     return true;  
  201.   }  
  202. // class end  
  203. ?>  

demo.php示例代码如下:

  1. <?php  
  2.    
  3. require "DEQue.class.php";  
  4.    
  5. // 例子1  
  6.    
  7. $obj = new DEQue(); // 前后端都可以输入,无限长度  
  8.    
  9. $obj->frontAdd('a'); // 前端入列  
  10. $obj->rearAdd('b'); // 后端入列  
  11. $obj->frontAdd('c'); // 前端入列  
  12. $obj->rearAdd('d'); // 后端入列  
  13.    
  14. // 入列后数组应为 cabd  
  15.    
  16. $result = array();  
  17.    
  18. $result[] = $obj->rearRemove(); // 后端出列  
  19. $result[] = $obj->rearRemove(); // 后端出列  
  20. $result[] = $obj->frontRemove(); // 前端出列  
  21. $result[] = $obj->frontRemove(); // 前端出列  
  22.    
  23. print_r($result); // 出列顺序应为 dbca  
  24.    
  25. // 例子2  
  26. $obj = new DEQue(3, 5); // 前端只能输出,后端可输入输出,最大长度5  
  27.    
  28. $insert = array();  
  29. $insert[] = $obj->rearAdd('a');  
  30. $insert[] = $obj->rearAdd('b');  
  31. $insert[] = $obj->frontAdd('c'); // 因前端只能输出,因此这里会返回false  
  32. $insert[] = $obj->rearAdd('d');  
  33. $insert[] = $obj->rearAdd('e');  
  34. $insert[] = $obj->rearAdd('f');  
  35. $insert[] = $obj->rearAdd('g'); // 超过长度,返回false  
  36.    
  37. var_dump($insert);  
  38.    
  39. // 例子3  
  40. $obj = new DEQue(6); // 输出依赖输入  
  41.    
  42. $obj->frontAdd('a');  
  43. $obj->frontAdd('b');  
  44. $obj->frontAdd('c');  
  45. $obj->rearAdd('d');  
  46.    
  47. $result = array();  
  48. $result[] = $obj->rearRemove();  
  49. $result[] = $obj->rearRemove(); // 因为输出依赖输入,这个会返回NULL  
  50. $result[] = $obj->frontRemove();  
  51. $result[] = $obj->frontRemove();  
  52. $result[] = $obj->frontRemove();  
  53.    
  54. var_dump($result);  
  55.    
  56. ?>

Tags: php双向队列

分享到: