PHPでのキューの詳しい説明

今日は、もう 1 つの非常に古典的な論理構造タイプであるキューについて学習します。 redis や Rabbitmq などのキャッシュ キュー ツールをすでに使用している学生も多いと思います。実際、データベースとプログラム コードはすべてキュー操作を実装できます。スタックと同様に、キューにも独自のルールがあり、これらのルールに従っている限り、キューと呼ばれます。

#キューとは何ですか?

スタックと比較すると、キューは先入れ先出し (FIFO) 順次論理構造です。先入れ先出しとは何ですか?私たちの行列と同じように、銀行や病院に行くときも、必ず入り口で番号を受け取り、その番号が順番に呼ばれます。先に来た人が先に用事を済ませたり、診察を受けたりすることができるのが典型的な行列です。同様に、毎日のキューイングは標準のキュー モードです。

キューを飛び越える人がいる場合、正当な理由がある場合は、その優先順位が高いと見なすことができます。これはキュー内の要素の特殊な形式です。地下鉄やバスを待つときに妊婦を優先するのと同じように、鉄道の切符を買うために並ぶときにも軍人のための優先窓口があります。ただし、これは今回の議論の範囲外です。

バス停に並ぶときは、当然のことながら、最初に並んでいる人が先にバスに乗り、その後に他の人が続きます。この時点でバス停に来たら、最後尾に並ぶしかありません。これはキューの具体的な現れです。

同様に、スタックと同様に、理解する必要がある名詞がいくつかあります。バス停に来て列の最後尾になったとき、この操作を「列に加わる」といいます。バスが駅に進入し、最初の乗客がバスに乗車することを「降車」といいます。最初の乗客の位置は「列の先頭」と呼ばれ、現在の列の最後の乗客であるあなたの位置は「列の最後尾」と呼ばれます。コードのロジックに戻ります。つまり、キューは「末尾」から「入力」され、「先頭」から「終了」されます。

シーケンシャル キュー

OK、コードを直接見てみましょう。最初に表示されるのは、やはりシーケンシャル キューの実装です。

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

シーケンシャル チームであるため、チーム内の要素を表すために配列データを引き続き使用します。次に、チームの先頭と最後尾を表す 2 つのポインターを前後に定義します。これはシーケンシャルキューであるため、ここでのポインターには実際には配列の添字が格納されます。次の操作は実際には非常に簡単で、「キューに入る」場合は後方、「キューから出る」場合は前です。

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 のレコードに設定するだけです。キューに参加するときは、キューの末尾を増やしてください。このコードでは、2 つの要素をキューに結合しており、出力される順次キューの内容はコメントに示されているとおりです。

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

チームを離れるときは、フロントに1を加える操作を行わせます。ただし、デキューする際には、配列内のすべての要素がデキューされたかどうかを判断する必要があるため、ここでは、前と後ろが等しいかどうかという非常に単純な判定条件のみを使用して、キューが空であるかどうかを判断します。コードの理解を助けるために図を使用できます。

回覧キュー

多くの学生が気づいたと思います。キュー操作はキューの先頭とキューの末尾のポインタ レコードを変更するだけですが、配列は増加し続けます。増加し続けると、配列がメモリをいっぱいにしてしまいます。これは明らかに良いキュー実装ではありません。実際、C 言語では配列には固定長が与えられます。 PHP の配列はハッシュ構造に似ているため、無限に増加する可能性があり、最初に特定の配列の長さを定義する必要はありません。

これも 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 中国語 Web サイトの他の関連記事を参照してください。