PHP Master | Structures de données pour les développeurs PHP: piles et files d'attente

Une structure de données, ou Type de données abstraites (ADT), est un modèle défini par une collection d'opérations qui peuvent être effectuées sur elle-même et limitées par les contraintes sur les effets de ces opérations. Il crée un mur entre ce qui peut être fait aux données sous-jacentes et comment il faut faire. La plupart d'entre nous connaissent des piles et des files d'attente dans une utilisation normale quotidienne, mais que les files d'attente et les distributeurs automatiques de supermarchés ont-ils à voir avec les structures de données? Découvrez-le. Dans cet article, je vous présenterai deux types de données abstraits de base - pile et file d'attente - qui ont leurs origines dans l'utilisation quotidienne.

Les plats clés

• Les types de données abstraits (ADT) sont des modèles définis par un ensemble d'opérations qui peuvent être effectuées sur eux. Les piles et les files d'attente sont des adts de base avec des origines dans l'utilisation quotidienne. En informatique, une pile est une collection séquentielle où le dernier objet placé est le premier supprimé (LIFO), tandis qu'une file d'attente fonctionne sur une base de premier-in, première (FIFO).
• Une pile peut être implémentée à l'aide de tableaux, car ils fournissent déjà des opérations push et pop. Les opérations de base définissant une pile incluent init (créer la pile), push (ajouter un élément en haut), pop (supprimer le dernier élément ajouté), en haut (regardez l'élément en haut sans le retirer) et iSempty (return si la pile ne contient plus d'éléments).
• L'extension SPL dans PHP fournit un ensemble de structures de données standard, y compris la classe SplStack. La classe SPLSTACK, implémentée en tant que liste liée à double, offre la capacité d'implémenter une pile traversable. La classe de listlist, implémentée en tant que Splstack, peut traverser la pile vers l'avant (de haut en bas) et vers l'arrière (ascendante).
• Une file d'attente, un autre type de données abstraite, fonctionne sur une base de premier intérieur (FIFO). Les opérations de base définissant une file d'attente incluent init (créez la file d'attente), l'embarcation (ajoutez un élément à la fin), la déshabitation (supprimez un élément de l'avant) et iSempty (renvoyez si la file d'attente ne contient plus d'éléments). La classe Splqueue en PHP, également implémentée à l'aide d'une liste à double liaison, permet la mise en œuvre d'une file d'attente.

piles

En usage courant, une pile est une pile d'objets qui sont généralement disposées en couches - par exemple, une pile de livres sur votre bureau ou une pile de plateaux dans la cafétéria de l'école. Dans le langage informatique, une pile est une collection séquentielle avec une propriété particulière, en ce que le dernier objet placé sur la pile, sera le premier objet supprimé. Cette propriété est communément appelée Last in First Out , ou lifo. Des bonbons, des copeaux et des distributeurs automatiques de cigarettes fonctionnent sur le même principe; Le dernier élément chargé dans le rack est supprimé en premier. En termes abstraits, une pile est une liste linéaire d'éléments dans lesquels tous les ajouts à (un «push») et les suppressions de (une «pop»), la liste est limitée à une extrémité - définie comme le «haut» (de la pile ). Les opérations de base qui définissent une pile sont:

• init - Créez la pile.
• push - Ajoutez un élément en haut de la pile.
• pop - Supprimez le dernier élément ajouté en haut de la pile.
• en haut - Regardez l'élément en haut de la pile sans le retirer.
• iSempty - Renvoyez si la pile ne contient plus d'éléments.

Une pile peut également être mise en œuvre pour avoir une capacité maximale. Si la pile est pleine et ne contient pas suffisamment de créneaux pour accepter de nouvelles entités, il est dit que c'est un débordement - d'où la phrase «Stack Overflow». De même, si une opération POP est tentée sur une pile vide, un «sous-flux de pile» se produit. Sachant que notre pile est définie par la propriété LIFO et un certain nombre d'opérations de base, notamment Push and POP, nous pouvons facilement implémenter une pile à l'aide de tableaux, car les tableaux fournissent déjà des opérations push et pop. Voici à quoi ressemble notre pile simple:

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

Dans cet exemple, j'ai utilisé array_unshift () et array_shift (), plutôt que array_push () et array_pop (), de sorte que le premier élément de la pile est toujours le haut. Vous pouvez utiliser array_push () et array_pop () pour maintenir la cohérence sémantique, auquel cas, le nième élément de la pile devient le sommet. Cela ne fait aucune différence dans les deux sens, car le but d'un type de données abstrait est de résumer la manipulation des données de sa mise en œuvre réelle. Ajoutons quelques éléments à la pile:

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

Pour supprimer certains éléments de la pile:

<span><span><?php
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span>

Voyons ce qui se passe en haut de la pile:

<span><span><?php
</span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>

Et si nous le supprimons?

<span><span><?php
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Feast for Crows'</span></span>

Et si nous ajoutons un nouvel élément?

<span><span><?php
</span></span><span><span>$myBooks->push('The Armageddon Rag');
</span></span><span><span>echo $myBooks->pop(); // outputs 'The Armageddon Rag'</span></span>

Vous pouvez voir que la pile fonctionne sur une dernière base. Tout ce qui est ajouté à la pile est le premier à être supprimé. Si vous continuez à faire preuve d'objets jusqu'à ce que la pile soit vide, vous obtiendrez une exception d'exécution de sous-flux de pile.

PHP Fatal error:  Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33
Stack trace:
#0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop()
#1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...')
#2 {main}
  thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33

Oh, bonjour… PHP a aimablement fourni une trace de pile montrant la pile d'appels d'exécution du programme avant et jusqu'à l'exception!

le splstack

L'extension SPL fournit un ensemble de structures de données standard, y compris la classe SplStack (PHP5> = 5.3.0). Nous pouvons implémenter le même objet, bien que beaucoup plus touristique, en utilisant une splstack comme suit:

<span><span><?php
</span></span><span><span>class ReadingList extends SplStack
</span></span><span><span>{
</span></span><span><span>}</span></span>

La classe SPLSTACK met en œuvre quelques méthodes supplémentaires que nous n'avons définies à l'origine. En effet, SplStack est implémenté en tant que liste liée à une liaison double, qui offre la capacité d'implémenter une pile traversable. Une liste liée, qui est un autre type de données abstrait lui-même, est une collection linéaire d'objets (nœuds) utilisée pour représenter une séquence particulière, où chaque nœud de la collection maintient un pointeur vers le nœud suivant de la collection. Dans sa forme la plus simple, une liste liée ressemble à ceci:

Dans une liste à double liaison, chaque nœud a deux pointeurs, chacun pointant vers les nœuds suivants et précédents de la collection. Ce type de structure de données permet une traversée dans les deux directions.

Les nœuds marqués d'une croix (x) indiquent un nœud nulle ou sentinelle - qui désigne l'extrémité du chemin de traversée (c'est-à-dire le terminateur de chemin). Étant donné que ReadingList est implémenté en tant que SPLSTACK, nous pouvons traverser la pile vers l'avant (de haut en bas) et en arrière (ascendante). Le mode de traversée par défaut pour SplStack est LIFO:

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

Pour traverser la pile dans l'ordre inverse, nous définissons simplement le mode itérateur sur FIFO (premier dans, premier sorti):

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

files d'attente

Si vous avez déjà été en ligne à la caisse des supermarchés, vous saurez que la première personne en ligne est en premier. Dans la terminologie informatique, une file d'attente est un autre type de données abstrait, qui fonctionne sur une base en premier dans la base de la première sortie , ou FIFO. L'inventaire est également géré sur une base FIFO, en particulier si ces éléments sont de nature périssable. Les opérations de base qui définissent une file d'attente sont:

• init - Créez la file d'attente.
• ENQUEUe - Ajoutez un élément à la «fin» (queue) de la file d'attente.
• Dequeue - Retirez un élément du «front» (tête) de la file d'attente.
• iSempty - Renvoyez si la file d'attente ne contient plus d'éléments.

Étant donné que Splqueue est également implémentée à l'aide d'une liste liée à une liaison double, la signification sémantique de Top et Pop est inversée dans ce contexte. Redéfinissons notre classe de listes de lecture comme une file d'attente:

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

Liste de listes spldoubly implémente également l'interface ARRAYACCESS afin que vous puissiez également ajouter des éléments à Splqueue et Splstack comme éléments de tableau:

<span><span><?php
</span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>

Pour supprimer les éléments de l'avant de la file d'attente:

<span><span><?php
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span>

Enqueue () est un alias pour push (), mais notez que dequeue () n'est pas un alias pour pop (); pop () a une signification et une fonction différentes dans le contexte d'une file d'attente. Si nous avions utilisé POP () ici, il supprimerait l'élément de la fin (queue) de la file d'attente qui viole la règle FIFO. De même, pour voir ce qui est à l'avant (tête) de la file d'attente, nous devons utiliser le bas () au lieu de TOP ():

<span><span><?php
</span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>

Résumé

Dans cet article, vous avez vu comment les types de données abstraits de pile et de file d'attente sont utilisés dans la programmation. Ces structures de données sont abstraites, en ce qu'elles sont définies par les opérations qui peuvent être effectuées sur elle-même, créant ainsi un mur entre sa mise en œuvre et les données sous-jacentes. Ces structures sont également limitées par l'effet de ces opérations: vous ne pouvez qu'ajouter ou supprimer les éléments du haut de la pile, et vous ne pouvez supprimer que les éléments de l'avant de la file d'attente, ou ajouter des éléments à l'arrière de la file d'attente. Image d'Alexandre Dulaunoy via Flickr

Questions fréquemment posées (FAQ) sur les structures de données PHP

Quels sont les différents types de structures de données dans PHP?

PHP prend en charge plusieurs types de structures de données, y compris des tableaux, des objets et des ressources. Les tableaux sont les structures de données les plus courantes et polyvalentes en PHP. Ils peuvent contenir tout type de données, y compris d'autres tableaux, et peuvent être indexés ou associatifs. Les objets en PHP sont des cas de classes, qui peuvent avoir des propriétés et des méthodes. Les ressources sont des variables spéciales qui détiennent des références aux ressources externes, telles que les connexions de base de données.

Comment puis-je implémenter une pile dans PHP?

Une pile est un type de structure de données qui suit le LIFO ( Principe du dernier dans, premier sorti). Dans PHP, vous pouvez utiliser la classe SplStack pour implémenter une pile. Vous pouvez pousser des éléments sur la pile à l'aide de la méthode push () et des éléments POP de la pile à l'aide de la méthode pop ().

Quelle est la différence entre les tableaux et les objets dans PHP?

Les tableaux et les objets en PHP sont les deux types de structures de données, mais ils ont des différences clés. Les tableaux sont des listes simples de valeurs, tandis que les objets sont des instances de classes et peuvent avoir des propriétés et des méthodes. Les tableaux peuvent être indexés ou associatifs, tandis que les objets utilisent toujours des touches de chaîne. Les tableaux sont plus polyvalents et plus faciles à utiliser, tandis que les objets fournissent plus de structure et d'encapsulation.

Comment puis-je utiliser des structures de données pour améliorer les performances de mon code PHP?

L'utilisation de la bonne structure de données peut améliorer considérablement les performances de votre code PHP. Par exemple, si vous devez stocker un grand nombre d'éléments et rechercher fréquemment des éléments spécifiques, l'utilisation d'une table de hachage ou d'un ensemble peut être beaucoup plus rapide que d'utiliser un tableau. De même, si vous avez besoin d'ajouter et de supprimer fréquemment des éléments aux deux extrémités, l'utilisation d'un désactive peut être plus efficace que d'utiliser un tableau.

Quelle est la classe SplDoublyLinked en php?

La classe SpldoublyLinkedLedList Dans PHP est une structure de données qui implémente une liste doublement liée. Il vous permet d'ajouter, de supprimer et d'accès aux éléments aux deux extrémités de la liste en temps constant. Il fournit également des méthodes d'itération sur les éléments de la liste et pour tri les éléments.

Comment puis-je implémenter une file d'attente dans PHP?

Une file d'attente est un type de structure de données qui suit Le principe FIFO (premier dans, premier sorti). Dans PHP, vous pouvez utiliser la classe Splqueue pour implémenter une file d'attente. Vous pouvez enterrer des éléments sur la file d'attente à l'aide de la méthode ENQUEUe () et les éléments de désactivation de la file d'attente à l'aide de la méthode Dequeue ().

Quelle est la différence entre une pile et une file d'attente en php?

Une pile et une file d'attente sont les deux types de structures de données, mais elles ont une différence clé dans la façon dont les éléments sont ajoutés et supprimés. Une pile suit le principe LIFO (dernier dans, premier sorti), ce qui signifie que le dernier élément ajouté est le premier à être supprimé. Une file d'attente, en revanche, suit le principe FIFO (premier dans, premier sorti), ce qui signifie que le premier élément ajouté est le premier à être supprimé.

Comment puis-je utiliser la classe SPLHEAP en php?

La classe SPLHEAP en PHP est une structure de données qui implémente un tas. Un tas est un type d'arbre binaire où chaque nœud parent est inférieur ou égal à ses nœuds enfants. Vous pouvez utiliser la classe SPLHEAP pour créer un mine-heap ou un max-heap, et pour ajouter, supprimer et accéder aux éléments dans le tas.

Quels sont les avantages de l'utilisation des structures de données en php?

L'utilisation de structures de données en PHP peut fournir plusieurs avantages. Ils peuvent vous aider à organiser vos données d'une manière plus efficace et logique, ce qui peut rendre votre code plus facile à comprendre et à maintenir. Ils peuvent également améliorer les performances de votre code, en particulier lorsqu'ils traitent de grandes quantités de données ou d'opérations complexes.

Comment puis-je implémenter un arbre binaire en php?

Un arbre binaire est un type de la structure des données où chaque nœud a au plus deux enfants, appelés l'enfant gauche et l'enfant droit. Dans PHP, vous pouvez implémenter un arbre binaire en utilisant une classe qui a des propriétés pour la valeur du nœud et des enfants gauche et droit. Vous pouvez ensuite utiliser des méthodes pour ajouter, supprimer et rechercher des nœuds dans l'arborescence.

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!