今天，我們就來學(xué)習(xí)另外一個(gè)也是非常經(jīng)典的邏輯結(jié)構(gòu)類型：隊(duì)列。相信不少同學(xué)已經(jīng)使用過 redis 、 rabbitmq 之類的緩存隊(duì)列工具。其實(shí)，數(shù)據(jù)庫、程序代碼，這些都可以實(shí)現(xiàn)隊(duì)列的操作，就和棧一樣，隊(duì)列也是有其特定的規(guī)則，只要符合這個(gè)規(guī)則，它就叫做隊(duì)列。

什么是隊(duì)列？

相對于棧來說，隊(duì)列是一種先進(jìn)先出（FIFO）的順序邏輯結(jié)構(gòu)。什么叫先進(jìn)先出呢？就和我們的排隊(duì)一樣，當(dāng)我們?nèi)ャy行或者醫(yī)院的時(shí)候，總是要在門口取一個(gè)號，這個(gè)號是按順序叫的。先來的人就可以先辦業(yè)務(wù)或者看病，這就是一個(gè)典型的隊(duì)列。同理，日常的排隊(duì)就是一個(gè)標(biāo)準(zhǔn)的隊(duì)列模式。

如果有插隊(duì)的，在有正當(dāng)理由的情況下，我們可以認(rèn)為它的優(yōu)先級更高，這是隊(duì)列中元素的一種特殊形式。就像我們會(huì)在等地鐵或者公交的時(shí)候讓孕婦優(yōu)先，在排隊(duì)買火車票的時(shí)候也有軍人的優(yōu)先窗口。不過，這個(gè)并不在我們這次的討論范圍之內(nèi)。

在公交站排隊(duì)時(shí)，排第一個(gè)的當(dāng)然可以第一個(gè)上車，然后依次。這時(shí)，你來到了公交站，那么你只能排到最后一位。這個(gè)就是隊(duì)列的具體表現(xiàn)形式。

同樣，和棧一樣，也有一些名詞我們需要了解。當(dāng)你來到公交站并排到最后一位時(shí)，這個(gè)操作叫作“入隊(duì)”。當(dāng)公交車進(jìn)站后，第一位乘客上車，這個(gè)操作叫做“出隊(duì)”。第一位乘客所處的位置叫做“隊(duì)頭”，你做為當(dāng)前隊(duì)列的最后一位乘客，你的位置就叫做“隊(duì)尾”?；氐酱a邏輯上面來看，也就是說隊(duì)列是從“隊(duì)尾”“入隊(duì)”，從“隊(duì)頭”“出隊(duì)”。

順序隊(duì)列

OK，我們還是直接從來代碼來看，首先看到的依然是順序隊(duì)的實(shí)現(xiàn)。

class SqQueue{     public $data;     public $front;     public $rear; }

既然是順序隊(duì)，我們依然還是用一個(gè)數(shù)組 data 來表示隊(duì)內(nèi)的元素。然后定義兩個(gè)指針 front 和 rear 來表示隊(duì)頭和隊(duì)尾。因?yàn)槭琼樞蜿?duì)，所以這里的指針其實(shí)也就是保存的是數(shù)組的下標(biāo)。接下來的操作其實(shí)就非常的簡單了，“入隊(duì)”時(shí) rear++ ，“出隊(duì)”時(shí) front++ 。

function InitSqQueue(){     $queue = new SqQueue();     $queue->data = [];     $queue->front = 0;     $queue->rear = 0;     return $queue; }  function EnSqQueue(SqQueue &$queue, $e){     $queue->data[$queue->rear] = $e;     $queue->rear ++; }  function DeSqQueue(SqQueue &$queue){     // 隊(duì)列為空     if($queue->front == $queue->rear){         return false;     }     $e = $queue->data[$queue->front];     $queue->front++;     return $e; }  $q = InitSqQueue(); EnSqQueue($q, 'A'); EnSqQueue($q, 'B'); print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => A //             [1] => B //         )  //     [front] => 0 //     [rear] => 2 // )

是不是感覺學(xué)過了棧之后，隊(duì)列也很好理解了。初始化隊(duì)列時(shí)，就是讓隊(duì)頭和隊(duì)尾指針都是 0 下標(biāo)的記錄就可以了。入隊(duì)的時(shí)候讓隊(duì)尾增加，在這段代碼中，我們?nèi)腙?duì)了兩個(gè)元素，打印出來的順序隊(duì)列內(nèi)容就如注釋所示。

