PILAS EN C++Prof. Mara A. Garca.

DEFINICINUna pila es una estructura de datos homognea (elementos del mismo tipo), secuencial y de tamao variable. Slo es posible un modo de acceso a esta estructura: a travs de la cabeza de la pila. De este modo podemos aadir un elemento a la cabeza de la pila o extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extraccin e insercin se realizan por el mismo extremo, el ltimo elemento en ser aadido ser el primero en ser extrado; por ello a estas estructuras se las conoce con el nombre de LIFO (last-in, first-out; ltimo en entrar, primero en salir).

La PilaGESTIN DE MEMORIA ESTTICAGESTIN DE MEMORIA DINMICA

EjemplificacionesUn ejemplo tpico de pila lo constituye un montn de platos: Cuando se quiere introducir un nuevo plato, ste se coloca en la posicin ms accesible, encima del ltimo plato. Cuando se toma un plato, ste se extrae, igualmente, del punto ms accesible, el ltimo que se ha introducido. O, si somos ms estrictos, otro ejemplo sera una caja llena de libros. Slo podemos ver cul es el libro que est ms arriba en la caja, y si ponemos o tomamos un libro, slo podremos actuar sobre este primer libro. No podemos siquiera saber el nmero total de libros guardados en la pila. Slo sabremos el nmero de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja.

