Pila (estructura de datos)
Keywords: Pila (estructura de datos), Array, Java (lenguaje de programación), Lista (programación), Notación polaca inversa, Recursividad, Tipo de dato abstracto (TDA)
Una pila (stack) es una estructura de tipo LIFO (del inglés Last In First Out) que permite almacenar y recuperar datos mediante operaciones push (apilar) y pop (des-apilar).
right|Representación gráfica de una pila.
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 una operación 'pop' siempre proporcionará el objeto de inserción más reciente 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.
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;
}
//Retira el último 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;
}
}
}