La pila se construye sobre el TAD Lista y hay que decidir
cuál extremo es el tope. Con la posición 0, apilar es
insertar(0, e) y desapilar es
eliminar(0); con el final, agregar(e) y
eliminar(tamano() - 1). Debajo puede haber la lista sobre
arreglo o la enlazada: cuatro combinaciones.
1. Cuánto se mueve en cada combinación
Se apila y se desapila n = 50 veces,
contando los elementos que se corren en el arreglo y los nodos que se
visitan en la enlazada. ¿Cuántos sale en cada combinación?
Arreglo, tope al frente
Arreglo, tope al final
Enlazada, tope al frente
Enlazada, tope al final
2. Cómo crece con n
n
arreglo, frente
arreglo, final
enlazada, frente
enlazada, final
Las dos columnas que no son cero crecen como el cuadrado
de n: duplicar n multiplica el trabajo por cuatro.
Las otras dos no crecen.
3. Por qué salen en espejo
El arreglo es gratis por un extremo y caro por el
otro, y la enlazada al contrario. ¿Cuál es la razón?
Lo que quedó
El costo de apilar no es del TAD Pila: sale
de la lista que se ponga debajo y del extremo que se nombre tope. Sobre el
arreglo, el tope va al final y las tres operaciones quedan en Θ(1); sobre
la enlazada, al frente, y también quedan en Θ(1). Las otras dos
combinaciones son Θ(n) por operación y Θ(n²) en la secuencia completa.
Escribir O(1) al lado de apilar sin decir cuál de las cuatro
es afirmar algo que puede ser falso.