Pilas y colas

I. Definición de pila:
Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propiaestructura.En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS. La pila es un área de memoria utilizada para el almacenamiento yrecuperación de valores de longitud fija. Hay que recordar que cada programa en ejecución (cada proceso, en términos de Windows), mantiene su propia pila, a la que ningún otro programa puede acceder. Con eso se garantiza la seguridad. Cuando se llama a función todas las variables locales a esa función son almacenadas (instrucciones PUSH de Ensamblador) en la pila, para ser posteriormenterecuperadas.Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese estremos se llama ``la parte superior'' de la pila.Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 9 elelemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.
Figura 9: Pila con 6 elementos

Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es la que se muestra en lafigura 10.

Figura 10: Operación de insertar el elemento G en la pila P
De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debedos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo.
Cuandose desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como:
Retira de la pila hasta que el elemento retirado sea C.
Nisiquiera es necesario decir: ``Retira un elemento de la pila...'' porque es sobreentendido que solamente se puede sacar un elemento a la vez. Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 11
Figura 11: Operación de retirar de la pila P
El concepto de pila es muy importante en computación y en especial enteoría de lenguajes de programación. En lenguajes procedurales como Pascal o C, la pila es una estructura indispensable, debido a las llamadas a función. Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurre una llamada a alguna función, el estado global del sistema se almacena en un registro y éste en una pila. Así que la pila va a contenr todas las llamadas a procedimientosque se hagan.
Cuando se termina de ejecutar algún procedimiento, se recupera el registro que está en la cima de la pila. En ese registro están los valores de las variables como estaban antes de la llamada a la función, o algunas pueden haber cambiado si valor, dependiendo del ámbito de las variables.
Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna...