Pilas
¿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.
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 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 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?
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
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.
Ahora tú prueban
- Usa una lista como tu pila (
appendpara insertar,poppara eliminar). - Pulsa Check answer para probar tu código.
Una pila es LIFO
Una pila realiza empujar y extraer en un solo extremo — último en entrar, primero en salir.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
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].)
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
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].)
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escriba top(stack) que devuelva el elemento superior (el último) sin eliminarlo. Si la pila está vacía, devuelva None.
Haz clic en Ejecutar para ver la salida aquí.