本文實例講述了php實現的雙向隊列類及其用法，對于PHP數據結構與算法的學習有不錯的參考價值。分享給大家供大家參考。具體分析如下：
（deque，全名double-ended queue）是一種具有隊列和棧的性質的數據結構。雙向隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。
在實際使用中，還可以有輸出受限的雙向隊列（即一個端點允許插入和刪除，另一個端點只允許插入的雙向隊列）和輸入受限的雙向隊列（即一個端點允許插入和刪除，另一個端點只允許刪除的雙向隊列）。而如果限定雙向隊列從某個端點插入的元素只能從該端點刪除，則該雙向隊列就蛻變為兩個棧底相鄰的棧了。
DEQue.class.php類文件如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
<?php /** php 雙向隊列。支持限定隊列長度，輸入受限，輸出受限，及輸出必須與輸入同端幾種設置 * Date: 2014-04-30 * Author: fdipzone * Ver: 1.0 * * Func: * public frontAdd 前端入列 * public frontRemove 前端出列 * public rearAdd 后端入列 * pulbic rearRemove 后端出列 * public clear 清空對列 * public isFull 判斷對列是否已滿 * private getLength 獲取對列長度 * private setAddNum 記錄入列,輸出依賴輸入時調用 * private setRemoveNum 記錄出列,輸出依賴輸入時調用 * private checkRemove 檢查是否輸出依賴輸入 */ class DEQue{ // class start private $_queue = array(); // 對列 private $_maxLength = 0; // 對列最大長度，0表示不限 private $_type = 0; // 對列類型 private $_frontNum = 0; // 前端插入的數量 private $_rearNum = 0; // 后端插入的數量 /** 初始化 * @param $type 對列類型 * 1:兩端均可輸入輸出 * 2:前端只能輸入，后端可輸入輸出 * 3:前端只能輸出，后端可輸入輸出 * 4:后端只能輸入，前端可輸入輸出 * 5:后端只能輸出，前端可輸入輸出 * 6:兩端均可輸入輸出，在哪端輸入只能從哪端輸出 * @param $maxlength 對列最大長度 */ public function __construct($type=1, $maxlength=0){ $this->_type = in_array($type, array(1,2,3,4,5,6))? $type : 1; $this->_maxLength = intval($maxlength); } /** 前端入列 * @param Mixed $data 數據 * @return boolean */ public function frontAdd($data=null){ if($this->_type==3){ // 前端輸入限制 return false; } if(isset($data) && !$this->isFull()){ array_unshift($this->_queue, $data); $this->setAddNum(1); return true; } return false; } /** 前端出列 * @return Array */ public function frontRemove(){ if($this->_type==2){ // 前端輸出限制 return null; } if(!$this->checkRemove(1)){ // 檢查是否依賴輸入 return null; } $data = null; if($this->getLength()>0){ $data = array_shift($this->_queue); $this->setRemoveNum(1); } return $data; } /** 后端入列 * @param Mixed $data 數據 * @return boolean */ public function rearAdd($data=null){ if($this->_type==5){ // 后端輸入限制 return false; } if(isset($data) && !$this->isFull()){ array_push($this->_queue, $data); $this->setAddNum(2); return true; } return false; } /** 后端出列 * @return Array */ public function rearRemove(){ if($this->_type==4){ // 后端輸出限制 return null; } if(!$this->checkRemove(2)){ // 檢查是否依賴輸入 return null; } $data = null; if($this->getLength()>0){ $data = array_pop($this->_queue); $this->setRemoveNum(2); } return $data; } /** 清空對列 * @return boolean */ public function clear(){ $this->_queue = array(); $this->_frontNum = 0; $this->_rearNum = 0; return true; } /** 判斷對列是否已滿 * @return boolean */ public function isFull(){ $bIsFull = false; if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){ $bIsFull = true; } return $bIsFull; } /** 獲取當前對列長度 * @return int */ private function getLength(){ return count($this->_queue); } /** 記錄入列,輸出依賴輸入時調用 * @param int $endpoint 端點 1:front 2:rear */ private function setAddNum($endpoint){ if($this->_type==6){ if($endpoint==1){ $this->_frontNum ++; }else{ $this->_rearNum ++; } } } /** 記錄出列,輸出依賴輸入時調用 * @param int $endpoint 端點 1:front 2:rear */ private function setRemoveNum($endpoint){ if($this->_type==6){ if($endpoint==1){ $this->_frontNum --; }else{ $this->_rearNum --; } } } /** 檢查是否輸出依賴輸入 * @param int $endpoint 端點 1:front 2:rear */ private function checkRemove($endpoint){ if($this->_type==6){ if($endpoint==1){ return $this->_frontNum>0; }else{ return $this->_rearNum>0; } } return true; } } // class end ?> |
demo.php示例代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
<?php require "DEQue.class.php"; // 例子1 $obj = new DEQue(); // 前后端都可以輸入，無限長度 $obj->frontAdd('a'); // 前端入列 $obj->rearAdd('b'); // 后端入列 $obj->frontAdd('c'); // 前端入列 $obj->rearAdd('d'); // 后端入列 // 入列后數組應為 cabd $result = array(); $result[] = $obj->rearRemove(); // 后端出列 $result[] = $obj->rearRemove(); // 后端出列 $result[] = $obj->frontRemove(); // 前端出列 $result[] = $obj->frontRemove(); // 前端出列 print_r($result); // 出列順序應為 dbca // 例子2 $obj = new DEQue(3, 5); // 前端只能輸出，后端可輸入輸出，最大長度5 $insert = array(); $insert[] = $obj->rearAdd('a'); $insert[] = $obj->rearAdd('b'); $insert[] = $obj->frontAdd('c'); // 因前端只能輸出，因此這里會返回false $insert[] = $obj->rearAdd('d'); $insert[] = $obj->rearAdd('e'); $insert[] = $obj->rearAdd('f'); $insert[] = $obj->rearAdd('g'); // 超過長度，返回false var_dump($insert); // 例子3 $obj = new DEQue(6); // 輸出依賴輸入 $obj->frontAdd('a'); $obj->frontAdd('b'); $obj->frontAdd('c'); $obj->rearAdd('d'); $result = array(); $result[] = $obj->rearRemove(); $result[] = $obj->rearRemove(); // 因為輸出依賴輸入，這個會返回NULL $result[] = $obj->frontRemove(); $result[] = $obj->frontRemove(); $result[] = $obj->frontRemove(); var_dump($result); ?> |
完整實例代碼點擊此處本站下載。
希望本文所述對大家PHP程序算法設計的學習有所幫助。
