t[i] et l'affectation t[i] = x se font en O(1) ; l'ajout ou le retrait en fin de liste (append, pop()) se font en O(1) amorti ; l'insertion ou la suppression en début ou au milieu (insert(0, x), pop(0)) se font en O(n), car il faut décaler tous les éléments suivants d'une case.python3 :
>>> pile = []
>>> pile.append("a")
>>> pile.append("b")
>>> pile.append("c")
>>> pile
['a', 'b', 'c']
>>> pile.pop()
'c'
>>> pile
['a', 'b']pop() ne demande aucun décalage : c'est une opération en O(1). Retirer le premier élément avec pop(0) obligerait au contraire à décaler tous les éléments restants d'un rang vers la gauche, en O(n).append empile, pop() dépile.Les piles interviennent dès qu'un traitement doit « revenir en arrière » dans l'ordre inverse de ce qui a été fait : la pile d'appels d'un programme qui exécute des fonctions récursives (chapitre 6), le bouton « précédent » d'un navigateur, ou encore la vérification qu'une expression comporte des parenthèses, crochets et accolades correctement imbriqués.
python3 :
>>> def parentheses_equilibrees(expression):
... pile = []
... paires = {"(": ")", "[": "]", "{": "}"}
... for car in expression:
... if car in "([{":
... pile.append(car)
... elif car in ")]}":
... if not pile:
... return False
... ouvrant = pile.pop()
... if paires[ouvrant] != car:
... return False
... return not pile
...
>>> parentheses_equilibrees("(a[b]{c})")
True
>>> parentheses_equilibrees("(a[b)c]")
False), on dépile [ : comme il ne correspond pas à ), la fonction renvoie immédiatement False. Empiler et dépiler coûtent chacun O(1) ; le parcours complet d'une expression de longueur n coûte donc O(n).dequet.pop(0) coûte O(n), car tous les éléments restants doivent être décalés. On utilise plutôt une file double du module collections, la classe deque, dont les opérations append (enfiler à droite) et popleft (défiler à gauche) coûtent toutes deux O(1).python3 :
>>> from collections import deque
>>> file_attente = deque()
>>> file_attente.append("Alice")
>>> file_attente.append("Bilal")
>>> file_attente.append("Chloé")
>>> file_attente
deque(['Alice', 'Bilal', 'Chloé'])
>>> file_attente.popleft()
'Alice'
>>> file_attente
deque(['Bilal', 'Chloé'])deque.Le premier chapitre de chaque matière reste accessible gratuitement. L'inscription ouvre 7 jours d'accès complet, sans engagement.