PHP中因?yàn)閿?shù)組太過(guò)強(qiáng)大，把這些數(shù)據(jù)結(jié)構(gòu)都囊括進(jìn)來(lái)了，所以不太需要去關(guān)注這些數(shù)據(jù)結(jié)構(gòu)，久而久之這些概念也就淡化了。在PHP中有個(gè)擴(kuò)展叫Data Structures，這個(gè)擴(kuò)展包含了這些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。今天就來(lái)介紹一下。

在 PHP 中因?yàn)閿?shù)組太過(guò)強(qiáng)大，把這些數(shù)據(jù)結(jié)構(gòu)都囊括進(jìn)來(lái)了，所以不太需要去關(guān)注這些數(shù)據(jù)結(jié)構(gòu)，久而久之這些概念也就淡化了，不是說(shuō) PHP 中沒(méi)有數(shù)據(jù)結(jié)構(gòu)。

在 PHP 中有個(gè)擴(kuò)展 Data Structures，這個(gè)擴(kuò)展包含了這些常見(jiàn)的 數(shù)據(jù)結(jié)構(gòu)。

PHP 數(shù)據(jù)結(jié)構(gòu)

• 優(yōu)先級(jí)隊(duì)列 PriorityQueue

• 雙端隊(duì)列 Deque

• 隊(duì)列 FIFO(先進(jìn)先出)

• 棧 LIFO(先進(jìn)后出)

• 散列表 Hash

• Set 集合
• Map 字典

數(shù)據(jù)結(jié)構(gòu)介紹

優(yōu)先級(jí)隊(duì)列 PriorityQueue

PriorityQueue 與 Queue 非常相似。 值被推入具有指定優(yōu)先級(jí)的隊(duì)列中，具有最高優(yōu)先級(jí)的值將始終位于隊(duì)列的前面。

注意

• 對(duì)于具有相同優(yōu)先級(jí)的值，保留“先進(jìn)先出”順序。

• 迭代 PriorityQueue 是破壞性的，相當(dāng)于連續(xù)彈出操作，直到隊(duì)列為空。

設(shè)置容量

默認(rèn)容量是 8，可以手動(dòng)設(shè)置容量,這個(gè)容量不是指隊(duì)列的長(zhǎng)度，而是說(shuō)存儲(chǔ)空間。再分配容量時(shí)確保有足夠的內(nèi)存

如果該值小于或等于當(dāng)前容量，容量將保持不變。

$queue = new DsPriorityQueue();  $queue->allocate(8);

獲取容量

當(dāng)前手動(dòng)設(shè)置了容量時(shí)，如果設(shè)置的容量大于實(shí)際占用容量，則返回設(shè)置的容量。反之，返回實(shí)際的容量。

$queue = new DsPriorityQueue();  // 此時(shí)返回默認(rèn)值 8 $queue->capacity();

設(shè)置優(yōu)先級(jí)

數(shù)值越大優(yōu)先級(jí)越高

$queue = new DsPriorityQueue();  $queue->push('value1', 1); $queue->push('value2', 2);

示例

$queue = new DsPriorityQueue();  $queue->push('沙僧', 2); $queue->push('唐僧', 5); $queue->push('白龍馬', 1); $queue->push('豬八戒', 3); $queue->push('孫悟空', 4); $cout = $queue->count(); for($i=0; $i<$cout; $i++) {   echo $queue->pop();   echo PHP_EOL; }

輸出

唐僧 孫悟空 豬八戒 沙僧 白龍馬

應(yīng)用場(chǎng)景

• MySQL 查詢(xún)時(shí)為了加快查詢(xún)速度，避免排序無(wú)法使用索引，沒(méi)有進(jìn)行排序，在服務(wù)端代碼層面進(jìn)行手動(dòng)排序再返回。

• 其他應(yīng)用場(chǎng)景…

雙端隊(duì)列 Deque

有兩個(gè)指針?lè)謩e指向頭部和尾部。分別可以在頭部和尾部進(jìn)行插入和彈出。

優(yōu)點(diǎn)

• 支持?jǐn)?shù)組語(yǔ)法（方括號(hào)）。

• 對(duì)于相同數(shù)量的值，比數(shù)組占用更少的內(nèi)存。

• 當(dāng)其大小下降到足夠低時(shí)，自動(dòng)釋放分配的內(nèi)存。

• get()、set()、push()、pop()、shift()和unshift()都是O(1)。

