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. )*/