Convertir une file en pile

Exercice de TD · niveau 2 · NSI (terminale), chapitre 1 — Structures de données linéaires

Énoncé

Convertir une file en pile.

On dispose d'une file (sous forme de deque). Écrire une fonction file_vers_pile(file) qui défile tous les éléments et les empile dans une pile (liste), puis renvoie cette pile. Quel est l'ordre obtenu au sommet ?

Corrigé


from collections import deque

def file_vers_pile(file):
    pile = []
    while len(file) > 0:
        x = file.popleft()    # on retire en tete de file (FIFO)
        pile.append(x)        # on empile (sommet = fin de liste)
    return pile

f = deque([1, 2, 3])          # tete = 1
p = file_vers_pile(f)
print(p)                      # [1, 2, 3]  -> sommet = 3

Les éléments sont défilés dans l'ordre $1, 2, 3$ puis empilés : le sommet de la pile devient le dernier défilé, soit $3$ . Le coût est $O (n)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.