Pila (estructura de datos)

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.

stack.png

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.

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;
		}
	}
}

Estructura de datos

Gourt Home::Gourt :: Pila (estructura de datos)

Implementación en Java de una pila