詳解php中的佇列

今天，我們就來學習另外一個也是非常經典的邏輯結構型別：佇列。相信不少同學已經使用過 redis 、 rabbitmq 之類的快取佇列工具。其實，資料庫、程式碼，這些都可以實作佇列的操作，就跟棧一樣，佇列也是有其特定的規則，只要符合這個規則，它就叫做佇列。

什麼是佇列？

相對於堆疊來說，佇列是一種先進先出（FIFO）的順序邏輯結構。什麼叫先進先出呢？就和我們的排隊一樣，當我們去銀行或醫院的時候，總是要在門口取一個號，這個號是按順序叫的。先來的人就可以先辦業務或看病，這就是一個典型的隊列。同理，日常的排隊就是一個標準的隊列模式。

如果有插隊的，在有正當理由的情況下，我們可以認為它的優先權更高，這是隊列中元素的一種特殊形式。就像我們會在等地鐵或公車的時候讓孕婦優先，在排隊買火車票的時候也有軍人的優先窗口。不過，這並不在我們這次的討論範圍內。

在公車站排隊時，排第一個的當然可以第一個上車，然後依序。這時，你來到了公車站，那麼你只能排到最後一位。這個就是隊列的具體表現。

同樣，和堆疊一樣，也有一些名詞我們需要了解。當你來到公車站並排到最後一位時，這個操作叫作「入隊」。當公車進站後，第一位乘客上車，這個操作叫做「出隊」。第一位乘客所處的位置叫做“隊頭”，你做為目前隊列的最後一位乘客，你的位置就叫做“隊尾”。回到程式碼邏輯上面來看，也就是說隊列是從“隊尾”“入隊”，從“隊頭”“出隊”。

順序佇列

OK，我們還是直接從來程式碼來看，首先看到的依然是順序隊伍的實作。

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

既然是順序隊，我們還是還是用一個陣列 data 來表示隊內的元素。然後定義兩個指針 front 和 rear 來表示隊頭和隊尾。因為是順序隊，所以這裡的指針其實也就是保存的是數組的下標。接下來的操作其實非常的簡單了，「入隊」時 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 下標的記錄就可以了。入隊的時候讓隊尾增加，在這段程式碼中，我們入隊了兩個元素，列印出來的順序佇列內容就如註解所示。

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 操作。不過，在出隊的時候還需要判斷數組中的元素是否全部出隊了，在這裡，我們只用了一個非常簡單的判斷條件，那就是 front 和 rear 是否相等來判斷隊列是否空了。大家可以透過一個圖示來輔助對程式碼的理解。

循環佇列

相信已經有不少同學看出來了。隊列操作只是修改隊頭和隊尾的指針記錄，但是數組會一直增加，這樣如果一直增加的話，就會導致這一個數組佔滿內存，這肯定不是一個好的隊列實現。其實，在 C 語言中，數組就是要給一個固定的長度的。而 PHP 中的陣列更像是一個 Hash 結構，所以它是可以無限增長的，並不需要我們在一開始就定義一個具體的陣列長度。

這也是 PHP 的方便之處，但如果我們不想浪費記憶體空間的話，我們該怎麼辦呢？就像在 C 語言中一樣，我們在 PHP 中也為陣列指定一個長度，並且使用非常經典的「循環佇列」來解決佇列數組的儲存問題。就像下圖所示：

其實意思是，在有限的陣列空間範圍內，當我們達到陣列的最大值時，將新的資料保存回之前的下標位置。例如圖中我們有 6 個元素，目前隊頭在 2 下標，隊尾在 5 下標。如果我們入隊一個元素，隊尾移動到 6 下標。再增加一個元素的話，隊尾移動回 0 下標，如果繼續加的話，當隊尾下標等於隊頭下標減 1 的時候，我們就認為這個隊列已經滿了，不能再增加元素了。

同理，出隊操作的時候我們也是循環地操作隊頭元素，當隊頭元素到6 的下標後，繼續出隊的話，也會回到0 下標的位置繼續出隊。當隊頭和隊尾相等時，目前的隊列也可以判定為空隊列了。

由此，我们可以看出，循环队列相比普通的线性队列来说，多了一个队满的状态。我们还是直接从代码中来看看这个队满的条件是如何判断的。

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; // 改成循环下标
}

function DeSqQueueLoop(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front = ($queue->front + 1) % MAX_QUEUE_LENGTH; // 改成循环下标
    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 这个形式进行的。根据队列长度的取模来获取当前的循环下标，是不是非常地巧妙。不得不感慨先人的智慧呀！当然，这也是基本的数学原理哦，所以，学习数据结构还是要复习一下数学相关的知识哦！

链式队列

顺序队列有没有看懵？没关系，队列的链式结构其实相比顺序结构还要简单一些，因为它真的只需要操作队头和队尾的指针而已，别的真的就不太需要考虑了。而且这个指针就是真的指向具体对象的指针了。

class LinkQueueNode{
    public $data;
    public $next;
}

class LinkQueue{
    public $first; // 队头指针
    public $rear; // 队尾指针
}

这里我们需要两个基本的物理结构。一个是节点 Node ，一个是队列对象，节点对象就是一个正常的链表结构，没啥特别的。而队列对象里面就更简单了，一个属性是队头指针，一个属性是队尾指针。

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] => 
//         )

// )

出、入队的代码函数和测试代码就一并给出了，是不是非常的简单。初始的队头元素依然是一个空节点做为起始节点。然后入队的时候，让 rear 等于新创建的这个节点，并在链表中建立链式关系。出队的时候也是同样的让 first 变成当前这个 first 的下一跳节点，也就是 first->next 就可以了。判断队空的条件也是简单的变成了队头和队尾指针是否相等就可以了。链队相比顺序队其实是简单了一些，不过同样的，next 这个东西容易让人头晕，硬记下来就可以了。大家还是可以结合图示来学习：

PHP 为我们提供的数组队列操作

最后，就和栈一样，PHP 代码中也为我们提供了一个可以用于队列操作的函数。

$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() 函数就是弹出数组中最前面的那个元素。请注意，这里元素的下标也跟着变动了，如果我们是 unset() 掉数组的 0 下标元素的话，b 和 c 的下标依然还会是 1 和 2 。而 array_shift() 则会重新整理数组，让其下标依然有序。

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

总结

关于栈的队列的内容我们就通过两篇文章介绍完了。不过光说不练假把式，接下来，我们来一点真实的干货，使用栈和队列来做做题呗，学算法就得刷题，一日不刷如隔三秋呀！！！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.2队列的相关逻辑操作.php

推荐学习：php视频教程

以上是詳解php中的佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！