from collections import deque

# --- Pile (LIFO : Last In, First Out) implémentée sur une liste Python ---
class Pile:
    def __init__(self):
        self._donnees: list = []

    def empiler(self, valeur) -> None:      # push, O(1) amorti
        self._donnees.append(valeur)

    def depiler(self):                       # pop, O(1)
        if self.est_vide():
            raise IndexError("Pile vide")
        return self._donnees.pop()

    def sommet(self):                        # peek, O(1)
        if self.est_vide():
            raise IndexError("Pile vide")
        return self._donnees[-1]

    def est_vide(self) -> bool:
        return len(self._donnees) == 0

# Application : vérifier que des parenthèses/accolades/crochets sont bien équilibrés
def parentheses_valides(expression: str) -> bool:
    correspondance = {')': '(', ']': '[', '}': '{'}
    pile = Pile()
    for caractere in expression:
        if caractere in "([{":
            pile.empiler(caractere)
        elif caractere in ")]}":
            if pile.est_vide() or pile.depiler() != correspondance[caractere]:
                return False
    return pile.est_vide()

assert parentheses_valides("({[]})") is True
assert parentheses_valides("({[}])") is False

# Application : évaluer une expression postfixée (notation polonaise inverse)
def evaluer_postfixe(tokens: list[str]) -> float:
    pile = Pile()
    operations = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
    }
    for token in tokens:
        if token in operations:
            b = pile.depiler()   # ordre important : b est dépilé avant a
            a = pile.depiler()
            pile.empiler(operations[token](a, b))
        else:
            pile.empiler(float(token))
    return pile.depiler()

assert evaluer_postfixe(["3", "4", "+", "2", "*"]) == 14.0   # (3+4)*2

# --- File (FIFO : First In, First Out) implémentée avec deque (O(1) aux deux extrémités) ---
class File:
    def __init__(self):
        self._donnees: deque = deque()

    def enfiler(self, valeur) -> None:       # enqueue, O(1)
        self._donnees.append(valeur)

    def defiler(self):                        # dequeue, O(1) -- deque.popleft() vs list.pop(0) qui est O(n)
        if self.est_vide():
            raise IndexError("File vide")
        return self._donnees.popleft()

    def premier(self):
        if self.est_vide():
            raise IndexError("File vide")
        return self._donnees[0]

    def est_vide(self) -> bool:
        return len(self._donnees) == 0

# --- File à double extrémité (Deque) : ajout/retrait aux deux bouts en O(1) ---
d = deque()
d.append(1)        # ajoute à droite
d.appendleft(0)     # ajoute à gauche
d.pop()             # retire à droite
d.popleft()         # retire à gauche

# Application : fenêtre glissante -- maximum de chaque sous-tableau de taille k
def max_fenetre_glissante(tableau: list[int], k: int) -> list[int]:
    # O(n) au total grâce à un deque d'indices maintenu en ordre décroissant de valeur
    resultat = []
    fenetre = deque()   # stocke des INDICES, pas des valeurs
    for i, valeur in enumerate(tableau):
        while fenetre and tableau[fenetre[-1]] <= valeur:
            fenetre.pop()   # retire les indices dont la valeur est dominée
        fenetre.append(i)
        if fenetre[0] <= i - k:
            fenetre.popleft()   # l'indice est sorti de la fenêtre
        if i >= k - 1:
            resultat.append(tableau[fenetre[0]])
    return resultat

assert max_fenetre_glissante([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]