Pilas en java

[pic] [pic] [pic]

I N S T I T U T O T EC N O L Ó G I C O D E C A N C Ú N

INGENIERIA
EN
SISTEMAS
COMPUTACIONALES

“PILAS EN JAVA”

Alumnos:

Caamal Can Adriana del Socorro

Mena Chablé Juan Diego

Materia: Estructura de Datos

Cancún, Quintana Roo a Octubre de 2010

INTRODUCCIÓN

PILAS EN JAVA

El método de pila para la evaluación de expresionesfue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Una pila (stack) es una lista o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (Last In First Out), último en entrar, primero en salir) (UEPS)que permitealmacenar y recuperar datos.
[pic]
La pila es un contenedor de nodos y tiene dos operaciones básicas: push (empujar) y pop (sacar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería, por analogía conobjetos cotidianos, una operación empujar equivaldría a colocar un plato sobre una pila de platos, y una operación sacar a retirarlo.
La pila se utiliza siempre que se desea recuperar una serie de elementos en orden inverso a como se introdujeron. La extracción de un elemento de una pila se realiza por la parte superior, de igual forma que la inserción. Esta propiedad implica que el único elementoaccesible de una pila es el último. Estas estructuras se denominan LIFO.
Las pilas se pueden implementar vinculando nodo y también mediante arrays, utilizando una variable auxiliar, cima, que apunte al último elemento de la pila.

En realidad, en Java no es necesario definir la clase Pila, ya que en el paquete java.uti1 viene la clase Stack (pila). La clase Stack hereda de Vector, ya que una pilase puede implementar con eficiencia mediante una tabla que no tiene tamaño fijo.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (TOS, Top of Stack ). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.
Entre lasaplicaciones de las pilas destacan:
• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto
• Uso en la transformación de expresiones aritméticas de notación infija a postfija y en la posterior evaluación de la expresión.
• Su utilización para la transformación de algoritmos recursivos eniterativos.
• Los compiladores utilizan pilas para evaluar expresiones aritméticas y generar código en lenguaje máquina para procesar las expresiones.
• Proporcionan un medio ordenado de demorar la realización de las tareas secundarias que aparecen durante la ejecución del programa.
• Suelen ir asociadas a algoritmos recursivos.
• Tipos derivados: pilas de programas,
• piladel analizador sintáctico (parser).
Operaciones
Una pila cuenta con 2 operaciones imprescindibles: push y pop, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.
• Crear: se crea la pila vacía.
• Apilar: se añade un elemento a la pila.(push)
• Desapilar: se elimina el elemento frontal de la pila.(pop)
• Cima: devuelve el elemento queestá en la cima de la pila. (top o peek)
• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.
La implementación de una pila es muy parecida a la de la lista enlazada, y solo difiere en la forma en que gestionamos los elementos almacenados.
Una pila puede implementarse usando un vector y un entero. El entero cdp(cima de la pila) es el índice del vector correspondiente...