缺點(diǎn)

• 設(shè)置的容量數(shù)值，必須是 2 的冪次方值，默認(rèn)值是 8。比如2^2

• insert()和remove()是O(n)。

類(lèi)方法說(shuō)明

雙端隊(duì)列 Deque

示例

$deque = new DsDeque(); $deque->push(...['唐僧', '孫悟空', '豬八戒', '沙僧', '白龍馬']); $clone = $deque->copy(); $count = $deque->count(); echo '頭：'.$deque->first().PHP_EOL; echo '尾：'.$deque->last().PHP_EOL; echo '--- 從隊(duì)尾開(kāi)始 ----'.PHP_EOL; for($i=0; $i<$count; $i++) {     echo $deque->pop();     echo PHP_EOL; }  echo '--- 從隊(duì)頭開(kāi)始 ----'.PHP_EOL; for($i=0; $i<$count; $i++) {     echo $clone->shift();     echo PHP_EOL; }

輸出

頭：唐僧 尾：白龍馬 --- 從隊(duì)尾開(kāi)始 ---- 白龍馬 沙僧 豬八戒 孫悟空 唐僧 --- 從隊(duì)頭開(kāi)始 ---- 唐僧 孫悟空 豬八戒 沙僧 白龍馬

應(yīng)用場(chǎng)景

• 多種應(yīng)用場(chǎng)景

隊(duì)列 FIFO(先進(jìn)先出)

隊(duì)列是“先進(jìn)先出”或“FIFO”集合，它只允許訪問(wèn)隊(duì)列前面的值。

示例

$queue = new DsQueue();  $queue->push('唐僧'); $queue->push(...['孫悟空', '豬八戒']); $queue->push(['沙僧', '白龍馬']); print_r($queue);

輸出

DsQueue Object (     [0] => 唐僧     [1] => 孫悟空     [2] => 豬八戒     [3] => Array         (             [0] => 沙僧             [1] => 白龍馬         ) )

棧 LIFO(先進(jìn)后出)

Stack 是一個(gè)“后進(jìn)先出”或“LIFO”集合，它只允許訪問(wèn)結(jié)構(gòu)頂部的值。

示例

$Stack = new DsStack();  $Stack->push('唐僧'); $Stack->push(...['孫悟空', '豬八戒']); $Stack->push(...['沙僧', '白龍馬']);  $cout = $Stack->count(); for($i=0; $i<$cout; $i++) {     echo $Stack->pop();     echo PHP_EOL; }

輸出

白龍馬 沙僧 豬八戒 孫悟空 唐僧

Map 字典

Map 是鍵值對(duì) [key=>value] 的順序集合，與數(shù)組相似。 鍵可以是任何類(lèi)型，但必須是唯一的。 如果使用相同的鍵將值添加到地圖，后添加的則會(huì)替換之前的值。

優(yōu)點(diǎn)

• 鍵和值可以是任何類(lèi)型，包括對(duì)象

• 支持?jǐn)?shù)組語(yǔ)法。

• 保留插入順序。

• 性能和內(nèi)存效率與數(shù)據(jù)相似。

• 當(dāng)大小下降到足夠低時(shí)自動(dòng)釋放分配的內(nèi)存。

缺點(diǎn)

• 當(dāng)對(duì)象作為鍵時(shí)，不能轉(zhuǎn)換為數(shù)組。

Set 集合

Set 是一系列唯一值，只有一組 key 不存儲(chǔ) value，而且 key 不能重復(fù)。

優(yōu)點(diǎn)

• 值可以是任何類(lèi)型，包括對(duì)象。

• 支持?jǐn)?shù)組語(yǔ)法。

• 保留插入順序。

• 當(dāng)大小下降到足夠低時(shí)自動(dòng)釋放分配的內(nèi)存。

• add()、remove()和contains()復(fù)雜度都是O(1)。

缺點(diǎn)

• 不支持push()、pop()、insert()、shift()或unshift()

• 如果在被訪問(wèn)的索引之前緩沖區(qū)中有被刪除的值，則get()為O(n)，否則為O(1)。

Map 和 Set 的區(qū)別

• 存儲(chǔ)方式不同。Map 存儲(chǔ)的是 [key => value] 形式，Set 存儲(chǔ)的是 […keys];

• Map 和 Set 都是通過(guò) key 來(lái)保證有序性的，所以是不允許修改 key 的。

推薦學(xué)習(xí)：php視頻教程