PHPのスタックについて詳しく解説

論理構造も最も単純なものから始めます。スタックとキューはほとんどの人にとって馴染みのある言葉ですが、実際にはヒープとスタックは別のものです。面接中に面接官に混乱させないでください。ヒープはツリー構造、または完全なバイナリ ツリー構造です。今日は主にこのスタックの応用について話します。

#スタックとは何ですか?

スタックは通常、順次データ構造です。その最大の特徴は、後入れ先出し (LIFO)、または逆に先入れ先出し (FILO) です。この 2 つの文は何を意味しますか?最も典型的な例は、テレビ シリーズ、特に銃撃戦映画を見るときに誰もが必ず目にするもの、つまり雑誌です。

マガジンに装填するとき、弾は一発ずつマガジンに押し込まれます、つまり、最初の弾は下部に押し込まれ、発射するときは弾丸は一発ずつマガジンに押し込まれます。弾丸はマガジンの上部から逆の順序で排出され、最初に挿入された弾丸が最後に排出されます。

この例は実際には非常に鮮やかなので、用語を統一しましょう。弾丸をマガジンに押し込むことを「スタッキング」といい、最初の弾丸が一番下にあり、この位置が「スタックボトム」と呼ばれ、最後の弾丸が一番上にあり、この位置が「スタックトップ」と呼ばれます。発射 スタックの「一番上」にある弾丸であり、この操作を「ポップ」と呼びます。

上記の用語の定義から、スタックの論理操作は主に「スタックへの入力」と「スタックからの出力」であり、論理操作で最も注意すべきことがわかります。構造体は、スタックをポップまたはプッシュするときの「スタックの最上位」および「スタックの最上位」「最下位」の状態です。もちろん、スタックの論理構造の順序やチェーン構造を利用しても問題はありませんので、一つずつ見ていきましょう。

シーケンシャル スタック

まず、これはシーケンシャル スタックの比較的単純な実装です。シーケンシャル構造なので配列を使います。ただし、「スタックの一番上」または「スタックの一番下」の状況も記録する必要があるため、シーケンシャルスタックの配列をクラスにカプセル化します。

同時に、現在のスタックの「上部」または「下部」ポインタを示す属性をこのクラスに定義します。これは、実際には、現在のスタックの「上部」または「下部」の添字位置です。配列。一般的に言えば、「スタックの一番上」の位置を記録し、「スタックの一番下」をデフォルトで -1 に設定するだけで済みます。配列の添字自体は 0 から始まるため、「スタックの最上位」属性が -1 の場合、スタックは空のスタックになります。これは、その「最上位」と「最下位」が一緒であり、その中に要素が存在しないためです。

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

シーケンシャル スタックの初期化は簡単で、空の配列を作成し、 $top を -1 に設定します。

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

次のステップは「プッシュ」操作と「ポップ」操作です。最初にコードを見てみましょう。

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

スタックへのプッシュは非常に簡単で、コンテンツを配列要素に追加してから $top するだけです。ただし、C言語の場合は配列長の制限があるため、スタックにプッシュする際にはスタックがいっぱいかどうかも判断する必要があります。もちろん、PHP ではこのような心配はありません。

順次スタック プッシュ アイコン

#スタックをポップするときは、現在のスタックが空かどうかを判断する必要があります。これは言語を区別しません。 -1 より小さい場合、このスタックを再度使用するときに問題が発生します。スタックをポップするとき、スタックがすでに空の場合は、$top-- を与えず、スタックの最上位要素を取得してそれを返すだけです。

シーケンシャル スタック ポップ アイコン

#このシーケンシャル スタックのテスト結果を見てみましょう。

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

配列を介してスタックを操作するのは非常に簡単ですか?チェーンスタックを読んで学習した後、PHP が用意した、より使いやすくなる配列スタック操作関数についても説明します。

チェーン スタック

実際、チェーン ストレージ構造のコアの内容は同じですが、スタックの最上位にも注意する必要があります。スタックの内外での操作。ただし、チェーンではヘッド挿入を使用できます。つまり、挿入されたデータをチェーンの先頭に保持して、「スタックの先頭」効果を実現します。この方法では、スタックの現在の先頭位置を保存するために特別な属性は必要ありません。図を直接見るとより明確に理解できます。

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

データ構造は典型的なチェーン構造ですが、重要なのはプッシュ操作がどのように実行されるかを確認することです。

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

実際には、チェーン スタック内の空のスタックを初期化する操作にはほとんど意味がありません。 null 変数を直接定義して、それに対してチェーン操作を実行することもできますが、ここでもシーケンシャル スタックと統合されたままです。シーケンシャル スタックのスタックの一番下が -1 であるのと同様に、チェーン スタックでも、スタックの一番下が null オブジェクト ノードであることに同意します。

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

以上がPHPのスタックについて詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。