EnSqQueue($q, 'C'); EnSqQueue($q, 'D'); EnSqQueue($q, 'E'); print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => A //             [1] => B //             [2] => C //             [3] => D //             [4] => E //         )  //     [front] => 0 //     [rear] => 5 // )  echo DeSqQueue($q), PHP_EOL; // A echo DeSqQueue($q), PHP_EOL; // B echo DeSqQueue($q), PHP_EOL; // C echo DeSqQueue($q), PHP_EOL; // D echo DeSqQueue($q), PHP_EOL; // E  echo DeSqQueue($q), PHP_EOL; //   print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => A //             [1] => B //             [2] => C //             [3] => D //             [4] => E  //         )  //     [front] => 5 //     [rear] => 5 // )

出隊(duì)的時(shí)候，就讓 front 進(jìn)行加 1 操作。不過，在出隊(duì)的時(shí)候還需要判斷數(shù)組中的元素是否全部出隊(duì)了，在這里，我們只用了一個(gè)非常簡單的判斷條件，那就是 front 和 rear 是否相等來判斷隊(duì)列是否空了。大家可以通過一個(gè)圖示來輔助對代碼的理解。

循環(huán)隊(duì)列

相信已經(jīng)有不少同學(xué)看出來了。隊(duì)列操作只是修改隊(duì)頭和隊(duì)尾的指針記錄，但是數(shù)組會(huì)一直增加，這樣如果一直增加的話，就會(huì)導(dǎo)致這一個(gè)數(shù)組占滿內(nèi)存，這肯定不是一個(gè)好的隊(duì)列實(shí)現(xiàn)。其實(shí)，在 C 語言中，數(shù)組就是要給一個(gè)固定的長度的。而 PHP 中的數(shù)組更像是一個(gè) Hash 結(jié)構(gòu)，所以它是可以無限增長的，并不需要我們在一開始定義一個(gè)具體的數(shù)組長度。

這也是 PHP 的方便之處，不過如果我們不想浪費(fèi)內(nèi)存空間的話，應(yīng)該怎么辦呢？就像在 C 語言中一樣，我們在 PHP 中也為數(shù)組指定一個(gè)長度，并且使用非常經(jīng)典的“循環(huán)隊(duì)列”來解決隊(duì)列數(shù)組的存儲問題。就像下圖所示：

其實(shí)意思就是，在有限的數(shù)組空間范圍內(nèi)，當(dāng)我們達(dá)到數(shù)組的最大值時(shí)，將新的數(shù)據(jù)保存回之前的下標(biāo)位置。比如圖中我們有 6 個(gè)元素，當(dāng)前隊(duì)頭在 2 下標(biāo)，隊(duì)尾在 5 下標(biāo)。如果我們?nèi)腙?duì)一個(gè)元素，隊(duì)尾移動(dòng)到 6 下標(biāo)。再添加一個(gè)元素的話，隊(duì)尾移動(dòng)回 0 下標(biāo)，如果繼續(xù)添加的話，當(dāng)隊(duì)尾下標(biāo)等于隊(duì)頭下標(biāo)減 1 的時(shí)候，我們就認(rèn)為這個(gè)隊(duì)列已經(jīng)滿了，不能再增加元素了。

同理，出隊(duì)操作的時(shí)候我們也是循環(huán)地操作隊(duì)頭元素，當(dāng)隊(duì)頭元素到 6 的下標(biāo)后，繼續(xù)出隊(duì)的話，也會(huì)回到 0 下標(biāo)的位置繼續(xù)出隊(duì)。當(dāng)隊(duì)頭和隊(duì)尾相等時(shí)，當(dāng)前的隊(duì)列也可以判定為空隊(duì)列了。

由此，我們可以看出，循環(huán)隊(duì)列相比普通的線性隊(duì)列來說，多了一個(gè)隊(duì)滿的狀態(tài)。我們還是直接從代碼中來看看這個(gè)隊(duì)滿的條件是如何判斷的。

