Pilas

Estructuras de Datos LinealesPilas
También llamadas LIFO: Last In First Out (Último en Entrar Primero en Salir). Animación Flash de una pila Esta estructura puede compararse con una pila de libros, donde el último en ponerse encima de la pila es el primero en retirarse de ella, y en general los libros se retiran en el orden inverso a como se han apilado. A continuación se muestra la especificación formal del tipo Pila Especificación pila (elemento) usa booleano tipo pila operaciones crear: -> pila apilar: pila x elemento -> pila desapilar: pila -> pila cima: pila -> elemento vacía: pila -> booleano errores desapilar (crear) cima (crear) ecuaciones " p Î pila, " e Î elemento desapilar (apilar (p, e)) = p cima (apilar (p, e)) = e vacía (crear) = cierto vacía (apilar (p, e)) = falso Fespecificación Implementación por vectores En esta implementación la pila se representa por medio de un vector y un apuntador a la cima del vector. elems = = tabla [1..MAX] de elemento pila = = tupla vector: elems cima: entero ftupla función crear retorna pila var p: pila fvar p.cima := 0 retorna p ffuncion función apilar (ent p: pila, ent e: elemento) retorna pila si p.cima = MAX entonces Tratamiento_de_Error sino p.cima := p.cima + 1 p.vector [p.cima] := e fsi retorna p ffuncion Ejercicio: escribir la implementación por medio de vectores del resto de operaciones del TAD pila. Puede verse fácilmente que que el tiempo de ejecución es de Q (1) para todas las operaciones, por tanto es muy eficiente en ejecución, pero tiene el inconveniente de que hay que reservar un máximo de espacio de memoria para el vector, espacio que en muchos casos no se aprovecha.

Autoría Correo de contacto Fecha de actualización