Postur yang betul untuk menggunakan tindanan dan baris gilir (dengan contoh)

Melalui kajian tindanan dan baris gilir, kami nampaknya merasakan bahawa struktur data sebenarnya sangat mudah. Sudah tentu, ini hanyalah permulaan. Kami bermula daripada senarai jujukan dan senarai terpaut kepada susunan dan baris gilir semasa, yang sebenarnya membuka jalan untuk masa hadapan. Tindanan dan baris gilir boleh dilihat dalam algoritma traversal pokok dan graf. Di sini, kita mula-mula melihat secara ringkas beberapa aplikasi praktikal tindanan dan baris gilir.

Soalan palindrom

Andaikata ada teks, kita perlu tentukan sama ada ia adalah "palindrom" (bukan teks yang ditulis oleh saudara Hui). Anda boleh menggunakan timbunan untuk menyelesaikan masalah ini.

Palindrom bermaksud bahawa selepas membahagikan perenggan teks ini kepada dua, kandungan perenggan sebelumnya dan kandungan perenggan berikut adalah betul-betul sama, tetapi susunannya terbalik. Sebagai contoh, ia sangat terkenal: Air paip Shanghai berasal dari laut. Shanghai berasal dari laut Struktur dua bahagian ini membentuk palindrom dalam satu ayat. Contoh lain ialah watak genap panjang: abcddcba, yang juga merupakan palindrom.

Soalan serupa boleh muncul dengan mudah dalam beberapa soalan temu bual algoritma mudah. ​​Saya percaya ramai rakan telah melihat petunjuk itu membandingkan timbunan dengan separuh kedua, anda boleh menentukan sama ada rentetan semasa ialah palindrom. Jangan hanya bercakap tanpa berlatih, mari kita laksanakan kod tersebut.

$string1 = 'abcdedcba';
$string2 = 'abcdeedcba';
$string3 = 'abcdefcba';

function getIsPlalindrome($string)
{
    if (gettype($string) != 'string') {
        return false;
    }
    $strlen = strlen($string);
    $mid = floor($strlen / 2);
    $arr = [];

    if ($strlen < 2) {
        return false;
    }

    // 入栈
    for ($i = 0; $i < $mid; $i++) {
        array_push($arr, $string[$i]);
    }

    $j = $mid;
    $i = $strlen % 2 == 0 ? $mid : $mid + 1; // $i 从中位数开始
    for (; $i < $strlen; $i++) {
        $v = $arr[$j - 1]; // 获得栈顶元素
        if ($v != $string[$i]) {
            return false;
        }
        array_pop($arr); // 弹出栈顶元素
        $j--;
    }
    if ($arr) {
        return false;
    }
    return true;
}

var_dump(getIsPlalindrome($string1)); // bool(true)
var_dump(getIsPlalindrome($string2)); // bool(true)
var_dump(getIsPlalindrome($string3)); // bool(false)

Ia sangat mudah, hanya gunakan array_push() dan array_pop() untuk melaksanakan operasi tindanan berjujukan. Satu-satunya perkara yang perlu diberi perhatian ialah untuk panjang watak ganjil dan genap yang berbeza, median yang ingin kita ambil juga akan berubah mengikut kesesuaian.

Algoritma palindrom agak mudah Selain itu, soalan seperti padanan kurungan ringkas, operasi aritmetik dan ungkapan infiks-ke-akhiran yang sering muncul ialah soalan temu bual algoritma tindanan biasa. Anda boleh mencari kandungan yang berkaitan dan mencubanya sendiri.

Rekursi

Sebelum bercakap tentang rekursi, kita perlu menjelaskan satu perkara, iaitu: panggilan fungsi dalam bahasa pengaturcaraan pada asasnya adalah panggilan tindanan.

Bagaimana anda memahami ayat ini? Apabila kita melaksanakan kod, jika kita menemui fungsi, kita akan sentiasa memasukkan fungsi ini terlebih dahulu Selepas menjalankan kod dalam fungsi ini, kita akan kembali ke baris pelaksanaan kod asal untuk terus melaksanakan kod yang memanggil fungsi semasa. Sebagai contoh, kod berikut.

function testA()
{
    echo 'A start.', PHP_EOL;
    testB();
    echo 'A end.', PHP_EOL;
}
function testB()
{
    echo 'B start.', PHP_EOL;
    echo 'B end.', PHP_EOL;
}
echo 'P start.', PHP_EOL;
testA();
echo 'P end.', PHP_EOL;

// P start.
// A start.
// B start.
// B end.
// A end.
// P end.

Apabila halaman semasa P dijalankan ke fungsi testA(), ia memasuki fungsi testA() untuk melaksanakan kod dalamannya, iaitu, P -> Kemudian fungsi testA() memanggil fungsi testB(), dan kini ia memasuki testB() dan melaksanakan kod dalam badan fungsi, iaitu P -> Apabila kod testB() selesai, kembali ke testA() untuk terus melaksanakan kandungan dalam badan fungsi testA(), dan akhirnya kembali ke halaman P untuk meneruskan pelaksanaan ke bawah, iaitu, B -> P .

