Penjelasan terperinci tentang timbunan dalam php

Untuk struktur logik, kami juga bermula dari yang paling mudah. Tindanan dan baris gilir adalah perkataan biasa kepada kebanyakan orang, tetapi timbunan dan tindanan sebenarnya adalah dua perkara yang berbeza. Jangan keliru dengan penemuduga semasa temuduga. Timbunan ialah struktur pokok, atau struktur pokok binari yang lengkap. Hari ini, kita terutamanya bercakap tentang aplikasi timbunan ini.

Apakah tindanan?

Timbunan secara amnya ialah struktur data berjujukan. Ciri terbesarnya ialah keluar-masuk-dahulu (LIFO), atau sebaliknya, keluar dahulu-masuk-akhir (FILO). Apakah maksud kedua-dua ayat ini? Contoh paling tipikal ialah sesuatu yang pasti akan dilihat oleh semua orang apabila menonton siri TV, terutamanya filem perang senjata: majalah.

Apabila memuatkan majalah, peluru ditekan ke dalam majalah satu demi satu, dengan kata lain, peluru pertama ditekan di bahagian bawah, dan apabila menembak, peluru ditekan ke dalam majalah satu demi satu. Peluru dikeluarkan dari bahagian atas majalah dalam susunan terbalik, dengan peluru pertama yang dimasukkan adalah yang terakhir dikeluarkan.

Contoh ini sebenarnya sangat jelas, mari kita satukan istilah. Menekan peluru ke dalam majalah dipanggil "menyusun", peluru pertama di bahagian bawah, kedudukan ini dipanggil "bawah tindanan", peluru terakhir di bahagian atas, kedudukan ini dipanggil "atas tindanan", peluru dipecat Ia adalah peluru di "atas" timbunan Operasi ini dipanggil "popping".

Melalui takrifan istilah di atas, kita dapat melihat bahawa operasi logik tindanan adalah terutamanya "ke dalam tindanan" dan "keluar daripada tindanan", dan perkara yang paling penting untuk diambil berat dalam logik struktur ialah keadaan "atas tindanan" dan "tindanan "Bawah" apabila muncul atau menolak tindanan. Sudah tentu, tiada masalah dalam menggunakan susunan atau struktur rantai struktur logik tindanan. Mari kita lihat satu persatu.

Timbunan Berjujukan

Pertama sekali, ini adalah pelaksanaan yang agak mudah bagi timbunan berjujukan. Oleh kerana ia adalah struktur berjujukan, maka gunakan tatasusunan. Walau bagaimanapun, kita juga perlu merekodkan situasi "atas timbunan" atau "bawah timbunan", jadi kami merangkum tatasusunan timbunan berjujukan ke dalam kelas.

Pada masa yang sama, tentukan atribut dalam kelas ini untuk menunjukkan penunjuk "atas" atau "bawah" bagi timbunan semasa, yang sebenarnya merupakan kedudukan subskrip bagi "atas" atau "bawah" semasa dalam tatasusunan itu. Secara umumnya, kita hanya perlu merekodkan kedudukan "atas tindanan" dan tetapkan "bawah tindanan" kepada -1 secara lalai. Oleh kerana subskrip tatasusunan itu sendiri bermula dari 0, apabila atribut "top of stack" ialah -1, stack ialah tindanan kosong, kerana "atas" dan "bawah" adalah bersama dan tiada unsur di dalamnya.

class SqStack
{
    public $data;
    public $top;
}

Memulakan tindanan berjujukan adalah mudah, dengan tatasusunan kosong dan menetapkan $top kepada -1 .

function InitSqStack()
{
    $stack = new SqStack();
    $stack->data = [];
    $stack->top = -1;
    return $stack;
}

Langkah seterusnya ialah operasi "tekan" dan "pop" Mari lihat kod dahulu.

function PushSqStack(SqStack &$stack, $x){
    $stack->top ++;
    $stack->data[$stack->top] = $x;
}

function PopSqStack(SqStack &$stack){
    // 栈空
    if($stack->top == -1){
        return false;
    }

    $v = $stack->data[$stack->top];
    $stack->top--;
    return $v;
}

Menolak ke tindanan adalah mudah, cuma tambah kandungan pada elemen tatasusunan dan kemudian $top. Walau bagaimanapun, jika ia adalah bahasa C, kerana ia mempunyai had panjang tatasusunan, apabila menolak ke tindanan, kita juga perlu menentukan sama ada tindanan itu penuh. Sudah tentu, dalam PHP kami tidak mempunyai kebimbangan ini.

Ikon tolak tindanan berurutan

Apabila muncul tindanan, anda perlu menentukan sama ada tindanan semasa kosong Ini tidak membezakan antara bahasa, kerana Jika ia lebih kecil daripada -1, masalah akan berlaku apabila menggunakan tindanan ini semula. Apabila memunculkan timbunan, jika timbunan sudah kosong, jangan berikan $top--, kemudian dapatkan elemen atas timbunan dan kembalikannya.

Ikon pop tindanan berjujukan

Mari kita lihat keputusan ujian tindanan berjujukan ini.

$stack = InitSqStack();

PushSqStack($stack, 'a');
PushSqStack($stack, 'b');
PushSqStack($stack, 'c');

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(2)
//   }

echo PopSqStack($stack), PHP_EOL; // c
echo PopSqStack($stack), PHP_EOL; // b
echo PopSqStack($stack), PHP_EOL; // a

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(-1)
//   }