define('MAX_QUEUE_LENGTH', 6);  function EnSqQueueLoop(SqQueue &$queue, $e){     // 判斷隊(duì)列是否滿了     if(($queue->rear + 1) % MAX_QUEUE_LENGTH == $queue->front){         return false;     }     $queue->data[$queue->rear] = $e;     $queue->rear = ($queue->rear + 1) % MAX_QUEUE_LENGTH; // 改成循環(huán)下標(biāo) }  function DeSqQueueLoop(SqQueue &$queue){     // 隊(duì)列為空     if($queue->front == $queue->rear){         return false;     }     $e = $queue->data[$queue->front];     $queue->front = ($queue->front + 1) % MAX_QUEUE_LENGTH; // 改成循環(huán)下標(biāo)     return $e; }  $q = InitSqQueue(); EnSqQueueLoop($q, 'A'); EnSqQueueLoop($q, 'B'); EnSqQueueLoop($q, 'C'); EnSqQueueLoop($q, 'D'); EnSqQueueLoop($q, 'E');  EnSqQueueLoop($q, 'F');  print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => A //             [1] => B //             [2] => C //             [3] => D //             [4] => E //             [5] =>   // 尾 //         )  //     [front] => 0 //     [rear] => 5 // )  echo DeSqQueueLoop($q), PHP_EOL; echo DeSqQueueLoop($q), PHP_EOL; print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => A //             [1] => B //             [2] => C // 頭 //             [3] => D //             [4] => E //             [5] =>   // 尾 //         )  //     [front] => 2 //     [rear] => 5 // )  EnSqQueueLoop($q, 'F'); EnSqQueueLoop($q, 'G');  EnSqQueueLoop($q, 'H'); print_r($q); // SqQueue Object // ( //     [data] => Array //         ( //             [0] => G //             [1] => B // 尾 //             [2] => C // 頭 //             [3] => D //             [4] => E //             [5] => F //         )  //     [front] => 2 //     [rear] => 1 // )

出、入隊(duì)的下標(biāo)移動(dòng)以及隊(duì)滿的判斷，都是以 (queue->rear + 1) % MAX_QUEUE_LENGTH 這個(gè)形式進(jìn)行的。根據(jù)隊(duì)列長度的取模來獲取當(dāng)前的循環(huán)下標(biāo)，是不是非常地巧妙。不得不感慨先人的智慧呀！當(dāng)然，這也是基本的數(shù)學(xué)原理哦，所以，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)還是要復(fù)習(xí)一下數(shù)學(xué)相關(guān)的知識哦！

鏈?zhǔn)疥?duì)列

順序隊(duì)列有沒有看懵？沒關(guān)系，隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)其實(shí)相比順序結(jié)構(gòu)還要簡單一些，因?yàn)樗娴闹恍枰僮麝?duì)頭和隊(duì)尾的指針而已，別的真的就不太需要考慮了。而且這個(gè)指針就是真的指向具體對象的指針了。

