Structures de données : Piles et files – Designveloper

Pourquoi des piles et des files ?

Contrairement à un tableau, dans les piles et les files, il n’y a pas d’opération d’accès aléatoire (nous ne pouvons pas accéder directement à un élément avec un ‘index’). Nous avons généralement moins de méthodes/actions sur lesquelles nous pouvons agir comme push(), pop(), peek(), enqueue(), dequeue() qui traitent toutes exclusivement de l’élément au début ou à la fin de la structure Data.

Mais…

Question : Cela semble si limitatif puisque nous ne pouvons accéder qu’au premier ou au dernier élément de la structure de données. Pourquoi voudrions-nous jamais utiliser quelque chose comme ça ? Pourquoi n’utilisons-nous pas simplement des tableaux pour plus de flexibilité ?

Réponse : Les piles et les files d’attente sont généralement des « structures de données de niveau supérieur » construites sur des structures de niveau inférieur (tableau ou liste chaînée) pour limiter les opérations que nous pouvons effectuer sur elles. C’est un avantage si nous voulons un accès contraint.

Avoir cette capacité limitée sur une structure de données est un avantage car nous pouvons contrôler celui qui utilise cette structure de données qui n’effectue que les bonnes opérations qui sont efficaces. Par exemple, nous n’aurons pas à nous demander si quelqu’un a inséré au hasard un élément au milieu de notre liste, mettant en désordre certains invariants. Cela nous a évité bien des problèmes. Regardons-les de plus près.

Qu’est-ce qu’une pile ?

Une pile est une structure de données linéaire à une extrémité qui modélise une pile du monde réel en ayant deux opérations primaires, à savoir, push et pop.

Dans cette image ci-dessous, nous pourrions voir qu’un membre de données est sorti du sommet de la pile et qu’un autre y est ajouté. Il y a un pointeur supérieur qui pointe vers le bloc en haut de la pile. Cela s’explique par le fait que les éléments d’une pile sont toujours retirés et ajoutés au sommet de la pile. Ce comportement est communément appelé LIFO (Last In First Out).

Opérations de la pile

Voici les 2 opérations de base qui peuvent être effectuées sur une pile.

• Fonction Push : Ajouter un élément sur le sommet de la pile
• Fonction Pop : Retirer l’élément supérieur (et éventuellement le retourner)

Visualisation des opérations de base de la pile

De plus, les fonctions supplémentaires suivantes sont prévues pour une pile afin de vérifier son état.

• Fonction Peek : Retourner l’élément supérieur de la pile sans le retirer ou le supprimer
• Fonction isEmpty : Vérifier si la pile est vide ou non
• Fonction isFull : Vérifier si la pile est pleine ou non

Tout fonctionne sur le sommet de la pile. Nous n’avons pas accès à autre chose que le sommet. Ceci est essentiel pour comprendre son fonctionnement.

Analyse de complexité

Le tableau de complexité suivant suppose que vous avez implémenté une pile en utilisant une liste chaînée

Applications des piles

Quand et où une pile est-elle utilisée ? nous utilisons beaucoup la pile en programmation sans même le remarquer, voici quelques exemples :

• Peut être utilisé pour l’évaluation d’expressions (par exemple : un algorithme de triage pour analyser et évaluer des expressions mathématiques).
• Peut être utilisé pour mettre en œuvre des appels de fonction dans la programmation par récurrence.

• Utilisé par les mécanismes d’annulation dans les éditeurs de texte pour annuler le texte que nous avons écrit (Cmd + Z sur Mac OS et Ctrl + Z sur Windows)
• Utilisé dans le navigateur pour naviguer en arrière et vers l’avant
• Peut être utilisé pour effectuer une recherche première en profondeur (DFS) sur un graphe
• Utilisé en coulisses pour supporter la récursion en gardant la trace des appels de fonction précédents

Qu’est-ce qu’une file d’attente ?

Une file d’attente est également une structure de données linéaire qui modélise les files d’attente du monde réel en ayant deux opérations primaires, à savoir, enqueue (nous pouvons penser à cela comme « entrer dans la file d’attente ») et dequeue (nous pouvons également penser à cela comme « supprimer de la file d’attente »). Cette structure est appelée « file d’attente » en raison du fait qu’elle ressemble à une file d’attente du monde réel – (où les gens attendent dans une file d’attente).

Toute file d’attente a une extrémité avant et une extrémité arrière (parfois appelée « arrière »). On insère des éléments par l’arrière et on les retire par l’avant.

Une file d’attente est une structure FIFO (First In First Out – l’élément placé en premier peut être accédé en premier) que l’on trouve couramment dans de nombreux langages de programmation.

Opérations de la file d’attente

Voici les 3 opérations de base qui peuvent être effectuées sur une file d’attente.

• Fonction Enqueue : Ajouter un élément à la fin de la file d’attente
• Fonction Dequeue : Retirer l’élément du début de la file
• Fonction Peeking : Regarder la valeur à l’avant de la file d’attente sans la retirer

Analyse de complexité

Comme nous pouvons le voir sur l’image, les opérations de mise en file d’attente et de sortie de file d’attente prennent un temps constant O(1). Cependant, vérifier si un élément est contenu dans la file d’attente est un temps linéaire O(n) puisque nous aurions potentiellement besoin de parcourir tous les éléments.

Il y a aussi le retrait d’éléments (pas la mise en file d’attente) en interne. Il nécessite un temps linéaire puisque nous devons parcourir tous les éléments dans le pire des cas.

Applications de files d’attente

• Utilisées pour gérer les threads dans le multithreading.
• Peut être utilisé pour garder efficacement la trace des x éléments les plus récemment ajoutés
• Gestion des demandes de serveur Web où nous voulons le premier arrivé premier servi. Par exemple : A tout moment, notre serveur web ne peut servir que jusqu’à maximum 50 personnes simultanément.

Si 70 demandes arrivent dans un court laps de temps, alors nous ne pourrons pas toutes les traiter. Le serveur Web n’extrait donc que 50 demandes de la file d’attente et met les 20 autres en attente. Lorsque le serveur web a fini de traiter une demande, il met en file d’attente la suivante à servir et il continue à le faire jusqu’à ce que la file d’attente soit vide.

• Recherche en largeur-première (BFS) traversée de graphe
• Utilisé pour mettre en œuvre des systèmes de file d’attente (par exemple : files d’attente prioritaires)
• Utilisé dans une imprimante réseau : L’imprimante ne peut servir qu’une seule demande à la fois. Ainsi, si d’autres demandes arrivent lorsque l’imprimante est occupée, le programme qui gère l’imprimante ne va pas rejeter ces demandes mais les mettre dans une file d’attente en attente d’exécution. La première demande sera servie en premier (FIFO).

Nous espérons que cet article vous a donné une image des piles et des files d’attente en tête. N’oubliez pas de vous abonner à notre blog et de suivre Designveloper sur Facebook, Twitter et LinkedIn.

Et voici d’autres articles qui pourraient vous plaire :

• Qu’est-ce que l’architecture d’application Web ?
• Les structures de données et leurs applications
• Qu’est-ce que la notation Big O ?

.