这篇文章主要介绍了php实现的双向队列类,是数据结构中非常重要的一个数据结构类型,需要的朋友可以参考下

本文实例讲述了php实现的双向队列类及其用法，对于PHP数据结构与算法的学习有不错的参考价值。分享给大家供大家参考。具体分析如下：

（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($type, array(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. //www.phpfensi.com 
54. var_dump($result);  
55.    
56. ?> 
57.  

出处：http://www.phpfensi.com/php/20210414/14276.html