Stacks · Pilas
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é es un TAD?
- Un Tipo de Dato Abstracto (TDA) es una colección de datos junto con un conjunto de operaciones sobre ellos.
- Utiliza las operaciones e ignora cómo está construido internamente.
- Una pila, una cola y una lista enlazada son todos TDA.
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.
Una pila es LIFO
- Una pila es Último en Entrar, Primero en Salir (LIFO).
- El último elemento que agregas es el primero que retiras.
- Piensa en una pila de platos: tomas primero el plato superior.
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 y pop con una lista
- Podemos construir una pila a partir de una lista de Python.
- push =
stack.append(x)— agregar al final (la parte superior). - pop =
stack.pop()— eliminar y devolver el final (la parte superior).
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 y empty
- peek en la parte superior sin eliminarla:
stack[-1]. - Una pila está vacía cuando
len(stack) == 0. - Hacer un pop en una pila vacía es un error, por lo que debes verificarlo primero.
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 pseudocódigo de Cambridge
- El examen construye una pila a partir de un array más un puntero
top(un índice).
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.
Errores comunes
- Una pila es último en entrar, primero en salir: haz push en la parte superior, haz pop desde la parte superior.
- Verifica que no esté vacía antes de hacer un pop.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
Ahora tú intentarlo
- Usa una lista como tu pila (
appendpara insertar,poppara eliminar). - Presiona Check answer para probar tu código.
A stack is LIFO · Una pila es LIFO
A stack pushes and pops at one end — last in, first out. · Una pila realiza empujar y extraer en un solo extremo — último en entrar, primero en salir.
Start with an empty stack. Push 1, then 2, then 3. Then pop once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].) · Comience con una pila vacía. Empuje 1, luego 2, luego 3. A continuación, extraiga una vez, almacenando el valor eliminado en top. (top debería ser 3 y la pila debería ser [1, 2].)
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
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].) · Use una pila para invertir la lista items. Empuje cada elemento a la pila, luego extraiga todos hacia result. (result debería ser [3, 2, 1].)
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write top(stack) that returns · retornos the top item (the last one) without removing it. If the stack is empty, return None. · Escriba top(stack) que devuelva el elemento superior (el último) sin eliminarlo. Si la pila está vacía, devuelva None.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.