Comprendre la structure des données de la pile : un guide étape par étape pour implémenter la pile en JavaScript

Une pile est une structure de données linéaire simple qui fonctionne comme une pile de plaques ?️. Il suit le principe Last In, First Out (LIFO). Considérez-le comme une pile d'assiettes : vous ne pouvez ajouter ou supprimer des assiettes que du haut de la pile.

Pour une meilleure compréhension du stack, embarquons-nous dans un petit voyage d'imagination ?.
Imaginez que vous êtes dans un restaurant chic ?️ et que le personnel de cuisine se prépare pour une soirée bien remplie ?‍?. Dans le coin vaisselle, il y a une grande pile d’assiettes qui attendent d’être utilisées. À mesure que les convives arrivent et que les commandes affluent, le personnel prend les assiettes du haut de la pile. Lorsque des assiettes propres sont ajoutées, elles vont directement au-dessus. Ce système simple garantit que les assiettes du bas de la pile qui sont là depuis le plus longtemps sont utilisées en dernier, tandis que les assiettes fraîchement nettoyées du dessus sont utilisées en premier ✨.

Voici essentiellement comment fonctionne une structure de données Stack. Une pile est une structure de données linéaire qui suit le principe Last In First Out (LIFO). Tout comme pour notre pile d'assiettes, le dernier élément ajouté à une pile est le premier à être supprimé.

Table des matières

Dans ce didacticiel complet sur la structure des données de la pile, nous explorerons les sujets suivants avec une approche simple et conviviale pour les débutants :

1. Qu'est-ce qu'une pile ?
2. Avantages et inconvénients de l'utilisation de Stack
3. Applications réelles des piles
4. Opérations clés sur une pile
5. Implémentation de la pile en JavaScript
6. Conclusion

---

---

Es-tu prêt ? Allons-y

Qu'est-ce qu'une pile ?

Une pile est une structure de données linéaire qui suit le principe Last In, First Out (LIFO). Cela signifie que le dernier élément ajouté à la pile sera le premier à être supprimé. Pensez-y comme à une pile de livres : vous pouvez uniquement ajouter ou supprimer des livres du haut de la pile.

Avantages et inconvénients de l'utilisation de Stack

Avant de continuer avec le flux et d'écrire quelques codes, il est bon de comprendre où et où ne pas utiliser Stack. Le tableau ci-dessous donne en détail les avantages et les inconvénients explicites de Stack.

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

Opérations clés sur une pile

Les opérations fondamentales pouvant être effectuées sur une pile sont :

1. push() : ajoute un élément en haut de la pile.
2. pop() : supprime l'élément le plus haut de la pile.
3. peek() : renvoie l'élément supérieur de la pile sans le supprimer.
4. isEmpty() : Vérifie si la pile est vide.
5. size() : renvoie le nombre d'éléments dans la pile.

Applications réelles des piles

Les piles sont omniprésentes dans l'informatique et le développement de logiciels. Voici quelques applications courantes :

1. Fonctionnalité d'annulation : Dans les éditeurs de texte ou les logiciels de conception graphique, chaque action est poussée sur une pile. Lorsque vous appuyez sur « Annuler », l'action la plus récente est retirée de la pile et inversée.

2. Historique du navigateur : lorsque vous visitez une nouvelle page, elle est placée sur une pile. Le bouton "retour" fait sortir la page actuelle de la pile, révélant la précédente.

3. Pile d'appels de fonction : Dans les langages de programmation, les appels de fonction sont gérés à l'aide d'une pile. Lorsqu'une fonction est appelée, elle est placée sur la pile d'appels. Quand il revient, il s'enlève.

4. Évaluation des expressions : les piles sont utilisées pour évaluer les expressions arithmétiques, en particulier celles en notation postfixée.

5. Algorithmes de retour en arrière : dans des problèmes tels que la résolution de labyrinthes ou d'énigmes, les piles peuvent garder une trace du chemin emprunté, permettant un retour en arrière facile en cas de besoin.

Implémentation de la pile en JavaScript

