Grundlegender Stack der PHP-Datenstruktur

Dieser Artikel stellt hauptsächlich den grundlegenden Stapel der PHP-Datenstruktur vor, der einen gewissen Referenzwert hat. Jetzt kann ich ihn mit allen teilen, die ihn benötigen.

Stack and Queue

Stapel und Warteschlangen sind lineare Strukturen wie die doppelt verknüpfte Liste, die Grundlage der zuvor erwähnten tatsächlichen PHP-Datenstruktur.

Was sind die Eigenschaften des Stacks?

Der Stack folgt dem Last-In-First-Out-Prinzip (LIFO). Dies bedeutet, dass der Stapel nur einen Ausgang zum Schieben und Knallen von Elementen hat. Wenn wir Push- oder Pop-Operationen durchführen, müssen wir darauf achten, ob der Stapel voll oder leer ist.

Allgemeine Operationen

Schauen wir uns ohne weitere Umschweife direkt die allgemeinen Operationen an, die wir auf dem Stapel ausführen.

• drücken

• Pop

• oben

• isEmpty

• ...

PHP-Implementierung

Zuerst definieren wir ein StackInterface.

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

Sehen wir uns die Array-basierte Stack-Implementierung an

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

Dank der leistungsstarken Array-Struktur von PHP können wir die grundlegenden Operationsmethoden des Stacks einfach ausschreiben. Tatsächlich wird die beste Sprache der Welt ihrem Ruf gerecht.

Dann sagte ein Klassenkamerad: Sie sagten, dass sowohl der Stapel als auch die vorherige verknüpfte Liste lineare Strukturen sind. Können Sie die verknüpfte Liste direkt zum Implementieren des Stapels verwenden? Diese Frage ist sehr scharf und die Antwort lautet „Ja“.

Vielleicht haben kluge Schüler schon vermutet, dass ich schon einmal eine Stack-Schnittstelle definiert habe, daher muss die Implementierung des Stacks mehr sein als nur die obige. Schauen wir uns die Implementierung basierend auf verknüpften Listen an.

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

Es handelt sich um die vorherige Implementierung einer verknüpften Liste. Schüler, die die Details nicht verstehen, können hier einen Blick darauf werfen. Einige Schüler fragten noch einmal: Wozu dient dieser Stapel? Das ist eine sehr gute Frage. Schauen wir uns eine Anforderung an.

Bitte implementieren Sie eine Klasse zur Überprüfung mathematischer Ausdrücke, geben Sie den folgenden Ausdruck ein und das erwartete Ergebnis ist wahr.

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

Das Folgende ist falsch.

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

Das Folgende ist ebenfalls falsch.

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

Denken Sie selbst darüber nach und schauen Sie sich dann die Umsetzung an.

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

Sonderserie

PHP-Basisdatenstruktur-Sonderserien-Verzeichnisadresse: https://github.com/... Verwendet hauptsächlich PHP-Syntax, um grundlegende Datenstrukturen und Algorithmen zusammenzufassen. Es gibt auch grundlegende Kenntnisse, die in unserer täglichen PHP-Entwicklung leicht übersehen werden, und einige praktische Vorschläge zur Standardisierung, Bereitstellung und Optimierung in der modernen PHP-Entwicklung. Außerdem gibt es eine eingehende Untersuchung der Eigenschaften der Javascript-Sprache.

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

Sperren und Entsperren von PHP-Redis

PHP-Methode zum Betrieb von Beanstalkd und Parameterkommentaren

Das obige ist der detaillierte Inhalt vonGrundlegender Stack der PHP-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!