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

PHP实现一个双向队列例子

发布:smiling 来源: PHP粉丝网  添加日期:2014-06-08 23:31:44 浏览: 评论:0 

deque,全名double-ended queue,是一种具有队列和栈的性质的数据结构,双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行,双向队列(双端队列)就像是一个队列,但是你可以在任何一端添加或移除元素.

双端队列(deque)是由一些项的表组成的数据结构,对该数据结构可以进行下列操作:

push(D,X) 将项X 插入到双端队列D的前端

pop(D) 从双端队列D中删除前端项并将其返回

inject(D,X) 将项X插入到双端队列D的尾端

eject(D) 从双端队列D中删除尾端项并将其返回

PHP实现代码如下:

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

例子,编写支持双端队伍的例程,每种操作均花费O(1)时间,代码如下:

  1. <?php  
  2. class deque 
  3.  public $queue  = array(); 
  4.  public $length = 0; 
  5.     
  6.  public function frontAdd($node){ 
  7.   array_unshift($this->queue,$node); 
  8.   $this->countqueue(); 
  9.  } 
  10.  public function frontRemove(){ 
  11.   $node = array_shift($this->queue); 
  12.   $this->countqueue(); 
  13.   return $node
  14.  } 
  15.     
  16.  public function rearAdd($node){ 
  17.   array_push($this->queue,$node); 
  18.   $this->countqueue(); 
  19.  } 
  20.    
  21.  public function rearRemove(){ 
  22.   $node = array_pop($this->queue); 
  23.   $this->countqueue(); 
  24.   return $node
  25.  } 
  26.    
  27.  public function countqueue(){ 
  28.   $this->length = count($this->queue);     
  29.  } 
  30. $fruit = new deque(); 
  31. echo $fruit -> length; 
  32. $fruit -> frontAdd("Apple"); 
  33. $fruit -> rearAdd("Watermelon"); 
  34. echo '<pre>'
  35. print_r($fruit); 
  36. echo '</pre>'
  37. ?> 
  38. /*结果 
  39. 0 
  40. deque Object 
  41. ( 
  42.     [queue] => Array 
  43.         ( 
  44.             [0] => Apple 
  45.             [1] => Watermelon 
  46.         ) 
  47.     [length] => 2 
  48. )*/ 

Tags: 队列 双向 例子

分享到: