Pila (estructura de datos)
De Wikipedia, la enciclopedia libre
Una pila (stack) es una estructura de datos de tipo LIFO (del inglés Last In First Out) que permite almacenar y recuperar datos mediante operaciones push (apilar) y pop (des-apilar). Estas operaciones se realizan sobre un único extremo llamado cima.
Por analogía con objetos cotidianos, una operación 'push' equivaldría a colocar un plato sobre una pila de platos, y un 'pop' a retirarlo. Esto quiere decir que con una operación 'pop' obtendremos el elemento que se añadió la última vez en la pila (el que se encuentre en la parte superior), al mismo tiempo que lo elimina de la pila.
Las pilas suelen emplearse en los siguientes contextos:
- Evaluación de expresiones en notación postfija (notación polaca inversa).
- Reconocedores sintácticos de lenguajes independientes del contexto
- Implementación de recursividad.
[editar] Implementación en Java de una pila
Una implementación del TDA pila puede realizarse con una lista o con un array.
El tipo java.util.Stack
no es siempre la opción más recomendable, puesto que hereda de java.util.Vector
, permitiendo el acceso a todos los elementos mediante operaciones distintas de push y pop.
public class Pila { NodoPila _ultimo; //Crea una pila public Pila() { _ultimo = null; } //Mete un objeto en la pila public void push(Object o) { NodoPila nuevo; nuevo = new NodoPila(o, _ultimo); _ultimo = nuevo; } imo objeto de la pila public Object pop() { Object resultado; resultado = null; if (_ultimo != null) { resultado = _ultimo.obtenerContenido(); _ultimo = _ultimo.obtenerAnterior(); } return resultado; } //esto es una clase interna class NodoPila { Object _contenido; NodoPila _anterior; public NodoPila(Object contenido, NodoPila anterior) { _contenido = contenido; _anterior = anterior; } public NodoPila obtenerAnterior() { return _anterior; } public Object obtenerContenido() { return _contenido; } } }