Structures de donnees/Piles et Files

Piles et Files

Pile d'assiettes, historique du navigateur, Ctrl+Z... Les PILES sont partout ! Et les FILES d'attente au supermarche ou a l'imprimante aussi. Ces deux structures simples mais puissantes sont fondamentales en informatique. LIFO vs FIFO : decouvrez leurs secrets !

50 min Niveau 3/5 +40 XP

Objectifs

Comprendre le principe LIFO (Last In, First Out)
Implementer une pile avec une liste Python
Implementer une file avec deque
Appliquer piles et files a des problemes concrets

Pieges a eviter

!Confondre pile (LIFO) et file (FIFO)
!Oublier de verifier si la pile est vide avant pop
!Utiliser pop(0) sur liste pour une file (inefficace)
!Ne pas gerer le cas de depassement de capacite

Cours complet

Une pile suit le principe LIFO : Last In, First Out. Le dernier element ajoute est le premier retire. Comme une pile d'assiettes !

# PILE (Stack) - LIFO : Last In, First Out

# Operations de base :
# - push(x) : empiler un element au sommet
# - pop() : depiler et retourner le sommet
# - peek() / top() : consulter le sommet sans le retirer
# - is_empty() : verifier si la pile est vide

# Implementation simple avec une liste Python

class Pile:
    def __init__(self):
        self._elements = []

    def push(self, element):
        """Ajoute un element au sommet."""
        self._elements.append(element)

    def pop(self):
        """Retire et retourne le sommet."""
        if self.is_empty():
            raise IndexError("Pop sur pile vide")
        return self._elements.pop()

    def peek(self):
        """Retourne le sommet sans le retirer."""
        if self.is_empty():
            raise IndexError("Peek sur pile vide")
        return self._elements[-1]

    def is_empty(self):
        """Retourne True si la pile est vide."""
        return len(self._elements) == 0

    def size(self):
        """Retourne le nombre d'elements."""
        return len(self._elements)

    def __str__(self):
        return f"Pile({self._elements})"

# Utilisation
pile = Pile()
pile.push(10)
pile.push(20)
pile.push(30)
print(pile)           # Pile([10, 20, 30])
print(pile.peek())    # 30 (sommet)
print(pile.pop())     # 30 (retire)
print(pile)           # Pile([10, 20])
print(pile.is_empty())  # False

Quiz Piles et Files

5 questions pour valider

PILE (LIFO)

Dernier arrive = Premier sorti

push() / pop()

FILE (FIFO)

Premier arrive = Premier sorti

enqueue() / dequeue()