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.