Detaillierte Erklärung des Stacks in PHP

Für den logischen Aufbau gehen wir ebenfalls vom Einfachsten aus. „Stack“ und „Queue“ sind den meisten Menschen vertraute Wörter, aber Heap und Stack sind eigentlich zwei verschiedene Dinge. Lassen Sie sich während des Interviews nicht vom Interviewer verwirren. Der Heap ist eine Baumstruktur oder eine vollständige binäre Baumstruktur. Heute sprechen wir hauptsächlich über die Anwendung dieses Stapels.

Was ist ein Stapel?

Der Stapel ist im Allgemeinen eine sequentielle Datenstruktur. Sein größtes Merkmal ist Last-In-First-Out (LIFO) oder umgekehrt First-In-First-Out (FILO). Was bedeuten diese beiden Sätze? Das typischste Beispiel ist etwas, das definitiv jeder sieht, wenn er Fernsehserien, insbesondere Schießereifilme, ansieht: Zeitschriften.

Beim Laden des Magazins werden die Kugeln einzeln in das Magazin gedrückt. Das heißt, die erste Kugel wird unten gedrückt, und beim Schießen werden die Kugeln in umgekehrter Reihenfolge gedrückt wird ausgeworfen und die erste eingeschossene Kugel ist die letzte, die abgefeuert wird.

Dieses Beispiel ist eigentlich sehr anschaulich, lasst uns die Terminologie vereinheitlichen. Das Eindrücken des Geschosses in das Magazin nennt man „Stacking“, das erste Geschoss ist unten, diese Position nennt man „Stack Bottom“, das letzte Geschoss ist oben, diese Position heißt „Stack Top“, das Geschoss abgefeuert Es ist die Kugel oben auf dem Stapel. Dieser Vorgang wird als „Knall“ bezeichnet.

Anhand der Definitionen der oben genannten Begriffe können wir sehen, dass die logischen Operationen des Stapels hauptsächlich „in den Stapel“ und „aus dem Stapel“ erfolgen und das Wichtigste bei der logischen Struktur das „ „oben im Stapel“ und „unten im Stapel“. Der Status beim Öffnen und Schließen des Stapels. Natürlich ist es kein Problem, die Reihenfolge oder Kettenstruktur der logischen Struktur des Stapels zu verwenden. Schauen wir uns das einzeln an.

Sequentieller Stapel

Erstens handelt es sich um eine relativ einfache Implementierung des sequentiellen Stapels. Da es sich um eine sequentielle Struktur handelt, verwenden Sie ein Array. Wir müssen jedoch auch die Situation „oben im Stapel“ oder „unten im Stapel“ aufzeichnen, sodass wir das Array des sequentiellen Stapels in einer Klasse kapseln.

Gleichzeitig definieren Sie in dieser Klasse ein Attribut, um den Zeiger „oben“ oder „unten“ des aktuellen Stapels anzugeben, der tatsächlich die tiefgestellte Position des aktuellen „oben“ oder „unten“ im Array ist. Im Allgemeinen müssen wir nur die Position der „Oberseite des Stapels“ aufzeichnen und die „Unterseite des Stapels“ standardmäßig auf -1 setzen. Da der Array-Index selbst bei 0 beginnt und das Attribut „oben im Stapel“ -1 ist, ist der Stapel ein leerer Stapel, da „oben“ und „unten“ zusammenliegen und keine Elemente darin sind.

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

Das Initialisieren des sequentiellen Stapels ist einfach: mit einem leeren Array und dem Setzen von $top auf -1.

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

Der nächste Schritt sind die „Push“- und „Pop“-Operationen. Schauen wir uns zuerst den Code an.

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;
}

Das Pushen auf den Stapel ist sehr einfach. Fügen Sie einfach Inhalt zu den Array-Elementen hinzu und dann $top++. Wenn es sich jedoch um eine C-Sprache handelt, müssen wir beim Pushen auf den Stapel auch feststellen, ob der Stapel voll ist, da es eine Array-Längenbeschränkung gibt. In PHP haben wir diese Sorge natürlich nicht.

Sequentielles Stapel-Push-Symbol

Beim Öffnen des Stapels müssen Sie feststellen, ob der aktuelle Stapel leer ist. Dabei wird nicht zwischen Sprachen unterschieden, denn wenn er kleiner als -1 ist, wird bei erneuter Verwendung dieses Stapels etwas passieren falsch. Wenn der Stapel beim Öffnen des Stapels bereits leer ist, geben Sie nicht $top-- ein, sondern holen Sie sich einfach das oberste Element des Stapels und geben Sie es zurück.

Sequentielles Stapel-Popping-Symbol

Werfen wir einen Blick auf die Testergebnisse dieses sequentiellen Stapels.

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

Ist es nicht sehr einfach, den Stack über Arrays zu bedienen? Nachdem wir den Kettenstapel gelesen und gelernt haben, werden wir auch über die von PHP für uns vorbereiteten Array-Stack-Betriebsfunktionen sprechen, die bequemer zu verwenden sind.

Kettenstapel

Tatsächlich ist der Kerninhalt der Kettenspeicherstruktur immer noch derselbe. Wir müssen uns auch um die Oberseite unseres Stapels kümmern, und wir müssen uns auch um die Vorgänge innerhalb und außerhalb des Stapels kümmern . In der Kette können wir jedoch die Kopfeinfügung verwenden, das heißt, die eingefügten Daten oben in der Kette belassen, um den „Top-of-Stack“-Effekt zu erzielen. Auf diese Weise benötigen wir kein spezielles Attribut, um die aktuelle oberste Position des Stapels zu speichern. Es wird direkt durch ein Diagramm klarer zu verstehen sein.

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

Die Struktur der Daten ist nur eine typische Kettenstruktur. Die Hauptsache ist, zu sehen, wie der Push-Vorgang ausgeführt wird.

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;
}

Tatsächlich macht die Initialisierung des leeren Stapels im Kettenstapel nicht viel Sinn. Wir können eine Nullvariable direkt definieren und Kettenoperationen darauf ausführen, aber hier bleiben wir immer noch mit dem sequentiellen Stapel vereinheitlicht. So wie der untere Teil des Stapels im sequentiellen Stapel -1 ist, sind wir uns auch im Kettenstapel darüber einig, dass der untere Teil des Stapels ein Nullobjektknoten ist.

接下来就是入栈操作了。这里我们使用的是头插法，其实就是将新元素放到链表的顶端。先实例化一个节点，然后将这个节点的 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视频教程

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung des Stacks in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!