鏈表的兩頭連接，形成了一個環(huán)狀鏈表，稱為循環(huán)鏈表。
創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的尉犁網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
約瑟夫環(huán)問題，是一個經(jīng)典的循環(huán)鏈表問題，題意是：已知 n 個人（以編號1，2，3，…，n分別表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數(shù)，數(shù)到 m 的那個人出列；他的下一個人又從 1 還是順時針開始報數(shù)，數(shù)到 m 的那個人又出列；依次重復(fù)下去，要求找到最后出列的那個人。
例如有 5 個人，要求從編號為 3 的人開始，數(shù)到 2 的那個人出列：
出列順序依次為：
編號為 3 的人開始數(shù) 1，然后 4 數(shù) 2，所以 4 先出列；
4 出列后，從 5 開始數(shù) 1，1 數(shù) 2，所以 1 出列；
1 出列后，從 2 開始數(shù) 1，3 數(shù) 2，所以 3 出列；
3 出列后，從 5 開始數(shù) 1，2 數(shù) 2，所以 2 出列；
最后只剩下 5 自己，所以 5 出列。
循環(huán)鏈表和動態(tài)鏈表唯一不同在于它的首尾連接，這也注定了在使用循環(huán)鏈表時，附帶的最多的操作就是遍歷鏈表。在遍歷的過程中，尤其要注意循環(huán)鏈表雖然首尾相連，但并不表示該鏈表沒有第一個節(jié)點(diǎn)和最后一個結(jié)點(diǎn)。所以，不要隨意改變頭指針的指向。
整個鏈表只能單方向從表頭訪問到表尾，這種結(jié)構(gòu)的鏈表統(tǒng)稱為 “單向鏈表”或“單鏈表”。
如果算法中需要頻繁地找某結(jié)點(diǎn)的前趨結(jié)點(diǎn)，單鏈表的解決方式是遍歷整個鏈表，增加算法的時間復(fù)雜度，影響整體效率。
為了快速便捷地解決這類問題，在單向鏈表的基礎(chǔ)上，給各個結(jié)點(diǎn)額外配備一個指針變量，用于指向每個結(jié)點(diǎn)的直接前趨元素。這樣的鏈表被稱為“雙向鏈表”或者“雙鏈表”。
雙向鏈表中的結(jié)點(diǎn)有兩個指針域，一個指向直接前趨，一個指向直接后繼。（鏈表中第一個結(jié)點(diǎn)的前趨結(jié)點(diǎn)為NULL，最后一個結(jié)點(diǎn)的后繼結(jié)點(diǎn)為NULL）
結(jié)點(diǎn)的具體構(gòu)成：
雙向鏈表創(chuàng)建的過程中，每一個結(jié)點(diǎn)需要初始化數(shù)據(jù)域和兩個指針域，一個指向直接前趨結(jié)點(diǎn)，另一個指向直接后繼結(jié)點(diǎn)。
創(chuàng)建一個雙向鏈表line（1，2，3）：
比如在（1，2，3）中插入一個結(jié)點(diǎn) 4，變成（1，4，2，3）。
實(shí)現(xiàn)效果圖：
在雙向鏈表中插入數(shù)據(jù)時，首先完成圖中標(biāo)注為 1 的兩步操作，然后完成標(biāo)注為 2 的兩步操作；反之，如果先完成 2，就無法通過頭指針訪問結(jié)點(diǎn) 2，需要額外增設(shè)指針，雖然能實(shí)現(xiàn)，但較前一種麻煩。
雙鏈表刪除結(jié)點(diǎn)時，直接遍歷鏈表，找到要刪除的結(jié)點(diǎn)，然后利用該結(jié)點(diǎn)的兩個指針域完成刪除操作。
在（1，4，2，3）中刪除結(jié)點(diǎn) 2：
雙向鏈表的查找操作和單鏈表的實(shí)現(xiàn)方法完全一樣，從鏈表的頭結(jié)點(diǎn)或者首元結(jié)點(diǎn)開始遍歷，這里不做過多解釋。
更改鏈表中某結(jié)點(diǎn)的數(shù)據(jù)域的操作是在查找的基礎(chǔ)上完成的。通過遍歷找到存儲有該數(shù)據(jù)元素的結(jié)點(diǎn)后，直接更改其數(shù)據(jù)域就可以。
其實(shí)就是雙向鏈表和循環(huán)鏈表的結(jié)合體
例如：約瑟夫環(huán)問題其實(shí)還可以這樣玩：如果順時針報數(shù)，有人出列后，順時針找出出列位置的下一個人，開始反方向（也就是逆時針）報數(shù)，有人出列后，逆時針找出出列位置的下一個人，開始順時針報數(shù)。依次重復(fù)，直至最后一個出列。
有興趣可以自行嘗試，這里就不再分析了，因?yàn)楸举|(zhì)就是雙向鏈表和循環(huán)鏈表。
不建議直接用php來做隊(duì)列，php的array操作雖然勉強(qiáng)能做偽隊(duì)列，但問題也來了，如果是大量的數(shù)據(jù)呢？php會不會內(nèi)存問題直接掛了？
建議：測試的話用用還湊合，但真正去用的話雙向隊(duì)列，用redis的list類型吧，可以滿足你的需求，同時數(shù)量級上也不是問題，單向隊(duì)列
httpsqs，rabbitmq等
再看看別人怎么說的。
隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)更簡單，就像我們生活中排隊(duì)一樣，它的特性是先進(jìn)先出(FIFO)。
PHP
SPL中SplQueue類就是實(shí)現(xiàn)隊(duì)列操作，和棧一樣，它也可以繼承雙鏈表(SplDoublyLinkedList)輕松實(shí)現(xiàn)。
SplQueue類摘要如下：
SplQueue簡單使用如下：
復(fù)制代碼
代碼如下:
$queue
=
new
SplQueue();
/**
*
可見隊(duì)列和雙鏈表的區(qū)別就是IteratorMode改變了而已，棧的IteratorMode只能為：
*
（1）SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_KEEP
（默認(rèn)值,迭代后數(shù)據(jù)保存）
*
（2）SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE
（迭代后數(shù)據(jù)刪除）
*/
$queue-setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE);
//SplQueue::enqueue()其實(shí)就是
SplDoublyLinkedList::push()
$queue-enqueue('a');
$queue-enqueue('b');
$queue-enqueue('c');
//SplQueue::dequeue()其實(shí)就是
SplDoublyLinkedList::shift()
print_r($queue-dequeue());
foreach($queue
as
$item)
{
echo
$item
.
PHP_EOL;
}
print_r($queue);
而優(yōu)先隊(duì)列SplPriorityQueue是基于堆(后文介紹)實(shí)現(xiàn)的。
SplPriorityQueue的類摘要如下：
SplPriorityQueue簡單使用：
$pq
=
new
SplPriorityQueue();
$pq-insert('a',
10);
$pq-insert('b',
1);
$pq-insert('c',
8);
echo
$pq-count()
.PHP_EOL;
//3
echo
$pq-current()
.
PHP_EOL;
//a
/**
*
設(shè)置元素出隊(duì)模式
*
SplPriorityQueue::EXTR_DATA
僅提取值
*
SplPriorityQueue::EXTR_PRIORITY
僅提取優(yōu)先級
*
SplPriorityQueue::EXTR_BOTH
提取數(shù)組包含值和優(yōu)先級
*/
$pq-setExtractFlags(SplPriorityQueue::EXTR_DATA);
while($pq-valid())
{
print_r($pq-current());
//a
c
b
$pq-next();
}
C語言是所有高級編程語言的入門語言，所以數(shù)據(jù)結(jié)構(gòu)中算法一般都使用C語言來表示，這樣大家都能看懂。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法是與語言無關(guān)的，C語言只是它實(shí)現(xiàn)的一種方式，不用太在乎的。建議你把C語言的基礎(chǔ)知識學(xué)習(xí)一下，這樣看起來就不會太累了。
數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計算機(jī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。 數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。
使用php實(shí)現(xiàn)的基本的數(shù)據(jù)結(jié)構(gòu)和算法，什么二叉樹、二叉搜索樹、AVL樹、B樹、鏈表和常見排序、搜索算法等等，而且全部是使用面向?qū)ο髞韺?shí)現(xiàn)的，確是是很強(qiáng)。
數(shù)組就是典型的數(shù)據(jù)結(jié)構(gòu)了，使用數(shù)組操作函數(shù)，就可以實(shí)現(xiàn)單向和多向隊(duì)列了。 操作函數(shù)有： array_shift array_unshift array_push array_pop
重慶分公司
重慶分公司