Jika anda tidak memahami penerangan di atas, sila baca beberapa kali lagi dan kaji dengan teliti. Bukankah ini hanya proses panggilan timbunan? !

Melihat dengan cara ini, dalam bahasa pengaturcaraan, timbunan benar-benar jauh di dalam tulang. Kerana selagi anda membangunkan kod, anda mesti menggunakan timbunan. "Rekursi" ialah pelaksanaan tindanan yang lebih tipikal.

function recursion($n)
{
    if ($n == 0 || $n == 1) {
        return 1;
    }
    $result = recursion($n - 1) * $n;
    return $result;
}

echo recursion(10), PHP_EOL;

Ini ialah pelaksanaan rekursif mudah bagi algoritma faktorial Memandangkan rekursi akan mencipta tindanan, perkara pertama yang dikira oleh kod kami ialah n di bahagian bawah tindanan ialah 1, dan memunculkan timbunan kembali. 1 Selepas itu, apabila melonjakkan tindanan semula, darab 1 dengan 2, dan apabila muncul daripada tindanan semula, darab 2 dengan 3, dan seterusnya, sehingga hasil pemfaktoran dari 1 hingga 10 dikira.

Soalan temu bual berkaitan rekursi juga sangat biasa dalam temu bual kami, jadi kami mesti memahami bahawa rekursi sebenarnya adalah satu bentuk timbunan, dan kemudian gunakan Pemikiran timbunan untuk menyahkonstruk keseluruhan proses panggilan rekursif.

Aplikasi baris gilir

Akhir sekali, mari kita bercakap tentang beberapa aplikasi praktikal baris gilir. Sebenarnya, tidak banyak contoh baris gilir yang baik pada tahap kod Yang lebih biasa mungkin ialah dua baris gilir digabungkan dan dinyah gilir (masalah pasangan tarian) atau dua baris gilir dinyah gilir bersama-sama, dan dua baris gilir di satu sisi sebelum itu. satu boleh dequeued oleh yang lain masalah ini. Anda boleh mencari topik berkaitan sendiri. Secara relatifnya, soalan algoritma baris gilir agak jarang di kalangan soalan temuduga, dan kebanyakannya muncul dalam bentuk soalan penghakiman pemilihan, termasuk dalam peperiksaan kemasukan pasca siswazah. Walau bagaimanapun, dalam aplikasi praktikal, baris gilir kini merupakan senjata ajaib yang hebat untuk menyelesaikan masalah konkurensi yang tinggi, dan ia juga merupakan faktor penting untuk penemuduga menilai pengalaman anda.

Dalam pembangunan projek sebenar, salah satu fungsi baris gilir yang paling tipikal ialah masalah jualan kilat. Sama seperti merebut tiket kereta api atau telefon mudah alih Xiaomi, di bahagian atas jam, sejumlah besar permintaan mengalir masuk. Jika anda hanya bergantung pada pelayan untuk mengendalikannya, konkurensi ultra tinggi bukan sahaja akan memberi tekanan besar pada pelayan , tetapi juga boleh menyebabkan pelbagai masalah yang hanya berlaku dalam senario konkurensi tinggi, seperti terlebih jual, pengecualian transaksi, dsb. (Berbilang rangkaian mengemas kini data serentak)

而队列，正是解决这个问题的一把好手。通常我们会使用的队列系统（redis、rabbitmq）都是以内存为主的队列系统，它们的特点就是存储非常快。由前端（生产者）生成的大量请求都存入队列中（入队），然后在后台脚本（消费者）中进行处理（出队）。前端只需要返回一个正在处理中，或者正在排队的提示即可，然后后台处理完成后，通知前台显示结果。这样，在一个秒杀场景中基本上就算是解决了高并发的问题了。当然，现实环境可能还需要考虑更多因素，但核心都是以队列的方式来解决这种瞬间高并发的业务功能。

另外，队列还有一个重要的业务场景，那就是通知、消息、邮件、短信之类的这种信息发送。因为队列的所能解决的一些问题的最大特点就是需要生产者/消费者的业务解耦。通常我们在群发消息时都会批量进行大规模的发送，这时就只需要准备好消息内容和对应的手机号、设备id，就可以让系统在后台队列中慢慢进行消息发送了，而不需要我们的前端一直等待消息全部发送完成。

这时，不少小伙伴又看出了一点点门道了。队列这货在实际应用中，就是多线程的感觉呀，JS 中的事件回调，CPU 的碎片时间轮询可不就是一种队列的真实应用嘛。还有设计模式中的“观察者模式”，本身就是事件回调这种机制的一种编程范式，所以，用它来实现的很多功能中，我们都能看到队列的影子。

总结

看看，一个栈，一个队列，竟然都是我们在开发过程中天天要接触的东西。是不是感觉自己的脑容量不够用了？仔细再想想，还有哪些东西和我们的栈、队列有关呢？其实只要把握住它们的两个本质就可以了：栈是后进先出（LIFO）或者说是先进后出（FILO），而队列是先进先出（FIFO）。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.3栈和队列的应用.php

推荐学习：php视频教程

Atas ialah kandungan terperinci Postur yang betul untuk menggunakan tindanan dan baris gilir (dengan contoh). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!