Penjelasan terperinci tentang baris gilir dalam php

Hari ini, kita akan mempelajari satu lagi jenis struktur logik yang sangat klasik: baris gilir. Saya percaya ramai pelajar telah menggunakan alat gilir cache seperti redis dan rabbitmq. Malah, pangkalan data dan kod program semuanya boleh melaksanakan operasi baris gilir Sama seperti tindanan, baris gilir juga mempunyai peraturan khusus mereka sendiri Selagi ia mematuhi peraturan ini, ia dipanggil baris gilir.

Apakah itu baris gilir?

Berbanding dengan timbunan, baris gilir ialah struktur logik urutan pertama masuk dahulu (FIFO). Apa yang pertama masuk dahulu keluar? Sama seperti barisan kami, apabila kami pergi ke bank atau hospital, kami sentiasa perlu mengambil nombor di pintu, dan nombor ini dipanggil mengikut urutan. Orang yang datang dahulu boleh berniaga atau berjumpa doktor dahulu. Ini adalah barisan biasa. Dengan cara yang sama, giliran harian ialah mod giliran standard.

Jika terdapat baris gilir-lompat, kami boleh menganggapnya sebagai keutamaan yang lebih tinggi jika ada sebab yang sah Ini adalah satu bentuk elemen khas dalam baris gilir. Sama seperti kita memberi keutamaan kepada wanita hamil ketika menunggu kereta api bawah tanah atau bas, terdapat juga tingkap keutamaan untuk anggota tentera ketika beratur membeli tiket kereta api. Namun, ini di luar skop perbincangan kita kali ini.

Apabila beratur di perhentian bas, sudah tentu orang pertama beratur boleh naik bas dahulu, dan seterusnya. Pada masa ini, anda datang ke perhentian bas, kemudian anda hanya boleh menjadi yang terakhir dalam barisan. Ini adalah manifestasi khusus baris gilir.

Begitu juga, seperti tindanan, terdapat beberapa istilah yang perlu kita fahami. Apabila anda tiba di perhentian bas dan berada di barisan terakhir, operasi ini dipanggil "menyertai baris gilir." Apabila bas memasuki stesen dan penumpang pertama menaiki bas, operasi ini dipanggil "keluar". Kedudukan penumpang pertama dipanggil "kepala barisan". Sebagai penumpang terakhir dalam barisan semasa, kedudukan anda dipanggil "ekor barisan". Berbalik kepada logik kod, iaitu, baris gilir "masuk" dari "ekor" dan "keluar" dari "kepala".

Baris Berjujukan

OK, mari kita lihat terus pada kod Perkara pertama yang kita lihat masih pelaksanaan baris gilir.

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

Memandangkan ia adalah pasukan berjujukan, kami masih menggunakan data tatasusunan untuk mewakili elemen dalam pasukan. Kemudian tentukan dua penunjuk depan dan belakang untuk mewakili kepala dan ekor pasukan. Kerana ia adalah baris gilir berurutan, penunjuk di sini sebenarnya menyimpan subskrip tatasusunan. Operasi seterusnya sebenarnya sangat mudah, belakang apabila "masuk barisan", dan depan apabila "keluar barisan".

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

Adakah anda rasa selepas mempelajari susunan, baris gilir juga mudah difahami. Apabila memulakan baris gilir, hanya tetapkan penunjuk kepala dan ekor kepada rekod dengan 0 subskrip. Apabila menyertai baris gilir, biarkan ekor baris gilir meningkat Dalam kod ini, kami menggabungkan dua elemen ke dalam baris gilir, dan kandungan baris gilir yang dicetak adalah seperti yang ditunjukkan dalam ulasan.

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

Apabila meninggalkan pasukan, biarkan hadapan melakukan operasi tambah 1. Walau bagaimanapun, semasa nyah gilir, anda masih perlu menentukan sama ada semua elemen dalam tatasusunan telah dinyah gilir Di sini, kami hanya menggunakan syarat penghakiman yang sangat mudah, iaitu sama ada hadapan dan belakang adalah sama untuk menentukan sama ada baris gilir kosong. Anda boleh menggunakan ilustrasi untuk membantu memahami kod.

Barisan Pekeliling

Saya percaya ramai pelajar menyedarinya. Operasi baris gilir hanya mengubah suai rekod penuding kepala baris gilir dan ekor baris gilir, tetapi tatasusunan akan terus meningkat Jika ia terus meningkat, tatasusunan akan mengisi memori. Malah, dalam bahasa C, tatasusunan diberi panjang tetap. Tatasusunan dalam PHP adalah lebih seperti struktur Hash, jadi ia boleh berkembang tanpa had, dan kita tidak perlu menentukan panjang tatasusunan tertentu pada permulaannya.

Ini juga kemudahan PHP, tetapi apakah yang perlu kita lakukan jika kita tidak mahu membazirkan ruang memori? Sama seperti dalam bahasa C, kami juga menentukan panjang tatasusunan dalam PHP, dan menggunakan "baris gilir bulat" yang sangat klasik untuk menyelesaikan masalah penyimpanan tatasusunan baris gilir. Seperti yang ditunjukkan dalam rajah di bawah:

Malah, ini bermakna dalam ruang tatasusunan yang terhad, apabila kita mencapai nilai maksimum tatasusunan, data baharu akan disimpan kembali ke kedudukan subskrip sebelumnya. Sebagai contoh, dalam gambar kita mempunyai 6 elemen, ketua pasukan semasa berada di subskrip 2, dan ekor pasukan berada di subskrip 5. Jika kita memasukkan elemen, penghujung barisan bergerak ke indeks 6. Jika anda menambah elemen lain, ekor baris gilir akan kembali ke subskrip 0 Jika anda terus menambah, apabila subskrip ekor baris gilir adalah sama dengan subskrip kepala baris gilir tolak 1, kami akan menganggap bahawa baris gilir sudah penuh dan tiada lagi elemen. boleh ditambah.

Begitu juga, apabila dequeuing, kami juga mengendalikan elemen ketua pasukan secara kitaran Apabila elemen ketua pasukan mencapai subskrip 6, jika kami terus dequeuing, ia akan kembali ke kedudukan 0 subscript dan terus dequeue. . Apabila kepala baris gilir dan ekor baris gilir adalah sama, baris gilir semasa juga boleh ditentukan sebagai baris gilir kosong.

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

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视频教程

Atas ialah kandungan terperinci Penjelasan terperinci tentang baris gilir dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!