Pilas

Una pila es una estructura de datos en la que los datos similar a una lista en la que los datos se introducen y se sacan por el mismo lugar. Un ejemplo de la vida real puede ser una caja de CD tipo torre, en la que los CD solamente se pueden introducir o sacar por arriba.

Ejemplos de pilas en la vida real


Otros ejemplos de una pila son los siguientes:

  • Una pila de platos (uno sobre otro).
  • Una pila de libros, o meter y sacar libros de una caja.
  • Las estanterías de un supermercado (el fondo de la pila es el fondo del estante, y el tope tiene los productos que podemos tomar facilmente)
  • Ponerse muchas camisas: la última camisa que nos pongamos la podremos sacar facilmente, pero para sacar la primera deberemos sacar antes todas.

Implementación en Logo

Una forma de implementar una pila en Logo es usando listas, que forman parte del lenguaje. Simplemente habría que limitarse a usar las instrucciones que hacen las funciones de PUSH y POP, por ejemplo FIRST, BF y FPUT, esta implementación es sencilla.

Soporte por parte del Intérprete

FMSLogo provee las instrucciones PUSH y POP, que se pueden aplicar a una lista cualquiera que se quiera usar para simular una pila.

Implementación usando un array

La pila también se puede implementar usando un array. Esto es mucho más complicado que usar una lista pero en otros lenguajes puede ser util si se conoce el tamaño máximo que tendrá la pila (en un intérprete Logo puede ser igual acceder a un array que a una lista).

Para implementar la pila con un arreglo hay que tener lo siguiente:

  • Una variable que guarde el tope
  • El largo del array
  • El array que contiene los datos

Para esto suponemos que el array comienza en 0.
Al principio la variable que indica el tope debe iniciarse en 0.
Al hacer PUSH si el tope no es igual al largo del array entonces se suma uno al tope y se introduce el dato en la posición del array indicada por la variable tope. Si el tope es igual al largo del array entonces hay que enviar un error o bien agrandar el array.
Al hacer POP se decrementa el tope de la pila. Si este es 0 se puede enviar un error o no hacer nada, pues la pila ya está vacía.

¿Porqué un arreglo?

Las listas suelen implementarse como un vínculo entre un elemento de la lista y otro, para cada elemento que está en la lista. Sin embargo, en memoria cada elemento de la lista puede muy cerca o muy lejos.

La ventaja de usar un arreglo para la pila es que los arreglos sí son contiguos, por lo que el procesador puede optimizar su acceso, por ejemplo guardándolos en su memoria cache.

Leave a Reply