Pile et file d'attente en JavaScript

Découvrez deux structures de données importantes – pile et file d'attente – et comment les implémenter en JavaScript.

Chaque fois que nous développons une nouvelle application, il y a certains sujets auxquels nous devons réfléchir avant d'atteindre notre objectif et avoir un beau résultat. Comment nous allons stocker nos données, comment nous allons gérer la logique d'état, comment nous devons gérer l'authentification, etc.

L'un des plus importants est probablement de savoir comment stocker les données. Les données sont un aspect important de chaque application. C'est ainsi que nous pouvons en savoir plus sur nos utilisateurs et en savoir plus. Ils comptent sur nous pour stocker leurs données, et nous devons gérer ce travail avec précaution.

Nous pouvons considérer les structures de données comme une manière agréable et performante de stocker des données. Il existe différentes structures de données, chacune a un cas d'utilisation différent, mais elles peuvent toutes avoir le même objectif – c'est comment obtenir les meilleures performances lors du stockage et du traitement des données.

Nous utilisons des structures de données dans tous les aspects de programmation informatique, dans nos logiciels, applications, sites Web, CLI, GUI, etc. Chaque programme informatique a une structure de données dedans.

La bonne chose à propos des structures de données est que, en tant qu'algorithmes, les structures de données ne dépendent d'aucun langage spécifique ou cadre. C'est pourquoi ils sont l'un des concepts les plus importants à connaître pour un développeur. Tout le monde peut les comprendre et en apprendre davantage à leur sujet, même les personnes qui ne sont pas des développeurs.

Savoir comment les structures de données fonctionnent vous aidera à mieux réfléchir à votre code et à mieux structurer les solutions à vos problèmes. Chaque problème a différentes solutions possibles que nous pourrions utiliser; tous les problèmes ne sont pas traités de la même manière.

Pile

Imaginez que vous avez une pile d'assiettes à laver après avoir dîné avec votre famille, et que vous êtes responsable de laver cette pile d'assiettes. Comment le commenceriez-vous? Eh bien, la réponse évidente est: du haut.

Une pile est normalement une structure d’éléments séquentiels et ordonnés et elle est basée sur le principe du dernier entré, premier sorti (LIFO). Vous pouvez affirmer que parfois vous pouvez supprimer un élément du milieu de la pile sans réellement retirer la plaque du haut, et c'est un argument valable. Mais parfois, cette solution peut ne pas fonctionner comme prévu. Imaginons que dans certaines situations, nous n'ayons que l'option de supprimer l'élément le plus récent ajouté à la pile.

Une structure de données de pile suit le même principe et on l'appelle une structure de données LIFO. LIFO signifie dernier entré, premier sorti, de la même manière qu'une pile d'assiettes ou d'autres types de pile dans le monde réel fonctionne – l'élément le plus récent ajouté à la pile devrait être le premier sorti.

Une structure de données de pile a deux opérations fondamentales:

