Stacks

En bref

Résumé de l’article

Supposons que vous souhaitez stocker l’historique des sites web visités dans votre programme. Une structure appropriée pour stocker la chronologie des sites web visités est une “pile”, comme une pile d’assiettes dans votre placard. Une particularité importante de cette structure de données est que le site visité le plus récemment apparaît en haut de la structure. Une seconde est que lorsqu’il s’agit de retirer un élément, par exemple pour prendre une assiette, le plus récemment ajouté est retiré.

Cette structure de données est omniprésente en informatique, par exemple pour stocker la séquence des appels de fonctions lorsqu’un programme est exécuté.

Comme pour les files d’attente, deux implémentations possibles d’une pile sont proposées. Il est montré qu’elles peuvent être utilisées indépendamment si les primitives abstraient les détails.

Points clés

• Les piles sont des structures de données où le premier élément ajouté est le dernier élément retiré.

• Selon l’implémentation de la pile, certaines opérations peuvent prendre plus de temps que d’autres.

• L’utilisation de primitives permet de cacher les détails d’implémentation.

Contenu de l’article

1 — Qu’est-ce qu’une pile ?

Une pile est une structure de données à accès restreint, ce qui signifie que son traitement est limité à quelques manipulations, appelées “primitives”. Ce type de données est géré de telle sorte que chaque nouvel élément est ajouté en haut de la pile et que le dernier élément ajouté est le premier à être retiré. Cette stratégie d’accès est appelée LIFO (Last In, First Out, dernier entré, premier sorti).

Les piles sont particulièrement utiles pour les processus qui nécessitent que les données attendent un traitement ultérieur. C’est le cas lors du calcul d’une expression arithmétique en notation postfixée, où les données (opérandes) apparaissent avant l’opérateur, par exemple, 3 2 + pour effectuer la somme de 3 et 2.

Les piles sont également idéales pour rendre un traitement récursif itératif. Les valeurs correspondant aux appels récursifs sont empilées, et leur dépilage simule le retour des appels.

2 — Primitives

Dans un programme utilisant une pile, les détails d’implémentation des données sont abstraits. Le programme se contente d’empiler ou de dépiler des éléments de la pile en utilisant des sous-programmes appelés “primitives de gestion”. Les principales primitives pour les opérations sur les piles sont :

• initialize – Initialise la pile.
• push – Ajoute un élément en haut de la pile.
• pop – Retire l’élément en haut de la pile.
• is_empty – Renvoie true si la pile est vide, et false sinon.

3 — Implémentation des piles

Il existe des implémentations testées et optimisées des piles dans presque tous, sinon tous, les langages de programmation. À des fins pédagogiques, deux implémentations possibles des primitives de gestion de pile sont étudiées, dont l’une sera mise en œuvre lors de la séance pratique.

3.1 — Utilisation des listes

La gestion d’une pile peut se faire en ajoutant et retirant des éléments à la fin de la liste. Voici une implémentation possible d’une pile, utilisant une liste pour stocker les informations.

"""
    This module provides an implementation of the primitives to handle a stack of values. 
    The stack is materialized by means of a list with a size limit to simulate an array.
"""

# Needed imports
from typing import List,Any

# define your own custom type
Stack = List[Any]



def initialize () -> Stack:

    """
        Initializes an empty stack.
        In:
            * None.
        Out:
            * An empty stack.
    """

    # We use lists to represent stacks
    return []



def is_empty (stack: Stack) -> bool:

    """
        This function checks if the stack is empty.
        In:
            * stack: Stack to check.
        Out:
            * True if the stack is empty, False otherwise.
    """

    # Check list length
    return len(stack) == 0



def push (stack: Stack, item: Any) -> None:

    """
        This function adds an element to the stack.
        The element is added at the last position of the storage structure.
        In:
            * stack: Stack to modify.
            * item:  Element to add.
    """

    # Add the element to the end of the list
    stack.append(item)



