站長資訊網(wǎng)今天，我們就來學習另外一個也是非常經(jīng)典的邏輯結(jié)構(gòu)類型：隊列。相信不少同學已經(jīng)使用過 redis 、 rabbitmq 之類的緩存隊列工具。其實，數(shù)據(jù)庫、程序代碼，這些都可以實現(xiàn)隊列的操作，就和棧一樣，隊列也是有其特定的規(guī)則，只要符合這個規(guī)則，它就叫做隊列。
什么是隊列？
相對于棧來說，隊列是一種先進先出（FIFO）的順序邏輯結(jié)構(gòu)。什么叫先進先出呢？就和我們的排隊一樣，當我們?nèi)ャy行或者醫(yī)院的時候，總是要在門口取一個號，這個號是按順序叫的。先來的人就可以先辦業(yè)務(wù)或者看病，這就是一個典型的隊列。同理，日常的排隊就是一個標準的隊列模式。
如果有插隊的，在有正當理由的情況下，我們可以認為它的優(yōu)先級更高，這是隊列中元素的一種特殊形式。就像我們會在等地鐵或者公交的時候讓孕婦優(yōu)先，在排隊買火車票的時候也有軍人的優(yōu)先窗口。不過，這個并不在我們這次的討論范圍之內(nèi)。
在公交站排隊時，排第一個的當然可以第一個上車，然后依次。這時，你來到了公交站，那么你只能排到最后一位。這個就是隊列的具體表現(xiàn)形式。
同樣，和棧一樣，也有一些名詞我們需要了解。當你來到公交站并排到最后一位時，這個操作叫作“入隊”。當公交車進站后，第一位乘客上車，這個操作叫做“出隊”。第一位乘客所處的位置叫做“隊頭”，你做為當前隊列的最后一位乘客，你的位置就叫做“隊尾”。回到代碼邏輯上面來看，也就是說隊列是從“隊尾”“入隊”，從“隊頭”“出隊”。
順序隊列
OK，我們還是直接從來代碼來看，首先看到的依然是順序隊的實現(xiàn)。
class SqQueue{ public $data; public $front; public $rear; }
既然是順序隊，我們依然還是用一個數(shù)組 data 來表示隊內(nèi)的元素。然后定義兩個指針 front 和 rear 來表示隊頭和隊尾。因為是順序隊，所以這里的指針其實也就是保存的是數(shù)組的下標。接下來的操作其實就非常的簡單了，“入隊”時 rear++ ，“出隊”時 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){ // 隊列為空 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 // )
是不是感覺學過了棧之后，隊列也很好理解了。初始化隊列時，就是讓隊頭和隊尾指針都是 0 下標的記錄就可以了。入隊的時候讓隊尾增加，在這段代碼中，我們?nèi)腙犃藘蓚€元素，打印出來的順序隊列內(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 // )
出隊的時候，就讓 front 進行加 1 操作。不過，在出隊的時候還需要判斷數(shù)組中的元素是否全部出隊了，在這里，我們只用了一個非常簡單的判斷條件，那就是 front 和 rear 是否相等來判斷隊列是否空了。大家可以通過一個圖示來輔助對代碼的理解。
循環(huán)隊列
相信已經(jīng)有不少同學看出來了。隊列操作只是修改隊頭和隊尾的指針記錄，但是數(shù)組會一直增加，這樣如果一直增加的話，就會導致這一個數(shù)組占滿內(nèi)存，這肯定不是一個好的隊列實現(xiàn)。其實，在 C 語言中，數(shù)組就是要給一個固定的長度的。而 PHP 中的數(shù)組更像是一個 Hash 結(jié)構(gòu)，所以它是可以無限增長的，并不需要我們在一開始定義一個具體的數(shù)組長度。
這也是 PHP 的方便之處，不過如果我們不想浪費內(nèi)存空間的話，應(yīng)該怎么辦呢？就像在 C 語言中一樣，我們在 PHP 中也為數(shù)組指定一個長度，并且使用非常經(jīng)典的“循環(huán)隊列”來解決隊列數(shù)組的存儲問題。就像下圖所示：
其實意思就是，在有限的數(shù)組空間范圍內(nèi)，當我們達到數(shù)組的最大值時，將新的數(shù)據(jù)保存回之前的下標位置。比如圖中我們有 6 個元素，當前隊頭在 2 下標，隊尾在 5 下標。如果我們?nèi)腙犚粋€元素，隊尾移動到 6 下標。再添加一個元素的話，隊尾移動回 0 下標，如果繼續(xù)添加的話，當隊尾下標等于隊頭下標減 1 的時候，我們就認為這個隊列已經(jīng)滿了，不能再增加元素了。
同理，出隊操作的時候我們也是循環(huán)地操作隊頭元素，當隊頭元素到 6 的下標后，繼續(xù)出隊的話，也會回到 0 下標的位置繼續(xù)出隊。當隊頭和隊尾相等時，當前的隊列也可以判定為空隊列了。
由此，我們可以看出，循環(huán)隊列相比普通的線性隊列來說，多了一個隊滿的狀態(tài)。我們還是直接從代碼中來看看這個隊滿的條件是如何判斷的。
define('MAX_QUEUE_LENGTH', 6); function EnSqQueueLoop(SqQueue &$queue, $e){ // 判斷隊列是否滿了 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)下標 } function DeSqQueueLoop(SqQueue &$queue){ // 隊列為空 if($queue->front == $queue->rear){ return false; } $e = $queue->data[$queue->front]; $queue->front = ($queue->front + 1) % MAX_QUEUE_LENGTH; // 改成循環(huán)下標 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 // )
出、入隊的下標移動以及隊滿的判斷，都是以 (queue->rear + 1) % MAX_QUEUE_LENGTH 這個形式進行的。根據(jù)隊列長度的取模來獲取當前的循環(huán)下標，是不是非常地巧妙。不得不感慨先人的智慧呀！當然，這也是基本的數(shù)學原理哦，所以，學習數(shù)據(jù)結(jié)構(gòu)還是要復習一下數(shù)學相關(guān)的知識哦！
鏈式隊列
順序隊列有沒有看懵？沒關(guān)系，隊列的鏈式結(jié)構(gòu)其實相比順序結(jié)構(gòu)還要簡單一些，因為它真的只需要操作隊頭和隊尾的指針而已，別的真的就不太需要考慮了。而且這個指針就是真的指向具體對象的指針了。
class LinkQueueNode{ public $data; public $next; } class LinkQueue{ public $first; // 隊頭指針 public $rear; // 隊尾指針 }
這里我們需要兩個基本的物理結(jié)構(gòu)。一個是節(jié)點 Node ，一個是隊列對象，節(jié)點對象就是一個正常的鏈表結(jié)構(gòu)，沒啥特別的。而隊列對象里面就更簡單了，一個屬性是隊頭指針，一個屬性是隊尾指針。
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] => // ) // )
出、入隊的代碼函數(shù)和測試代碼就一并給出了，是不是非常的簡單。初始的隊頭元素依然是一個空節(jié)點做為起始節(jié)點。然后入隊的時候，讓 rear 等于新創(chuàng)建的這個節(jié)點，并在鏈表中建立鏈式關(guān)系。出隊的時候也是同樣的讓 first 變成當前這個 first 的下一跳節(jié)點，也就是 first->next 就可以了。判斷隊空的條件也是簡單的變成了隊頭和隊尾指針是否相等就可以了。鏈隊相比順序隊其實是簡單了一些，不過同樣的，next 這個東西容易讓人頭暈，硬記下來就可以了。大家還是可以結(jié)合圖示來學習：
PHP 為我們提供的數(shù)組隊列操作
最后，就和棧一樣，PHP 代碼中也為我們提供了一個可以用于隊列操作的函數(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ù)組中最前面的那個元素。請注意，這里元素的下標也跟著變動了，如果我們是 unset() 掉數(shù)組的 0 下標元素的話，b 和 c 的下標依然還會是 1 和 2 。而 array_shift() 則會重新整理數(shù)組，讓其下標依然有序。
unset($sqQueueList[0]); print_r($sqQueueList); // Array // ( // [1] => c // )
總結(jié)
關(guān)于棧的隊列的內(nèi)容我們就通過兩篇文章介紹完了。不過光說不練假把式，接下來，我們來一點真實的干貨，使用棧和隊列來做做題唄，學算法就得刷題，一日不刷如隔三秋呀?。?！
測試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.棧和隊列/source/3.2隊列的相關(guān)邏輯操作.php
推薦學習：php視頻教程