1. push —Cette opération est chargée d'insérer ou de pousser un nouvel élément dans la pile.
2. pop —Cette opération est responsable de la suppression de l'élément le plus récent de la pile. [19659016] Une pile est une structure de données linéaire, ce qui signifie que tous les éléments sont disposés dans un ordre séquentiel. Il en résulte que les opérations push et pop ne peuvent avoir lieu qu'à une extrémité de la structure, dans ce cas, le haut de la pile.

   Parfois, il peut y avoir plus de deux opérations dans une structure de données de pile. Parfois, nous pouvons utiliser l'opération isEmpty pour vérifier si la pile est vide et l'opération peek pour renvoyer l'élément supérieur sans modifier la pile.

   Maintenant que nous savons comment fonctionne la structure de données de la pile, commençons l'implémentation en JavaScript

   La bonne chose à propos du travail avec des structures de données de pile en JavaScript est que JavaScript nous fournit déjà les méthodes push et pop dont nous avons discuté. La méthode push ajoute un élément à un tableau et la méthode pop supprime le dernier élément d'un tableau.

   Nous pouvons démarrer notre pile en créant un nouveau tableau nommé stack :

    let  stack  =   [] ; 
   

   Nous pouvons maintenant créer notre opération push . Cette fonction sera chargée de recevoir un élément en argument et d'ajouter cet élément à notre stack .

    const   push   =   ( item )   =>  stack .  push  ( item ) ; 
   

   Maintenant, nous allons créer une autre opération appelée pop ]. Cette fonction sera chargée de supprimer le dernier élément de la pile. Fondamentalement, ce sera le dernier élément ajouté à la pile. Puisque nous ne savons pas exactement quel pourrait être le dernier élément de la pile, cette fonction ne reçoit aucun argument.

    const   pop   =   ()   =>  stack .  pop  () ; 
   

   Nous pouvons également implémenter une structure de données stack en JavaScript en utilisant des classes. Voici comment procéder:

    class   Stack   {
     constructor  ()   {
       this .  stack  =   [] ; 
    } 
     push  ( item )   {
       this .  stack .  push  ( item ) ; 
    } 
     pop  ()   {
       this  .  stack .  pop  () ; 
    } 
   } 
   

   Certains développeurs aiment implémenter des structures de données de pile en utilisant des listes liées au lieu de tableaux en JavaScript. Bien que cela puisse sembler une solution intelligente, les performances ne sont peut-être pas les meilleures.

   Comme Hyunjae Jun l'a souligné ici les performances des tableaux au lieu des listes liées dans la pile les structures de données sont meilleures.

   Il existe des cas spécifiques où les listes chaînées peuvent être plus performantes que les tableaux, mais lorsque vous implémentez des structures de données de pile en JavaScript, préférez toujours les tableaux. Les méthodes de tableau que vous allez utiliser, push et pop, auront une complexité temporelle de O (1) ce qui signifie qu'elles fonctionneront efficacement et auront les meilleures performances possibles.

   File d'attente

   Imaginez que nous ayons une file de personnes pour entrer dans un restaurant spécifique. La dernière personne à faire la queue sera la dernière à entrer dans le restaurant, selon la taille de la file. La première personne à faire la queue sera la première personne à entrer dans le restaurant.

   Une file d'attente est une structure linéaire d'éléments séquentiels et ordonnés, semblable à une pile, à la différence qu'elle fonctionne selon le principe de ] premier entré, premier sorti (FIFO) .

   

   Une structure de données de file d'attente est appelée une structure de données FIFO: c'est une structure d'éléments ordonnés séquentiellement dans laquelle le premier élément à supprimer sera le premier élément ajouté à la file d'attente.

   Une structure de données de file d'attente comporte deux opérations fondamentales:

   1. enqueue —Cette opération est chargée d'insérer ou de pousser un nouvel élément dans la file d'attente.
   2. dequeue —Ceci L'opération est responsable de la suppression de l'élément le plus ancien de la file d'attente.

   Semblable à une pile, nous avons une structure de données linéaire, ce qui signifie que toutes les opérations dans une file d'attente ne peuvent se produire qu'à une extrémité de la structure, dans ce cas, le début de la file d'attente.

   JavaScript est un langage très utile et pratique qui nous fournit de nombreuses méthodes différentes pour nous aider à obtenir de meilleurs résultats. L'avantage de JavaScript est que nous avons aussi une méthode pour supprimer le premier élément d'un tableau, qui est la méthode shift array.

   L'implémentation d'une file d'attente en JavaScript devient très simple et puissante. Nous pouvons définir notre tableau de files d'attente comme suit:

    let  stack  =   [] ; 
   

   Maintenant, nous pouvons créer notre opération de mise en file d'attente pour ajouter un élément à notre queue, exactement comme nous l'avons fait avec l'exemple de pile. Créez une fonction appelée enqueue et passez un argument à cette fonction, comme ceci:

    const   enqueue   =   ( item )   = >  queue .  push  ( item ) ; 
   

   Nous pouvons maintenant créer la fonction pour supprimer le premier élément de notre file d'attente. Nous allons créer une fonction appelée dequeue et cette fonction sera chargée de supprimer le premier élément de notre file d'attente.

    const   dequeue   =   ()   ] =>  file d'attente .  shift  () ; 
   

   Assez facile, hein? Mais il y a des différences cachées que nous pourrions ne pas remarquer au début, en particulier au sujet des performances.

   N'oubliez pas que les méthodes push et pop ont une complexité temporelle de O (1) ? La méthode shift a une complexité temporelle de O (n) .

   Une simple différence dans la complexité temporelle d'un morceau de code peut faire une différence totale en termes d'argent, de coûts et performance pour une entreprise. Si vous prévoyez de travailler avec une structure de données de file d'attente, la meilleure idée possible est de créer votre propre file d'attente.

    function   Queue  ()   {
      this  ].  queue  =   {} ; 
      this .  tail  =   0 ; 
      this .  tête  =   0 ; 
   } 
   
   
   Queue .  prototype .  enqueue   =   function  ( element )   {
      this .  queue  [ this .  tail  ++ ]   =  element ; 
   } 
   
   
   Queue .  prototype .  dequeue   =   function  ()   {
      if   ( this [19659027].  tail  ===   this .  head ) 
          return  undefined
   
      var  element  =   this .  queue  [ this .  head ] ; [19659134] supprimer   this .  elements  [ this .  head  ++ ] ; 
      return  element ; 
   } 
   

   Les structures de données de pile et de file d'attente sont très flexibles et faciles à implémenter, mais il existe différents cas d'utilisation pour chacune d'elles.

   Une pile est utile lorsque nous voulons ajouter des éléments dans une liste dans un ordre séquentiel et supprimez le dernier élément ajouté. Une file d'attente est utile lorsque nous voulons le même comportement, mais au lieu de supprimer le dernier élément ajouté, nous voulons supprimer le premier élément ajouté à la liste.

   Conclusion

   Les structures de données sont un concept très simple et puissant à apprendre à propos. Ils peuvent nous aider à améliorer notre pensée logique, la façon dont nous structurons et résolvons les problèmes, et comment nous trouvons les meilleures solutions pour des cas d'utilisation spécifiques dans nos applications modernes. Les piles et les files d'attente sont deux solutions puissantes qui peuvent nous aider à organiser les données en ordre séquentiel en fonction du résultat que nous voulons obtenir et à avoir des performances efficaces et fantastiques.

   ---