本文主要向大家介绍了PHP语言 双向队列类，通过具体的实例向大家展示，希望对大家学习php语言有所帮助。

（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双向队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

在实际使用中，还可以有输出受限的双向队列（即一个端点允许插入和删除，另一个端点只允许插入的双向队列）和输入受限的双向队列（即一个端点允许插入和删除，另一个端点只允许删除的双向队列）。而如果限定双向队列从某个端点插入的元素只能从该端点删除，则该双向队列就蜕变为两个栈底相邻的栈了。

DEQue.class.php

[php] view plain copy

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.   

64.         return false;  

65.   

66.     }  

67.   

68.   

69.     /** 前端出列 

70.     * @return Array 

71.     */  

72.     public function frontRemove(){  

73.   

74.         if($this->_type==2){ // 前端输出限制  

75.             return null;  

76.         }  

77.   

78.         if(!$this->checkRemove(1)){ // 检查是否依赖输入  

79.             return null;  

80.         }  

81.   

82.         $data = null;  

83.   

84.         if($this->getLength()>0){  

85.   

86.             $data = array_shift($this->_queue);  

87.   

88.             $this->setRemoveNum(1);  

89.   

90.         }  

91.   

92.         return $data;  

93.   

94.     }  

95.   

96.   

97.     /** 后端入列 

98.     * @param  Mixed   $data 数据 

99.     * @return boolean 

100.     */  

101.     public function rearAdd($data=null){  

102.   

103.         if($this->_type==5){ // 后端输入限制  

104.             return false;  

105.         }  

106.   

107.         if(isset($data) && !$this->isFull()){  

108.   

109.             array_push($this->_queue, $data);  

110.   

111.             $this->setAddNum(2);  

112.   

113.             return true;  

114.   

115.         }  

116.   

117.         return false;  

118.     }  

119.   

120.   

121.     /** 后端出列 

122.     * @return Array 

123.     */  

124.     public function rearRemove(){  

125.   

126.         if($this->_type==4){ // 后端输出限制  

127.             return null;  

128.         }  

129.   

130.         if(!$this->checkRemove(2)){ // 检查是否依赖输入  

131.             return null;  

132.         }  

133.   

134.         $data = null;  

135.   

136.         if($this->getLength()>0){  

137.   

138.             $data = array_pop($this->_queue);  

139.   

140.             $this->setRemoveNum(2);  

141.   

142.         }  

143.   

144.         return $data;  

145.   

146.     }  

147.   

148.   

149.     /** 清空对列 

150.     * @return boolean 

151.     */  

152.     public function clear(){  

153.         $this->_queue = array();  

154.         $this->_frontNum = 0;  

155.         $this->_rearNum = 0;  

156.         return true;  

157.     }  

158.   

159.   

160.     /** 判断对列是否已满 

161.     * @return boolean 

162.     */  

163.     public function isFull(){  

164.         $bIsFull = false;  

165.         if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){  

166.             $bIsFull = true;  

167.         }  

168.         return $bIsFull;  

169.     }  

170.   

171.   

172.     /** 获取当前对列长度 

173.     * @return int 

174.     */  

175.     private function getLength(){  

176.         return count($this->_queue);  

177.     }  

178.   

179.   

180.     /** 记录入列,输出依赖输入时调用 

181.     * @param int $endpoint 端点 1:front 2:rear 

182.     */  

183.     private function setAddNum($endpoint){  

184.         if($this->_type==6){  

185.             if($endpoint==1){  

186.                 $this->_frontNum ++;  

187.             }else{  

188.                 $this->_rearNum ++;  

189.             }  

190.         }  

191.     }  

192.   

193.   

194.     /** 记录出列,输出依赖输入时调用 

195.     * @param int $endpoint 端点 1:front 2:rear 

196.     */  

197.     private function setRemoveNum($endpoint){  

198.         if($this->_type==6){  

199.             if($endpoint==1){  

200.                 $this->_frontNum --;  

201.             }else{  

202.                 $this->_rearNum --;  

203.             }  

204.         }  

205.     }  

206.   

207.   

208.     /** 检查是否输出依赖输入 

209.     * @param int $endpoint 端点 1:front 2:rear 

210.     */  

211.     private function checkRemove($endpoint){  

212.         if($this->_type==6){  

213.             if($endpoint==1){  

214.                 return $this->_frontNum>0;  

215.             }else{  

216.                 return $this->_rearNum>0;  

217.             }  

218.         }  

219.         return true;  

220.     }  

221.   

222. } // class end  

223.   

224. ?>  

demo.php

[php] view plain copy

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.   

54. var_dump($result);  

55.   

56. ?>  

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言PHP频道！