Estructura de Datos Ing. Manuel Guerra

Sesin 2

Pilas Una pila (stack en ingls) es una estructura de datos de tipo LIFO (del

ingls Last In First Out, ltimo en entrar, primero en salir) que permite

almacenar y recuperar datos.

Se aplica en multitud de ocasiones en informtica debido a su

simplicidad y ordenamiento en la propia estructura.

Pilas - Push / Pop

Para el manejo de los datos se cuenta con dos operaciones bsicas:

Apilar (push), que coloca un objeto en la pila,

Au operacin inversa, Retirar (o desapilar, pop), que retira el ltimo

elemento apilado.

En cada momento slo se tiene acceso a la parte superior de la pila, es

decir, al ltimo objeto apilado (denominado TOS, Top of Stack en ingls).

La operacin retirar permite la obtencin de este elemento, que es retirado

de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que

pasa a ser el nuevo TOS.

Por analoga con objetos cotidianos, una operacin apilar equivaldra a

colocar un plato sobre una pila de platos, y una operacin retirar a

retirarlo.

Pilas - Usos

Las pilas suelen emplearse en los siguientes contextos:

Evaluacin de expresiones en notacin postfija (notacin polaca inversa).

Reconocedores sintcticos de lenguajes independientes del contexto

Implementacin de recursividad.

Piense:

Identifique nuevos puntos de uso para las Pilas..

Pilas - Representacin

Identifique donde esta Push, Pop, TOS

Pilas

Pila de Llamadas La pila de llamadas es un segmento de memoria que utiliza esta

estructura de datos para almacenar informacin sobre las llamadas a

subrutinas actualmente en ejecucin en un programa en proceso.

Cada vez que una nueva subrutina es llamada, se apila una nueva

entrada con informacin sobre sta tal como sus variables locales.

En especial, se almacena aqu el punto de retorno al que regresar

cuando sta subrutina termine (para volver a la subrutina anterior y

continuar su ejecucin despus de esta llamada).

Pilas Ejemplo

Pilas Ejemplo

Pilas Ejemplo

Pilas Ejemplo

Pilas Ejemplo

Pilas Preguntas?

Puntos a Considerar

La pila es un contenedor de nodos y tiene dos operaciones bsicas:

push y pop.

Push aade un nodo a la parte superior de la pila anterior, dejando por

debajo de los nodos.

Pop elimina y devuelve el actual nodo superior de la pila.

TOS indica el tope de la pila.

Debe llevar el punto maximo de la pila.

Tarea :

Elabore una pila para manejo unicamente de nombres de personas manejada por vectores, aproveche sus conocimientos para el manejo de procedimientos y funciones.