← Volver a los ejercicios

Una pila es una lista por un solo extremo

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

narreglo, frentearreglo, finalenlazada, frenteenlazada, 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?