Hay cuatro formas de tener una pila con el mismo contrato:
el arreglo con tope, la lista sobre arreglo con el tope al frente, la lista
enlazada con el tope al frente y la pila directa sobre nodos. Tres programas
distintos, y para cada uno la que conviene.
1. Un tope conocido y poca memoria
El programa corre en un equipo con memoria escasa y
se sabe, por el enunciado del problema, que nunca habrá más de 200
elementos en la pila a la vez.
2. Sin saber cuántos elementos llegan
El programa lee de la entrada hasta que se acaba y
no hay ninguna cota: pueden llegar diez elementos o diez millones.
3. Una lista que ya existe
El programa ya tiene una Lista enlazada
cargada y probada, y hay que ofrecer sobre ella una vista de pila, sin
copiar los elementos a otra parte ni volver a escribir el manejo de
nodos.
4. El techo y lo que cuesta no tenerlo
Con CAPACIDAD = 500 se intenta apilar
20000 elementos en cada una. ¿Cuántos quedan dentro, y cuánta memoria
ocupan los nodos de la enlazada?
Caben en el arreglo
Caben en la enlazada
KiB de los nodos de la enlazada
Lo que quedó
Ninguna de las cuatro gana en todo. El arreglo con tope
da Θ(1) en las tres operaciones y no paga un puntero por elemento, a
cambio de reservar CAPACIDAD casillas aunque la pila esté
vacía y de detenerse en la que no cabe. La enlazada con el tope al frente
da Θ(1) en las tres y crece mientras haya memoria, a cambio de un puntero
por elemento. La lista sobre arreglo con el tope al frente es la única que
cobra Θ(n) por operación, y esa no se escoge para una pila. La pregunta no
es cuál es mejor, sino si se sabe de antemano cuántos elementos van a
caber.