PHPデータ構造の基本スタック-PHPチュートリアル-php.cn

PHPデータ構造の基本スタック

不言

リリース： 2023-04-02 18:14:02

オリジナル

1541 人が閲覧しました

この記事では主に PHP のデータ構造の基本的なスタックを紹介しますが、これは参考になると思いますので、皆さんに共有します。必要な友人は参考にしてください。

スタックとキュー

スタックとキューは、前述した実際の PHP データ構造の基礎である二重リンクリストのような線形構造です。

スタックの特徴とは

スタックは後入れ先出し原則 (LIFO) に従います。これは、スタックには要素のプッシュと要素のポップのためのアウトレットが 1 つしかないことを意味します。プッシュまたはポップ操作を実行するときは、スタックがいっぱいであるか、スタックが空であるかに注意する必要があります。

一般的な操作

早速、スタック上で実行する一般的な操作を直接見てみましょう。

プッシュ
ポップ
##トップ
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(&#39;stack is overflow&#39;);
        }
    }

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

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

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

ログイン後にコピー

PHP の強力な配列構造のおかげで、スタックの基本的な操作メソッドを簡単に記述することができます。案の定、世界最高の言語はその評判に恥じません。

一部の学生は、スタックと前のリンクリストは両方とも線形構造であると言いました。スタックを実装するためにリンクリストを直接使用できますか?この質問は非常に鋭いものであり、答えは「はい」です。

おそらく賢いクラスメートは、私が以前にスタックインターフェイスを定義したことがあり、スタックの実装は上記のものだけではないはずだと推測しているでしょう。リンクリストに基づいた実装を見てみましょう。

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(&#39;stack is empty&#39;);
        } 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(&#39;stack is overflow&#39;);
        }
    }

ログイン後にコピー

これには、以前のリンクリストの実装が含まれます。詳細を理解していない学生は、ここにアクセスして確認してください。何人かの学生は、そのスタックは何に使うのですかと再度尋ねました。とても良い質問ですね。要件を見てみましょう。

数式チェッククラスを実装し、次の式を入力してください。期待される結果は true です。

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

ログイン後にコピー

以下は誤りです。

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

ログイン後にコピー

以下も誤りです。

"[{ (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 言語の特性についても詳しく説明されています。

上記がこの記事の全内容です。皆様の学習に少しでもお役に立てれば幸いです。その他の関連コンテンツについては、PHP 中国語 Web サイトをご覧ください。