Maintenant, implémentons une Stack en JavaScript. Il est important de savoir qu’il existe différentes manières d’implémenter une pile en JavaScript. L'une des façons courantes d'implémenter une pile consiste à utiliser un tableau, une autre méthode consiste à utiliser une liste chaînée. Dans cet article, nous allons implémenter une pile utilisant une liste chaînée (liste chaînée unique).

Implémenter la pile à l'aide d'une liste chaînée

J'espère que vous vous souvenez encore du fonctionnement des listes chaînées ? Vous devrez peut-être consulter l'implémentation de la liste chaînée dans l'un de nos articles précédents de cette même série.

Comment implémenter une liste à lien unique en JavaScript

La Grande Solution ? ・ 4 octobre

#javascript #débutants #programmation #dsa

Maintenant, commençons à implémenter notre pile en utilisant une liste à chaînage unique. On y va ?

Tout d'abord, nous allons créer une classe Node pour représenter l'élément individuel de notre pile.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Ensuite, nous créerons une classe Stack pour représenter notre pile.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Opération de poussée

L'opération push ajoute un nouvel élément en haut de la pile. Il crée un nouveau StackNode, définit son prochain pointeur sur le sommet actuel, puis met à jour top pour pointer vers ce nouveau nœud. Enfin, cela incrémente la taille.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

Opération Pop

L'opération pop supprime l'élément le plus haut de la pile. Il vérifie d'abord si la pile est vide. Si c'est le cas, il renvoie un message d'erreur. Sinon, il supprime l'élément supérieur, met à jour le pointeur supérieur vers le nœud suivant et décrémente la taille. Enfin, il renvoie l'élément supprimé.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Opération de coup d'oeil

L'opération peek renvoie l'élément supérieur sans le supprimer. Il vérifie d'abord si la pile est vide. Si c'est le cas, il renvoie un message d'erreur. Sinon, il renvoie les données de l'élément supérieur.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

Opération isEmpty

L'opération isEmpty vérifie si la pile est vide. Il renvoie vrai si la pile est vide, et faux sinon.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

Opération getSize

L'opération getSize renvoie la taille de la pile. Il renvoie le nombre d'éléments dans la pile.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Opération d'impression

L'opération d'impression imprime la pile. Il renvoie les données de l'élément supérieur.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Exemple d'utilisation

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

Dans cette implémentation, nous avons utilisé une structure de liste chaînée (liste chaînée) pour représenter notre pile. Chaque élément est un nœud avec une valeur de données et une référence au nœud suivant. Le haut de la pile est toujours le nœud le plus récemment ajouté.

Conclusion

Les piles sont une structure de données fondamentale en informatique qui suit le principe Last In, First Out (LIFO). Ils sont utilisés dans diverses applications, notamment la gestion des appels de fonction, la mise en œuvre de fonctionnalités d'annulation et l'évaluation d'expressions arithmétiques.

Dans ce tutoriel, nous avons couvert les bases des piles, les avantages et les inconvénients de leur utilisation, ainsi que leur implémentation en JavaScript (à l'aide de listes chaînées). Comprendre les piles ne consiste pas seulement à savoir comment les mettre en œuvre, mais aussi à reconnaître quand elles constituent le bon outil pour résoudre un problème.

En poursuivant votre parcours dans le développement de logiciels, vous constaterez que les piles sont un outil indispensable dans votre boîte à outils de résolution de problèmes. Ils sont simples mais puissants, et leur maîtrise améliorera considérablement votre capacité à concevoir des algorithmes et des structures de données efficaces.

---

---

Restez à jour et connecté

Pour vous assurer de ne manquer aucune partie de cette série et pour me contacter pour des discussions plus approfondies sur le développement de logiciels (Web, serveur, mobile ou Scraping/automatisation), les structures de données et les algorithmes, ainsi que d'autres technologies passionnantes. sujets, suivez-moi sur :

• GitHub
• Linkedin
• X (Twitter)

Restez à l'écoute et bon codage ?‍??

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!