Inverser une liste à l'aide d'une pile

L'idée exploite le caractère LIFO de la pile : en empilant tous les éléments puis en les dépilant, on obtient l'ordre inverse.

def inverser(liste):
    pile = []                  # une pile (liste Python)
    for valeur in liste:
        pile.append(valeur)    # on empile tout
    resultat = []
    while len(pile) > 0:
        resultat.append(pile.pop())  # on depile : ordre inverse
    return resultat

# Test
print(inverser([1, 2, 3, 4]))   # [4, 3, 2, 1]

Chaque élément est empilé puis dépilé une fois : le coût est $O(n)$.