def pop (stack: Stack) -> Any:
    
    """
        This function removes the next element of the stack.
        In:
            * stack: Stack to modify.
        Out:
            * The next element of the stack.
    """
    
    # Extract and return the last element of the list
    return stack.pop()



def display (stack: Stack) -> None:

    """
        This function displays the content of the stack.
        In:
            * stack: Stack to display.
        Out:
            * None.
    """

    # Shows the list
    print(stack)

import java.util.ArrayList;
import java.util.List;

public class ListStack {
    private List<Object> stack;

    public ListStack() {
        this.stack = new ArrayList<>();
    }

    public boolean isEmpty() {
        /**
         * This function checks if the stack is empty.
         * @return True if the stack is empty, False otherwise.
         */
        return this.stack.isEmpty();
    }

    public void push(Object item) {
        /**
         * This function adds an element to the stack.
         * The element is added at the end.
         * @param item Element to add.
         */
        this.stack.add(item);
    }

    public Object pop() {
        /**
         * This function removes the last element of the stack.
         * @return The last element of the stack.
         */
        if (this.stack.isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return this.stack.remove(this.stack.size() - 1);
    }

    public static void main(String[] args) {
        ListStack stack = new ListStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack after pushes: " + stack.stack);
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack after pop: " + stack.stack);
    }
}

3.2 — Utilisation des listes chaînées

Conceptuellement, pour implémenter les primitives qui définissent le comportement d’une structure de données pile, il suffit d’accéder à l’élément en haut de la pile, et au successeur de chaque élément. Une pile se réduit ainsi à un pointeur vers son élément supérieur, et un élément stocke une valeur et un pointeur vers son successeur. Une liste chaînée est une structure de données appropriée pour définir les primitives d’une pile comme illustré dans la figure suivante :

L’implémentation d’une pile utilisant une liste chaînée, plus précisément une liste doublement chaînée, est laissée pour l’activité pratique.

4 — Une utilisation pratique

Un exemple d’utilisation de la structure de données pile est donné ci-dessous avec pour objectif d’inverser une chaîne de caractères (ne le faites jamais en pratique, ce n’est définitivement pas la manière optimale d’effectuer cette tâche). Les caractères composant une chaîne d’entrée sont ajoutés un par un. Les éléments de la pile sont ensuite dépilés un par un pour obtenir l’inverse de la chaîne d’entrée.

# Ask for a string
s = input("Enter a string: ")

# Initialize a stack with the length of the string
my_stack = initialize()
for i in range(len(s)):
    push(my_stack, s[i])

# Process the elements one by one
result = ""
while not is_empty(my_stack):
    result += pop(my_stack)

# Show the result
print(f"Characters of {s} processed in order using a stack:")
display(result)

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports
import java.util.Scanner;

public class Main {
    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Read input from user
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String sentence = scanner.nextLine();
        StackArray<Character> s = new StackArray<>(sentence.length());
        // Fill the stack with characters from the sentence
        for (Character c : sentence.toCharArray()) {
            s.push(c);
        }
        // Pop stack to reverse sentence
        StringBuilder reversedSentence = new StringBuilder();
        while (!s.isEmpty()) {
            reversedSentence.append(s.pop());
        }

        // Print the reversed sentence
        System.out.println("Reversed sentence: " + reversedSentence.toString());
        
        scanner.close();
    }

}

Pour aller plus loin

Rappelez-vous que tous les exemples ci-dessus sont pédagogiques, et faits pour comprendre comment créer des structures. Pour des structures aussi simples, vous devriez utiliser les implémentations par défaut.

Par exemple, il est plus approprié d’utiliser la classe deque de Python dans le package collections, qui fournit les opérations optimales pour manipuler des piles.

Un exercice dans l’activité pratique illustrera le gain d’efficacité lorsque des structures de données appropriées et optimisées sont utilisées.

Pour aller encore plus loin

On dirait que cette section est vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !