Stacks · Piles (Stacks)
What is an ADT?
- An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
- You use the operations and ignore how it is built inside.
- A stack, a queue, and a linked list are all ADTs.
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.
A stack is LIFO
- A stack is Last In, First Out (LIFO).
- The last item you add is the first one you take off.
- Think of a stack of plates: you take the top plate first.
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 and pop with a list
- We can build a stack from a Python list.
- push =
stack.append(x)— add to the end (the top). - pop =
stack.pop()— remove and return the end (the top).
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 and empty
- peek at the top without removing it:
stack[-1]. - A stack is empty when
len(stack) == 0. - Popping an empty stack is an error, so check first.
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?
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
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
Common mistakes
- A stack is last-in, first-out: push to the top, pop from the top.
- Check it is not empty before you pop.
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.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
À vous maintenant
- Utilisez une liste comme pile (
appendpour push,poppour retirer). - Appuyez sur Vérifier la réponse pour tester votre code.
A stack is LIFO · Une pile est LIFO
A stack pushes and pops at one end — last in, first out. · Une pile empile et dépile à une seule extrémité — dernier entré, premier sorti.
Start with an empty stack. Push 1, then 2, then 3. Then pop · populer once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].) · Commencez avec une pile vide. Push 1, puis 2, puis 3. Ensuite, pop · populer une fois, stockant la valeur retirée dans top. (top doit être 3 et la pile doit être [1, 2].)
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Use a stack to reverse the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].) · 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].)
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write top(stack) that returns · rendements the top item (the last one) without removing it. If the stack is empty, return None. · Écrivez top(stack) qui retourne l'élément du sommet (le dernier) sans le retirer. Si la pile est vide, retournez None.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.