Programacion Orientada

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 el elemento 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 la figura 10.

Figura 10: Operación de insertar el elementoG 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.

Cuando se 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.

Ni siquiera 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 en teorí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 procedimientos que 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 función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas debe haber quedado en 0 también, de otro modo podría causar algun tipo de error.

Esto nos lleva a pensar en otras utilidades de la pila. La pila sirve para encontrar errores.

La dinámica de la pila, es decir, la manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del ingés first in first out (primero en entrar, primero en salir).

Figura 12: Dinámica de la pila P

En la figura 12 se muestran ``fotografías'' en distintos momentos de la pila, cuando se desea insertar H justo debajo de F. Para hacer esto se requiere, retirar tantos elementos como sean necesarios, aquí se han retirado de la cima G y F para luego insertar H, que quedará posteriormente debajo de F.

Lo que sucede es que, cuando se retira el elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en este caso el elemento objetivo es F, puesto que se desea insertar un elemento debajo de F.

Después de haber insertado F, insertamos de nuevo los elementos F y G en ese orden, además de insertar finalmente el elemento I que queda en la cima de la pila. Enseguida veremos con más detalle las operaciones básicas de las pilas.

Estructura de las colas en C/C++

De manera similar a las pilas, las colas definen una estructura no estándar, de manera que se debe crear un nuevo tipo de dado, el tipo cola, que debe tener los siguientes elementos:

• Un arreglo de elementos de algún tipo específico, puede incluso ser un tipo estándar o no.

• Un número que indica el elemento que está en la posición del frente de la cola.

• Un número que indica el elemento que está en la posición trasera de la cola.

Suponiendo que los elementos son números enteros, una idea para representar una cola en C/C++ es usar un arreglo para contener los elementos y emplear otras dos variables para representar la parte frontal y trasera de la cola.

#define maxQueue 100

...