这篇文章主要介绍了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. class DEQue{ // class start
20. private $_queue = array(); // 对列
21. private $_maxLength = 0; // 对列最大长度，0表示不限
22. private $_type = 0; // 对列类型
23. private $_frontNum = 0; // 前端插入的数量
24. private $_rearNum = 0; // 后端插入的数量
25. /** 初始化
26. * @param $type 对列类型
27. * 1:两端均可输入输出
28. * 2:前端只能输入，后端可输入输出
29. * 3:前端只能输出，后端可输入输出
30. * 4:后端只能输入，前端可输入输出
31. * 5:后端只能输出，前端可输入输出
32. * 6:两端均可输入输出，在哪端输入只能从哪端输出
33. * @param $maxlength 对列最大长度
34. */
35. public function __construct($type=1, $maxlength=0){
36. $this->_type = in_array($type, array(1,2,3,4,5,6))? $type : 1;
37. $this->_maxLength = intval($maxlength);
38. }
39. /** 前端入列
40. * @param Mixed $data 数据
41. * @return boolean
42. */
43. public function frontAdd($data=null){
44. if($this->_type==3){ // 前端输入限制
45. return false;
46. }
47. if(isset($data) && !$this->isFull()){
48. array_unshift($this->_queue, $data);
49. $this->setAddNum(1);
50. return true;
51. }
52. return false;
53. }
54. /** 前端出列
55. * @return Array
56. */
57. public function frontRemove(){
58. if($this->_type==2){ // 前端输出限制
59. return null;
60. }
61. if(!$this->checkRemove(1)){ // 检查是否依赖输入
62. return null;
63. }
64. $data = null;
65. if($this->getLength()>0){
66. $data = array_shift($this->_queue);
67. $this->setRemoveNum(1);
68. }
69. return $data;
70. }
71. /** 后端入列
72. * @param Mixed $data 数据
73. * @return boolean
74. */
75. public function rearAdd($data=null){
76. if($this->_type==5){ // 后端输入限制
77. return false;
78. }
79. if(isset($data) && !$this->isFull()){
80. array_push($this->_queue, $data);
81. $this->setAddNum(2);
82. return true;
83. }
84. return false;
85. }
86. /** 后端出列
87. * @return Array
88. */
89. public function rearRemove(){
90. if($this->_type==4){ // 后端输出限制
91. return null;
92. }
93. if(!$this->checkRemove(2)){ // 检查是否依赖输入
94. return null;
95. }
96. $data = null;
97. if($this->getLength()>0){
98. $data = array_pop($this->_queue);
99. $this->setRemoveNum(2);
100. }
101. return $data;
102. }
103. /** 清空对列
104. * @return boolean
105. */
106. public function clear(){
107. $this->_queue = array();
108. $this->_frontNum = 0;
109. $this->_rearNum = 0;
110. return true;
111. }
112. /** 判断对列是否已满
113. * @return boolean
114. */
115. public function isFull(){
116. $bIsFull = false;
117. if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){
118. $bIsFull = true;
119. }
120. return $bIsFull;
121. }
122. /** 获取当前对列长度
123. * @return int
124. */
125. private function getLength(){
126. return count($this->_queue);
127. }
128. /** 记录入列,输出依赖输入时调用
129. * @param int $endpoint 端点 1:front 2:rear
130. */
131. private function setAddNum($endpoint){
132. if($this->_type==6){
133. if($endpoint==1){
134. $this->_frontNum ++;
135. }else{
136. $this->_rearNum ++;
137. }
138. }
139. }
140. /** 记录出列,输出依赖输入时调用
141. * @param int $endpoint 端点 1:front 2:rear
142. */
143. private function setRemoveNum($endpoint){
144. if($this->_type==6){
145. if($endpoint==1){
146. $this->_frontNum --;
147. }else{
148. $this->_rearNum --;
149. }
150. }
151. }
152. /** 检查是否输出依赖输入
153. * @param int $endpoint 端点 1:front 2:rear
154. */
155. private function checkRemove($endpoint){
156. if($this->_type==6){
157. if($endpoint==1){
158. return $this->_frontNum>0;
159. }else{
160. return $this->_rearNum>0;
161. }
162. }
163. return true;
164. }
165. } // class end
166. ?>

demo.php示例代码如下：

1. <?php
2. require "DEQue.class.php";
3. // 例子1
4. $obj = new DEQue(); // 前后端都可以输入，无限长度
5. $obj->frontAdd('a'); // 前端入列
6. $obj->rearAdd('b'); // 后端入列
7. $obj->frontAdd('c'); // 前端入列
8. $obj->rearAdd('d'); // 后端入列
9. // 入列后数组应为 cabd
10. $result = array();
11. $result[] = $obj->rearRemove(); // 后端出列
12. $result[] = $obj->rearRemove(); // 后端出列
13. $result[] = $obj->frontRemove(); // 前端出列
14. $result[] = $obj->frontRemove(); // 前端出列
15. print_r($result); // 出列顺序应为 dbca
16. // 例子2
17. $obj = new DEQue(3, 5); // 前端只能输出，后端可输入输出，最大长度5
18. $insert = array();
19. $insert[] = $obj->rearAdd('a');
20. $insert[] = $obj->rearAdd('b');
21. $insert[] = $obj->frontAdd('c'); // 因前端只能输出，因此这里会返回false
22. $insert[] = $obj->rearAdd('d');
23. $insert[] = $obj->rearAdd('e');
24. $insert[] = $obj->rearAdd('f');
25. $insert[] = $obj->rearAdd('g'); // 超过长度，返回false
26. var_dump($insert);
27. // 例子3
28. $obj = new DEQue(6); // 输出依赖输入
29. $obj->frontAdd('a');
30. $obj->frontAdd('b');
31. $obj->frontAdd('c');
32. $obj->rearAdd('d');
33. $result = array();
34. $result[] = $obj->rearRemove();
35. $result[] = $obj->rearRemove(); // 因为输出依赖输入，这个会返回NULL
36. $result[] = $obj->frontRemove();
37. $result[] = $obj->frontRemove();
38. $result[] = $obj->frontRemove();
39. //www.phpfensi.com
40. var_dump($result);
41. ?>