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.       
49. } 

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

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

Tags: 队列 双向 例子

分享到：