Ingeniero

Algoritmos y Programación II - 7504 Curso 2006
TDA PILA (Stack)
Una pila es un contenedor de objetos que se insertan y se eliminan siguiendo el principio ‘Ultimo en
entrar, primero en salir’(L.I.F.O.= ’Last In, First Out’).
En ese sentido puede decirse que una cola es una clase especial de lista en la cual todas las inserciones
(alta ,apilar o push) y borrados (baja, desapilar o pop) tienenlugar en un extremo denominado extremo,
cabeza o tope.
El Tope de la pila corresponde al elemento que entró en último lugar, es decir que saldrá en la próxima
baja.
Se puede considerar una pilacomo una estructura ideal e infinita, o bien como una estructura finita.
Operaciones básicas o primitivas para pilas infinitas
Crear o New : crea la pila
Precondiciones : no tiene
Postcondiciones :una pila vacía preparada para ser usada.
Tope o Top : retorna el valor del tope de la pila
Precondiciones : la pila , ya creada, no debe estar vacía.
Postcondiciones: no tiene
Apilar o Push : dade alta en la pila a un elemento (que se ubicará en el tope) pasado por argumento
Precondiciones : la pila debe haber sido creada.
Postcondiciones : la pila modificada con la inserción del nuevoelemento
Desapilar o Pop : elimina el elemento del tope de la misma.
Precondiciones : la pila , ya creada, no debe estar vacía.
Postcondiciones : pila modificada por la eliminación del elemento deltope.
Vacia o Empty : devuelve un valor indicando si la pila está vacía.
Precondiciones : la pila debe haber sido creada
Postcondiciones : no tiene
En símbolos:
Primitivas:
push: PILA[G] x GPILA[G]
pop: PILA[G] PILA[G]
top: PILA[G] G
empty: PILA[G] BOOLEAN
new: PILA[G]
Axiomas :
top(push(s, x)) = x (si se hace top luego de push, se obtiene el elemnto
insertado con ese push)pop(push(s, x)) = s (si se compone push con pop, la pila vuelve al estado
previo al push)
1
Algoritmos y Programación II - 7504 Curso 2006
empty(new) (la pila se crea vacía)
not empty(push(s, x))...