Pila (estructura de datos)
De Wikipedia, la enciclopedia libre
Una pila (stack en inglés) es una estructura de datos de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.
Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apliado (denominado TOS, top of stack en inglés). 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.
Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.
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] Pila de llamadas
La pila de llamadas es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre las subrutinas (llamadas) actualmente en ejecución en un programa en proceso.
Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información 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 ejecución después de esta llamada).
[editar] Ejemplo: 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;
}
}
}
