4.1.1 Concepto de pila.

 

Se comienza definiendo lo que es una pila a nivel de programación;

pila es una estructura de datos en la que la inserción y la extracción de elementos se realiza sólo por un extremo que se denomina cabeza. como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. es decir, el último elemento que se metió en la pila será el primero en salir de ella.

 

debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura lifo (last in, first out: último en entrar, primero en salir).

 

ejemplo grafico:

 




en resumen: una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. sólo es

posible un modo de acceso a esta estructura: a través de la cabeza de la pila.

 

en donde se logran a través de funciones como:

 

*insertar

*mostrar

*extraer

*mostrar

 

 

Una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos añadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas estructuras se las conoce con el nombre de LIFO (last-in, first-out; último en entrar, primero en salir). La pila es una lista de elementos caracterizada porque las operaciones de inserción y eliminación de elementos se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente cima (top en la nomenclatura inglesa).

Dada una pila P, formada por los elementos a, b, c, ..., k (P=(a,b,c,...,k)), se dice que a, que es el elemento más inaccesible de la pila, está en el fondo de la pila (bottom) y que k, por el contrario, el más accesible, está en la cima (top).

Las restricciones definidas para la pila implican que si una serie de elementos A, B, C, D, E, F se añaden, en este orden, a una pila entonces el primer elemento que se elimine (borre) de la estructura deberá ser E. Por tanto, resulta que el último elemento que se inserta en una pila es el primero que se borra. Por esa razón, se dice que una pila es una lista o estructura lineal de tipo LIFO (Last In First Out, el último que entra es el primero que sale).

 

 

Un ejemplo típico de pila lo constituye un montón de platos: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se coge un plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. O, si somos más estrictos, otro ejemplo sería una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o cojemos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos el número de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja.

Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos.

Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, direción de retorno, etc...) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado, el que está en la cima). De ahí que una estructura muy apropiada para este fin sea la estructura pila.

Como ya vimos con las estructuras de ejemplo del tema anterior, asociadas con la estructura pila existen una serie de operaciones necesarias para su manipulación. Éstas son:

 

Iniciación de la estructura:

- Crear la pila (CrearPila): La operación de creación de la pila inicia la pila como vacía.

Operaciones para añadir y eliminar información:

- Añadir elementos en la cima (Apilar): pondrá un nuevo elemento en la parte superior de la pila.

- Eliminar elementos de la cima (Desapilar): lo que hará será devolver el elemento superior de la cima y eliminarlo de la pila.

Operaciones para comprobar tanto la información contenida en la pila, como el propio estado de la cima:

- Comprobar si la pila está vacía (PilaVacia): Esta operación es necesaria para poder decidir si es posible eliminar elementos de la pila.

- Acceder al elemento situado en la cima (CimaPila): Nos indica el valor del elemento situado en la parte superior de la pila.

La especificación correcta de todas estas operaciones permitirá definir adecuadamente una pila.

Una declaración más formal de las operaciones definidas sobre la estructura de datos pila, y los axiomas que las relacionan pordrían ser las siguientes:

 

 

Representación de las Pilas en C++ con clases

 

Los lenguajes de programación de alto nivel no suelen disponer de un tipo de datos pila. Aunque, por el contrario, en lenguajes de bajo nivel (ensambladores) es posible manipular directamente alguna estructura pila propia del sistema. Por lo tanto, en general, es necesario representar la estructura pila a partir de otros tipos de datos existentes en el lenguaje.

En C++, lo primero que nos plantearemos serán los métodos a través de los que podremos acceder a la información contenida en la estructura.

Las operaciones van a ser básicamente las que hemos definido en el tipo abstracto de datos, pero ahora habrá que decidir la implementación concreta de las mismas. Como criterio general estableceremos que aquellas funciones que puedan producir error, devolverán un booleano que marque si se ha producido o no error en la operación. Si esas funciones tuvieran que devolver algún valor, lo devolverán por referencia.

Así, Desapilar y CimaPila tendrán el siguiente prototipo:

 

bool Desapilar (Valor &);

bool CimaPila (Valor &);

 

suponiendo Valor, como el tipo de dato guardado en la Pila.

La consulta del estado de la pila (PilaVacia) será:

bool PilaVacia (void);

Recordar que en C++, si la implementación se realiza mediante clases, no es necesario pasar como parámetro el objeto de la consulta, ya que es el propio objeto el que hace la llamada al método que realiza la consulta.

Respecto de Apilar, su prototipo será similar al de Desapilar, aunque según los axiomas, en principio no va a devolver ningún error. En la implementación, la memoria del ordenador es finita, y tendremos en cuenta la posibilidad de que llegue un punto en el que no podamos apilar más elementos.

 

bool Apilar (Valor);

 

Finalmente, nos queda el método de iniciación de la estructura CrearPila. Este método debería ser llamado cada vez que declarasemos un objeto de tipo pila, ya la pila siempre debe empezar sin contener ningún valor.

En las declaraciones de clases en C++, esto se soluciona mediante la inclusión de un constructor por defecto en la clase.

El constructor por defecto es un método especial que es llamado siempre que se instancia (declara) un nuevo objeto de una clase.

Si no existe el constructor por defecto, la instanciación se limita a reservar el espacio necesario para guardar la información del objeto.

Si existe el constructor por defecto, éste es llamado después de la reserva de memoria, y se suele utilizar para iniciar las estructuras con valores ‘correctos’ (y no los valores aleatorios que en principio habría en la memoria.)

El constructor por defecto es un método que tiene el mismo nombre que la clase, no devuelve ningún valor (ni siquiera void) y tiene como parámetro void.