Pile de base de la structure de données PHP

Cet article présente principalement la pile de base de la structure de données PHP, qui a une certaine valeur de référence. Maintenant, je la partage avec tout le monde. Les amis dans le besoin peuvent s'y référer

Pile et file d'attente

. Les piles et les files d'attente sont des structures linéaires comme la liste doublement chaînée mentionnée précédemment, qui constitue la base de la structure de données PHP réelle.

Quelles sont les caractéristiques de la stack

La stack suit le principe du dernier entré, premier sorti (LIFO). Cela signifie que la pile n'a qu'une seule sortie pour pousser des éléments et faire éclater des éléments. Lorsque nous effectuons des opérations de poussée ou de pop, nous devons faire attention à savoir si la pile est pleine ou si la pile est vide.

Opérations courantes

Sans plus tarder, regardons directement les opérations courantes que nous effectuons sur la pile.

• push

• pop

• haut

• isEmpty

• ...

Implémentation PHP

Nous définissons d'abord une StackInterface.

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

Examinons l'implémentation de la pile basée sur un tableau

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

Grâce à la puissante structure de tableau de PHP, nous pouvons facilement écrire les méthodes de fonctionnement de base de la pile. Effectivement, la meilleure langue du monde est à la hauteur de sa réputation.

Ensuite, un camarade de classe a dit, vous avez dit que la pile et la liste chaînée précédente sont toutes deux des structures linéaires. Pouvez-vous utiliser directement la liste chaînée pour implémenter la pile ? Cette question est très pointue et la réponse est oui.

Peut-être que des camarades de classe intelligents ont deviné que j'avais déjà défini une interface de pile, et que l'implémentation de la pile doit être plus que celle ci-dessus. Regardons l'implémentation basée sur les listes chaînées.

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

Cela implique la mise en œuvre précédente de la liste chaînée. Les étudiants qui ne comprennent pas les détails peuvent aller ici pour y jeter un œil. Certains étudiants ont demandé à nouveau : à quoi sert cette pile ? C’est une très bonne question. Examinons une exigence.

Veuillez implémenter une classe de vérification d'expression mathématique, entrez l'expression suivante et le résultat attendu est vrai.

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

Ce qui suit est faux.

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

Ce qui suit est également faux.

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

Pensez-y par vous-même, puis regardez la mise en œuvre.

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

Série spéciale

Adresse du répertoire de la série spéciale sur la structure de données de base PHP : https://github.com/... Utilise principalement la syntaxe PHP pour résumer les structures de données et les algorithmes de base. Il existe également des connaissances de base qui sont facilement négligées dans notre développement PHP quotidien et quelques suggestions pratiques sur la standardisation, le déploiement et l'optimisation dans le développement PHP moderne. Il existe également une étude approfondie des caractéristiques du langage Javascript.

Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

Recommandations associées :

Verrouillage et déverrouillage PHP Redis

Méthode PHP de fonctionnement de Beanstalkd et commentaires sur les paramètres

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!