摘要:本文主要向大家介绍了PHP语言 双向队列类,通过具体的实例向大家展示,希望对大家学习php语言有所帮助。
本文主要向大家介绍了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频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号