PHP实现一个双向队列例子

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

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

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

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

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

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

PHP实现代码如下:

<?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);  
	    } 
	      
	} 

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

<?php  
	class deque 
	{ 
	 public $queue  = array(); 
	 public $length = 0; 
	    
	 public function frontAdd($node){ 
	  array_unshift($this->queue,$node); 
	  $this->countqueue(); 
	 } 
	 public function frontRemove(){ 
	  $node = array_shift($this->queue); 
	  $this->countqueue(); 
	  return $node; 
	 } 
	    
	 public function rearAdd($node){ 
	  array_push($this->queue,$node); 
	  $this->countqueue(); 
	 } 
	   
	 public function rearRemove(){ 
	  $node = array_pop($this->queue); 
	  $this->countqueue(); 
	  return $node; 
	 } 
	   
	 public function countqueue(){ 
	  $this->length = count($this->queue);     
	 } 
	} 
	$fruit = new deque(); 
	echo $fruit -> length; 
	$fruit -> frontAdd("Apple"); 
	$fruit -> rearAdd("Watermelon"); 
	echo &#39;<pre class="brush:php;toolbar:false">&#39;; 
	print_r($fruit); 
	echo &#39;

';    /*结果  0  deque Object  (      [queue] => Array          (              [0] => Apple              [1] => Watermelon          )      [length] => 2  )*/ 

文章链接：

随便收藏，请保留本文地址！