class LinkQueueNode{     public $data;     public $next; }  class LinkQueue{     public $first; // 隊(duì)頭指針     public $rear; // 隊(duì)尾指針 }

這里我們需要兩個(gè)基本的物理結(jié)構(gòu)。一個(gè)是節(jié)點(diǎn) Node ，一個(gè)是隊(duì)列對象，節(jié)點(diǎn)對象就是一個(gè)正常的鏈表結(jié)構(gòu)，沒啥特別的。而隊(duì)列對象里面就更簡單了，一個(gè)屬性是隊(duì)頭指針，一個(gè)屬性是隊(duì)尾指針。

function InitLinkQueue(){     $node = new LinkQueueNode();     $node->next = NULL;     $queue = new LinkQueue();     $queue->first = $node;     $queue->rear = $node;     return $queue; }  function EnLinkQueue(LinkQueue &$queue, $e){     $node = new LinkQueueNode();     $node->data = $e;     $node->next = NULL;      $queue->rear->next = $node;     $queue->rear = $node; }  function DeLinkQueue(LinkQueue &$queue){     if($queue->front == $queue->rear){         return false;     }      $node = $queue->first->next;     $v = $node->data;      $queue->first->next = $node->next;     if($queue->rear == $node){         $queue->rear = $queue->first;     }      return $v; }  $q = InitLinkQueue(); EnLinkQueue($q, 'A'); EnLinkQueue($q, 'B'); EnLinkQueue($q, 'C'); EnLinkQueue($q, 'D'); EnLinkQueue($q, 'E');  print_r($q); // LinkQueue Object // ( //     [first] => LinkQueueNode Object //         ( //             [data] =>  //             [next] => LinkQueueNode Object //                 ( //                     [data] => A //                     [next] => LinkQueueNode Object //                         ( //                             [data] => B //                             [next] => LinkQueueNode Object //                                 ( //                                     [data] => C //                                     [next] => LinkQueueNode Object //                                         ( //                                             [data] => D //                                             [next] => LinkQueueNode Object //                                                 ( //                                                     [data] => E //                                                     [next] =>  //                                                 )  //                                         )  //                                 )  //                         )  //                 )  //         )  //     [rear] => LinkQueueNode Object //         ( //             [data] => E //             [next] =>  //         )  // )  echo DeLinkQueue($q), PHP_EOL; // A echo DeLinkQueue($q), PHP_EOL; // B  EnLinkQueue($q, 'F'); print_r($q); // LinkQueue Object // ( //     [first] => LinkQueueNode Object //         ( //             [data] =>  //             [next] => LinkQueueNode Object //                 ( //                     [data] => C //                     [next] => LinkQueueNode Object //                         ( //                             [data] => D //                             [next] => LinkQueueNode Object //                                 ( //                                     [data] => E //                                     [next] => LinkQueueNode Object //                                         ( //                                             [data] => F //                                             [next] =>  //                                         )  //                                 )  //                         )  //                 )  //         )  //     [rear] => LinkQueueNode Object //         ( //             [data] => F //             [next] =>  //         )  // )

出、入隊(duì)的代碼函數(shù)和測試代碼就一并給出了，是不是非常的簡單。初始的隊(duì)頭元素依然是一個(gè)空節(jié)點(diǎn)做為起始節(jié)點(diǎn)。然后入隊(duì)的時(shí)候，讓 rear 等于新創(chuàng)建的這個(gè)節(jié)點(diǎn)，并在鏈表中建立鏈?zhǔn)疥P(guān)系。出隊(duì)的時(shí)候也是同樣的讓 first 變成當(dāng)前這個(gè) first 的下一跳節(jié)點(diǎn)，也就是 first->next 就可以了。判斷隊(duì)空的條件也是簡單的變成了隊(duì)頭和隊(duì)尾指針是否相等就可以了。鏈隊(duì)相比順序隊(duì)其實(shí)是簡單了一些，不過同樣的，next 這個(gè)東西容易讓人頭暈，硬記下來就可以了。大家還是可以結(jié)合圖示來學(xué)習(xí)：

PHP 為我們提供的數(shù)組隊(duì)列操作

最后，就和棧一樣，PHP 代碼中也為我們提供了一個(gè)可以用于隊(duì)列操作的函數(shù)。

$sqQueueList = [];  array_push($sqQueueList, 'a'); array_push($sqQueueList, 'b'); array_push($sqQueueList, 'c');  print_r($sqQueueList); // Array // ( //     [0] => a //     [1] => b //     [2] => c // )  array_shift($sqQueueList); print_r($sqQueueList); // Array // ( //     [0] => b //     [1] => c // )

array_shift() 函數(shù)就是彈出數(shù)組中最前面的那個(gè)元素。請注意，這里元素的下標(biāo)也跟著變動(dòng)了，如果我們是 unset() 掉數(shù)組的 0 下標(biāo)元素的話，b 和 c 的下標(biāo)依然還會(huì)是 1 和 2 。而 array_shift() 則會(huì)重新整理數(shù)組，讓其下標(biāo)依然有序。

unset($sqQueueList[0]); print_r($sqQueueList); // Array // ( //     [1] => c // )

總結(jié)

關(guān)于棧的隊(duì)列的內(nèi)容我們就通過兩篇文章介紹完了。不過光說不練假把式，接下來，我們來一點(diǎn)真實(shí)的干貨，使用棧和隊(duì)列來做做題唄，學(xué)算法就得刷題，一日不刷如隔三秋呀！??！

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.棧和隊(duì)列/source/3.2隊(duì)列的相關(guān)邏輯操作.php

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