PHP隊(duì)列的相關(guān)邏輯操作是什么

這篇文章主要介紹“PHP隊(duì)列的相關(guān)邏輯操作是什么”，在日常操作中，相信很多人在PHP隊(duì)列的相關(guān)邏輯操作是什么問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”P(pán)HP隊(duì)列的相關(guān)邏輯操作是什么”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

什么是隊(duì)列？

相對(duì)于棧來(lái)說(shuō)，隊(duì)列是一種先進(jìn)先出（FIFO）的順序邏輯結(jié)構(gòu)。什么叫先進(jìn)先出呢？就和我們的排隊(duì)一樣，當(dāng)我們?nèi)ャy行或者醫(yī)院的時(shí)候，總是要在門(mén)口取一個(gè)號(hào)，這個(gè)號(hào)是按順序叫的。先來(lái)的人就可以先辦業(yè)務(wù)或者看病，這就是一個(gè)典型的隊(duì)列。同理，日常的排隊(duì)就是一個(gè)標(biāo)準(zhǔn)的隊(duì)列模式。如果有插隊(duì)的，在有正當(dāng)理由的情況下，我們可以認(rèn)為它的優(yōu)先級(jí)更高，這是隊(duì)列中元素的一種特殊形式。就像我們會(huì)在等地鐵或者公交的時(shí)候讓孕婦優(yōu)先，在排隊(duì)買(mǎi)火車(chē)票的時(shí)候也有軍人的優(yōu)先窗口。不過(guò)，這個(gè)并不在我們這次的討論范圍之內(nèi)。

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

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

順序隊(duì)列

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

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

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

是不是感覺(jué)學(xué)過(guò)了棧之后，隊(duì)列也很好理解了。初始化隊(duì)列時(shí)，就是讓隊(duì)頭和隊(duì)尾指針都是 0 下標(biāo)的記錄就可以了。入隊(duì)的時(shí)候讓隊(duì)尾增加，在這段代碼中，我們?nèi)腙?duì)了兩個(gè)元素，打印出來(lái)的順序隊(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 操作。不過(guò)，在出隊(duì)的時(shí)候還需要判斷數(shù)組中的元素是否全部出隊(duì)了，在這里，我們只用了一個(gè)非常簡(jiǎn)單的判斷條件，那就是 front 和 rear 是否相等來(lái)判斷隊(duì)列是否空了。大家可以通過(guò)一個(gè)圖示來(lái)輔助對(duì)代碼的理解。

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

相信已經(jīng)有不少同學(xué)看出來(lái)了。隊(duì)列操作只是修改隊(duì)頭和隊(duì)尾的指針記錄，但是數(shù)組會(huì)一直增加，這樣如果一直增加的話，就會(huì)導(dǎo)致這一個(gè)數(shù)組占滿內(nèi)存，這肯定不是一個(gè)好的隊(duì)列實(shí)現(xiàn)。其實(shí)，在 C 語(yǔ)言中，數(shù)組就是要給一個(gè)固定的長(zhǎng)度的。而 PHP 中的數(shù)組更像是一個(gè) Hash 結(jié)構(gòu)，所以它是可以無(wú)限增長(zhǎng)的，并不需要我們?cè)谝婚_(kāi)始定義一個(gè)具體的數(shù)組長(zhǎng)度。這也是 PHP 的方便之處，不過(guò)如果我們不想浪費(fèi)內(nèi)存空間的話，應(yīng)該怎么辦呢？就像在 C 語(yǔ)言中一樣，我們?cè)?PHP 中也為數(shù)組指定一個(gè)長(zhǎng)度，并且使用非常經(jīng)典的“循環(huán)隊(duì)列”來(lái)解決隊(duì)列數(shù)組的存儲(chǔ)問(wèn)題。就像下圖所示：

其實(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ì)列來(lái)說(shuō)，多了一個(gè)隊(duì)滿的狀態(tài)。我們還是直接從代碼中來(lá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ì)列長(zhǎng)度的取模來(lái)獲取當(dāng)前的循環(huán)下標(biāo)，是不是非常地巧妙。不得不感慨先人的智慧呀！當(dāng)然，這也是基本的數(shù)學(xué)原理哦，所以，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)還是要復(fù)習(xí)一下數(shù)學(xué)相關(guān)的知識(shí)哦！

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

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

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ì)列對(duì)象，節(jié)點(diǎn)對(duì)象就是一個(gè)正常的鏈表結(jié)構(gòu)，沒(méi)啥特別的。而隊(duì)列對(duì)象里面就更簡(jiǎn)單了，一個(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ù)和測(cè)試代碼就一并給出了，是不是非常的簡(jiǎn)單。初始的隊(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ì)空的條件也是簡(jiǎn)單的變成了隊(duì)頭和隊(duì)尾指針是否相等就可以了。鏈隊(duì)相比順序隊(duì)其實(shí)是簡(jiǎn)單了一些，不過(guò)同樣的，next 這個(gè)東西容易讓人頭暈，硬記下來(lái)就可以了。大家還是可以結(jié)合圖示來(lái)學(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è)元素。請(qǐng)注意，這里元素的下標(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
// )

到此，關(guān)于“PHP隊(duì)列的相關(guān)邏輯操作是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！