Bukankah sangat mudah untuk mengendalikan tindanan melalui tatasusunan? Selepas membaca dan mempelajari tindanan rantai, kami juga akan bercakap tentang fungsi operasi tindanan tatasusunan yang PHP sediakan untuk kami, yang akan lebih mudah digunakan.

Timbunan Rantaian

Malah, untuk struktur storan rantai, kandungan teras masih sama Kami juga perlu mengambil berat tentang bahagian atas timbunan kami, dan kami juga perlu mengambil berat tentangnya operasi di dalam dan di luar timbunan. Walau bagaimanapun, dalam rantaian, kita boleh menggunakan sisipan kepala, iaitu, menyimpan data yang dimasukkan di bahagian atas rantai untuk mencapai kesan "atas tindanan". Dengan cara ini, kami tidak memerlukan atribut khas untuk menyimpan kedudukan teratas semasa tindanan. Ia akan lebih jelas untuk memahami secara langsung melalui gambar.

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

Struktur data hanyalah struktur rantai biasa Perkara utama ialah melihat bagaimana operasi tolak dilakukan.

function InitLinkStack(){
    return null;
}

function PushLinkStack(?LinkStack &$stack, $x){
    $s = new LinkStack();
    $s->data = $x;
    $s->next = $stack;
    $stack = $s;
}

function PopLinkStack(?LinkStack &$stack){
    if($stack == NULL){
        return false;
    }
    $v = $stack->data;
    $stack = $stack->next;
    return $v;
}

Malah, operasi memulakan tindanan kosong dalam tindanan rantai tidak masuk akal. Kita boleh mentakrifkan pembolehubah nol secara langsung dan melakukan operasi rantaian padanya, tetapi di sini kita masih kekal bersatu dengan timbunan berjujukan. Sama seperti bahagian bawah timbunan dalam timbunan berjujukan ialah -1, dalam timbunan rantai, kami juga bersetuju bahawa bahagian bawah timbunan ialah nod objek nol.

接下来就是入栈操作了。这里我们使用的是头插法，其实就是将新元素放到链表的顶端。先实例化一个节点，然后将这个节点的 next 指向链表的头节点。接着再让当前这个节点成为链表的新的头节点，就像下图所示的那样。

同理，出栈的操作其实也是类似的，将头节点变成当前头节点的 next 节点，直到当前节点变成 null ，也就是栈已经空了，如图所示：

最后，我们同样的测试一下这一套链式栈的代码运行情况如何。

$stack = InitLinkStack();

PushLinkStack($stack, 'a');
PushLinkStack($stack, 'b');
PushLinkStack($stack, 'c');

var_dump($stack);
// object(LinkStack)#3 (2) {
//     ["data"]=>
//     string(1) "c"
//     ["next"]=>
//     object(LinkStack)#2 (2) {
//       ["data"]=>
//       string(1) "b"
//       ["next"]=>
//       object(LinkStack)#1 (2) {
//         ["data"]=>
//         string(1) "a"
//         ["next"]=>
//         NULL
//       }
//     }
//   }

echo PopLinkStack($stack), PHP_EOL; // c
echo PopLinkStack($stack), PHP_EOL; // b
echo PopLinkStack($stack), PHP_EOL; // a

var_dump($stack);
// NULL

是不是很多小伙伴已经看出之前我们花费了 4 篇文章的时间来讲述线性结构中的顺序表和链表的重要作用了吧。它们真的是一切其它逻辑结构的基础。不光是栈，在队列、树、图中我们都会有不同结构的线性和链式的实现。当然，更重要的是能体会它们之间的区别，在不同的业务场景中，两种不同的存储结构可能真的会带来完全不一样的体验。

PHP 为我们提供的数组栈操作

最后，我们简单的看一下在 PHP 中已经为我们准备好的两个数组操作函数。有了它们，对于顺序栈来说，我们的操作可以简化到非常傻瓜智能的效果。

$sqStackList = [];

array_push($sqStackList, 'a');
array_push($sqStackList, 'b');
array_push($sqStackList, 'c');

print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_pop($sqStackList);
print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
// )

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// b

array_pop($sqStackList);

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// c

array_pop($sqStackList);

print_r($sqStackList);
// Array
// (
// )

估计不少同学早就用过这两个函数了。array_push() 就是向数组中压入一个数据，其实说白了，增加一个数据到数组中而已，没什么特别稀罕的功能。而 array_pop() 则是将数组最后一个位置的数据弹出。是不是和我们上面自己实现的那个顺序栈是完全相同的概念。没错，既然语言环境已经为我们准备好了，那么除了在某些场景下需要链式结构的话，大部分情况下我们直接使用这两个函数就可以方便地实现 PHP 中的栈操作了。

总结

栈这个逻辑结构是不是非常的简单清晰呀，在日常应用中其实栈的使用非常广泛。比如算式中的前缀算式、中缀算式、后缀算式的转化，比如我们后面学习树、图时要接触到了BFS（深度搜索），再根据BFS引出递归这个概念。另外，在解析字符时的一些对称匹配、回文算法的判断等等，这些都是栈的典型应用。可以说，栈这个东西撑起了计算机算法的半壁江山。而另外半壁呢？当然就是我们下回要讲的：队列。

测试代码：

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

推荐学习：php视频教程

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