Piles (Stacks)
Qu'est-ce qu'un TDA ?
- Un Type de Données Abstrait (TDA) est un ensemble de données plus un ensemble d'opérations dessus.
- Vous utilisez les opérations et ignorez comment elles sont construites à l'intérieur.
- Une pile, une file et une liste chaînée sont tous des TDAs.
Une pile est LIFO
- Une pile est Last In, First Out (LIFO - Dernier entré, premier sorti).
- Le dernier élément ajouté est le premier retiré.
- Pensez à une pile d'assiettes : vous prenez la première assiette en haut.
push et pop avec une liste
- Nous pouvons construire une pile à partir d'une liste Python.
- push =
stack.append(x)— ajouter à la fin (le sommet). - pop =
stack.pop()— retirer et retourner la fin (le sommet).
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek et empty
- peek sur le sommet sans le retirer :
stack[-1]. - Une pile est vide quand
len(stack) == 0. - Retirer d'une pile vide est une erreur, donc vérifiez d'abord.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
En pseudocode Cambridge
- L'examen construit une pile à partir d'un tableau plus un pointeur
top(un index).
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
Erreurs courantes
- Une pile est last-in, first-out : push vers le sommet, pop depuis le sommet.
- Vérifiez qu'elle n'est pas vide avant de faire un pop.
À vous maintenant
- Utilisez une liste comme pile (
appendpour push,poppour retirer). - Appuyez sur Vérifier la réponse pour tester votre code.
Une pile est LIFO
Une pile empile et dépile à une seule extrémité — dernier entré, premier sorti.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Commencez avec une pile vide. Push 1, puis 2, puis 3. Ensuite, populer une fois, stockant la valeur retirée dans top. (top doit être 3 et la pile doit être [1, 2].)
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Utilisez une pile pour inverser la liste items. Empilez chaque élément dans une pile, puis dépilez-les tous dans result. (result doit être [3, 2, 1].)
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez top(stack) qui retourne l'élément du sommet (le dernier) sans le retirer. Si la pile est vide, retournez None.
Cliquez sur Exécuter pour voir le résultat ici.