EjemplificacionesOtro ejemplo natural de la aplicacin de la estructura pila aparece durante la ejecucin de un programa de ordenador, en la forma en que la mquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o funcin) hace que el sistema almacene toda la informacin asociada con ese procedimiento (parmetros, variables, constantes, direccin 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 informacin almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador slo se puede estar ejecutando un procedimiento, esto quiere decir que slo 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.

Operaciones con PilaAsociadas con la estructura pila existen una serie de operaciones necesarias para su manipulacin. stas son:Iniciacin de la estructura:- Crear la pila (CrearPila): La operacin de creacin de la pila inicia la pila como vaca.Operaciones para aadir y eliminar informacin:- Aadir 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 informacin contenida en la pila, como el propio estado de la cima:- Comprobar si la pila est vaca (PilaVacia): Esta operacin 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 especificacin correcta de todas estas operaciones permitir definir adecuadamente una pila.

Operaciones con PilaUna declaracin ms formal de las operaciones definidas sobre la estructura de datos pila, y los axiomas que las relacionan podran ser las siguientes:EstructuraPila ( Valor ) /* Valor ser el tipo de datos que podremos guardar en la pila */OperacionesCREAR_PILA ( ) PilaAPILAR ( Pila , Valor ) PilaDESAPILAR ( Pila ) PilaCIMA_PILA ( Pila ) ValorPILA_VACIA ( Pila ) LgicoAxiomas stack Pila, x Valor se cumple que:PILA_VACIA ( CREAR_PILA ( ) ) ciertoPILA_VACIA ( APILAR ( stack, x ) ) falsoDESAPILAR ( CREAR_PILA ( ) ) errorDESAPILAR ( APILAR ( stack, x ) ) stackCIMA_PILA ( CREAR_PILA ( ) ) errorCIMA_PILA ( APILAR ( stack, x ) ) x

Implementacin mediante estructuras estticasLa forma ms simple, y habitual, de representar una pila es mediante un vector unidimensional. Este tipo de datos permite definir una secuencia de elementos (de cualquier tipo) y posee un eficiente mecanismo de acceso a la informacin contenida en ella.Al definir un array hay que determinar el nmero de ndices vlidos y, por lo tanto, el nmero de componentes definidos. Entonces, la estructura pila representada por un array tendr limitado el nmero de posibles elementos.La parte privada de la clase, ser pues un vector donde guardaremos la informacin. El primer elemento de la pila se almacenar en info[0], ser el fondo de la pila, el segundo elemento en info[1] y as sucesivamente. En general, el elemento i-simo estar almacenado en info[i - 1].Como todas las operaciones se realizan sobre la cima de la pila, es necesario tener correctamente localizada en todo instante esta posicin. Es necesaria una variable adicional, cima, que apunte al ltimo elemento de la pila o nos diga cuantos elementos tenemos en ella.

Implementacin mediante estructuras estticas (Crear-Pila)Resumiendo, la clase Pila contendr, en esta implementacin, la iguiente parte privada:class Pila{public: ...private:Vector vect;int cima;};

Donde Vector ser:typedef Valor Vector[MAX];Suponiendo Valor, el tipo de dato que se puede almacenar en la pila, y MAX una constante que me limita el tamao mximo de la pila.

Implementacin mediante estructuras estticas (Crear-Pila)Operacin CREAR_PILALa creacin de la pila se realizar mediante el constructor por defecto. La tarea que deber realizar ser decir que no existen elementos en la pila:Pila::Pila (void){cima = 0;}

Implementacin mediante estructuras estticas (Pila-Vacia)Operacin PILA_VACIAEsta operacin permitir determinar si es posible eliminar elementos. La pila estar vaca si la cima est apuntando al valor cero.Algoritmo Pila_VaciaEntradastack: PilaSalida(CIERTO, FALSO)InicioSi ( stack.Cima = 0 ) entoncesDevolver ( CIERTO )SinoDevolver ( FALSO )Fin_siFin

bool Pila::PilaVacia (void){return cima == 0;}

Implementacin mediante estructuras estticas (Apilar)Operacin de insercin de informacin (APILAR)La operacin de insercin normalmente se conoce por su nombre ingls Push, o Apilar. La operacin aplicada sobre un pila y un valor x, inserta x en la cima de la pila. Esta operacin est restringida por el tipo de representacin escogido. En este caso, la utilizacin de un array implica que se tiene un nmero mximo de posibles elementos en la pila, por lo tanto, es necesario comprobar, previamente a la insercin, que realmente hay espacio en la estructura para almacenar un nuevo elemento. Con est consideracin, el algoritmo de insercin sera:

Implementacin mediante estructuras estticas (Apilar)Algoritmo ApilarEntradasx: Valor {* elemento que se desea insertar *}stack: Pila de ValorSalidasstackInicio{* comprobar si en la pila se pueden insertar ms elementos *}{* esto es necesario por el tipo de representacin de la estructura *}Si ( stack.Cima = MAX ) entoncesError "pila llena"Sinostack.Cima stack.Cima + 1stack.Info [stack.Cima] xFin_sinoFinbool Pila::Apilar (Valor x){bool error;if (cima == MAX)error = true;else{error = false;info[cima] = x;cima++;}return error;}En la implementacin en C++, tendremos en cuenta que vamos a devolver mediante la funcin si se ha producido algn tipo de error o no, en vez de mostrar un mensaje por pantalla.

Implementacin mediante estructuras estticas (Desapilar)La operacin de borrado elimina de la estructura el elemento situado en la cima. Normalmente recibe el nombre de Pop en la bibliografa inglesa. El algoritmo de borrado sera:Algoritmo DesapilarEntradasstack: Pila de ValorSalidasstackx: ValorInicio{* comprobar si se pueden eliminar elementos de la pila *}{* esta operacin no depende de la representacin, siempre es necesaria *}Si ( Pila_Vacia ( stack ) ) entoncesError pila vaciasinostack.Cima stack.Cima - 1Fin_siFinbool Pila::Desapilar (void){bool error;if (cima == 0)error = true;else{error = false;cima--;}return error;}

Implementacin mediante estructuras estticas (Cima-Pila)Operacin de consulta de informacin (CIMA_PILA)La operacin de consulta de la informacin, slo puede acceder al elemento que est situado en la cima de la pila, y proporcionar su valor. El algoritmo se limitar a devolver el elemento que est situado en la posicin cima de la pila, si existe informacin almacenada en la pila.

Algoritmo Cima_PilaEntradasstack: Pila de ValorSalidasValorInicio{* comprobar si existe informacin en la pila *}{* esta operacin no depende de la representacin, siempre es necesaria *}Si ( Pila_Vacia ( stack ) ) entoncesError pila vaciasinoDevolver ( stack.Info [stack.Cima] )Fin_siFin

bool Pila::CimaPila (Valor & x){bool error;if (cima == 0)error = true;else{error = false;x = info[cima - 1];}return error;}

Implementacin medianteestructuras dinmicasUno de los mayores problemas en la utilizacin de estructuras estticas, estriba en el hecho de tener que determinar, en el momento de la realizacin del programa, el valor mximo de elementos que va a poder contener la estructura. Una posible solucin a este problema es la utilizacin de estructuras dinmicas enlazadas (utilizacin de punteros) tal y como se explic en el primer cuatrimestre.Por tanto, la clase Pila contendr, en esta implementacin, la siguiente parte privada:class Pila{public: ...private:Puntero cima;};

Donde Puntero ser:typedef struct Nodo * Puntero;el tipo Nodo ser:struct Nodo{Valor info;Puntero sig;};Suponiendo Valor, el tipo de dato que se puede almacenar en la pila.La implementacin en este caso de los mtodos de la clase Pila ser la siguiente.

Implementacin medianteestructuras dinmicas (Crear-Pila)Operacin CREAR_PILAstack: Pilastack.Cima NULL

En C++:Pila::Pila (void){cima = NULL;}

Implementacin medianteestructuras dinmicas (Pila-Vacia) Operacin PILA_VACIAEsta operacin permitir determinar si es posible eliminar elementos. La pila estar vaca si la cima est apuntando al valor cero.Algoritmo Pila_VaciaEntradastack: PilaSalida(CIERTO, FALSO)InicioSi (stack.Cima = NULL) entoncesDevolver ( CIERTO )SinoDevolver ( FALSO )Fin_siFinbool Pila::PilaVacia (void){return cima == NULL;}

Implementacin medianteestructuras dinmicas (Apilar) Operacin de insercin de informacin (APILAR)Con la representacin enlazada de la pila, la estructura tiene una menor limitacin en cuanto al posible nmero de elementos que se pueden almacenar simultneamente. Hay que tener en cuenta que la representacin de la pila ya no requiere la especificacin de un tamao mximo, por lo que mientras exista espacio libre en memoria se va a poder reservar espacio para nuevos elementos. Por esa razn, se va suponer en el siguiente algoritmo que la condicin de pila llena no se va a dar y, por lo tanto, no ser necesaria su comprobacin.

Implementacin medianteestructuras dinmicas (Apilar) Algoritmo ApilarEntradastack: Pila de Valoresx: ValorSalidastackVariablep_aux: Puntero_a_Nodo_pilaIniciop_aux Crear_Espaciop_aux^.Info xp_aux^.Sig stack.Cimastack.Cima p_auxFinbool Pila::Apilar (Valor x){bool error;Puntero p_aux;error = false;p_aux = new Nodo;p_aux->info = x;p_aux->sig = cima;cima = p_aux;return error;}

Implementacin medianteestructuras dinmicas (Desapilar) Operacin de eliminacin de informacin (DESAPILAR)La nico que hay que tener en cuenta a la hora de disear un algoritmo para esta operacin es la utilizacin eficiente de la memoria, de forma que el espacio ocupado por el nodo borrado vuelva a estar disponible para el sistema. Recordar que si la pila est vaca no se puede desapilar.

Implementacin medianteestructuras dinmicas (Desapilar) Algoritmo DesapilarEntradastack: Pila de ValorSalidastackx: ValorVariablep_aux: Puntero_a_Nodo_pilaInicioSi (Pila_Vacia (stack) ) entoncesError pila_vaciaSinop_aux stack.Cimastack.Cima p_aux^.SigLiberar_Espacio (p_aux)Fin_siFinbool Pila::Desapilar (void){bool error;Puntero p_aux;if (cima == NULL)error = true;else{error = false;p_aux = cima;cima = cima->sig;delete p_aux;}return error;}

Implementacin medianteestructuras dinmicas (Cima-Pila) Operacin de consulta de informacin (CIMA_PILA)Al elemento "visible" de la pila se puede acceder fcilmente a travs del puntero que le referencia, cima, que siempre debe existir y ser adecuadamente actualizado.

Algoritmo Cima_PilaEntradasstack: Pila de ValorSalidasValorInicio{* comprobar si existe informacin en la pila *}{* esta operacin no depende de la representacin, siempre es necesaria *}Si ( Pila_Vacia ( stack ) ) entoncesError pila vaciasinoDevolver (Cima^.Info)Fin_siFin

bool Pila::CimaPila (Valor & x){bool error;if (cima == NULL)error = true;else{error = false;x = cima->info;}return error;}