実戦PHPデータ構造基礎のスタック

スタックとキュー
スタックおよびキューは、前述した実戦PHPデータ構造基礎のダブルチェーンテーブルと同様に線形構造である.
スタックの特徴
スタックは後進先出の原則(LIFO)に従う.これは、スタックが要素とポップアップ要素を圧入するための出口が1つしかないことを意味し、圧入またはポップアップ操作を実行するときは、スタックが満タンであるか、スタックが空であるかに注意しなければならない.
一般的な操作
やはりくだらない話は多く言わないで、直接私たちがスタックに対して実行しているよく使われている操作を見てみましょう.

push

pop

top

isEmpty

...

PHP実現
まずStackInterfaceを定義します.

interface StackInterface
{
    public function push(string $item);
    public function pop();
    public function top();
    public function isEmpty();
}

配列ベースのスタック実装を見ると

class ArrStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit = 20)
    {
        $this->limit = $limit;
        $this->stack = [];
    }

    public function __get($val)
    {
        return $this->$val;
    }

    public function push(string $data = null)
    {
        if (count($this->stack) < $this->limit) {
            array_push($this->stack, $data);
        } else {
            throw new \OverflowException('stack is overflow');
        }
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('stack is empty');
        } else {
            return array_pop($this->stack);
        }
    }

    public function isEmpty()
    {
        return empty($this->stack);
    }

    public function top()
    {
        return end($this->stack);
    }

PHPの強力なarray構造のおかげで、スタックの基本的な操作方法を簡単に書きました.やはり世界最高の言葉は名に恥じない.
スタックと前のチェーンテーブルは線形構造だと言っていますが、チェーンテーブルを直接使ってスタックを実現してもいいですか?この問題はとても鋭いですね.答えはいいです.
機知のある同級生はもう推測したかもしれませんが、私は前にスタックインタフェースを定義しました.そのスタックの実現はきっと上の1つだけではありません.チェーンテーブルベースの実装を見てみましょう.

class LinkedListStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit)
    {
        $this->limit = $limit;
        $this->stack = new LinkedList();
    }

    public function top()
    {
        return $this->stack->getNthNode($this->stack->getSize() - 1)->data;
    }

    public function isEmpty()
    {
        return $this->stack->getSize() === 0;
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('stack is empty');
        } else {
            $lastItem = $this->top();
            $this->stack->deleteLast();

            return $lastItem;
        }
    }

    public function push(string $item)
    {
        if ($this->stack->getSize() < $this->limit) {
            $this->stack->insert($item);
        } else {
            throw new \OverflowException('stack is overflow');
        }
    }

これまでのチェーンテーブルの実装については、詳細を知らない学生はここに行ってみることができます.ある同級生はまた、あの宿はいったい何の役に立つのかと聞いた.この問題はとても良くて、需要を見てみましょう.
数学式チェッククラスを実装し、次の式を入力し、結果をtrueとします.

"8 * (9 -2) + { (4 * 5) / ( 2 * 2) }

次はfalseです.

"5 * 8 * 9 / ( 3 * 2 ) )"

以下もfalseです.

"[{ (2 * 7) + ( 15 - 3) ]"

自分で考えて、また下を見て実現します.

class ExpressionChecker
{
    //$expressions[] = "8 * (9 -2) + { (4 * 5) / ( 2 * 2) }";
    //$expressions[] = "5 * 8 * 9 / ( 3 * 2 ) )";
    //$expressions[] = "[{ (2 * 7) + ( 15 - 3) ]";

    public function check(string $expression): bool
    {
        $stack = new \SplStack();

        foreach (str_split($expression) as $item) {
            switch ($item) {
                case '{':
                case '[':
                case '(':
                    $stack->push($item);
                    break;

                case '}':
                case ']':
                case ')':
                    if ($stack->isEmpty()) return false;

                    $last = $stack->pop();

                    if (
                        $item == '{' && $last != '}' ||
                        $item == '(' && $last != ')' ||
                        $item == '[' && $last != ']'
                    )
                        return false;

                    break;
            }
        }

        if ($stack->isEmpty()) {
            return true;
        }

        return false;
    }
}

特集シリーズ
PHP基礎データ構造特集シリーズ目次アドレス:https://github.com/...主にPHP文法を用いて基礎データ構造とアルゴリズムを総括する.また、日常のPHP開発において無視しやすい基礎知識と現代のPHP開発における規範、配置、最適化に関するいくつかの実戦的な提案もあり、Javascript言語の特徴に対する深い研究もある.