tdapila

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 pila comouna 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 pilavací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 : da de alta en lapila 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 nuevo elemento
Desapilaro 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 del tope.
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 componepush con pop, la pila vuelve al estado
previo al push)
1

Algoritmos y Programación II - 7504
empty(new) (la pila se crea vacía)

Curso 2006

not empty(push(s, x)) (luego de hacer un push la pila...