3.1 Pilas
Una pila (stack) es una estructura de datos lineal que sigue el principio LIFO (Last In, First Out), es decir, el último elemento en entrar es el primero en salir. Imagina una pila de platos: el último plato que colocas encima es el primero que quitas.
Gráficamente se vería de la siguiente forma:
3.1.1 Representación en memoria
En el tema 1.4 manejo de memoria se explicó la relación entre la memoria de la computadora y las estrcuturas de datos, para el caso de la pila, al ser esta una estructura de datos, el manejo de memoria se maneja segun lo ya explicado, es decir si la pila se implementa a través de arreglos (Estructuras estáticas) el manejo de memoria será forma estática (no cambia), pero si la pila se implementa a través de una estrucutura dinámica (listas) el manejo de memoria será de forma dinámica (Puede cambiar durante la ejecución del programa).
3.1.2 Funcionamiento
- Orden: Los elementos se apilan uno encima del otro.
- Acceso: Solo se puede acceder al elemento superior de la pila.
-
Operaciones:
- Push: Agregar un elemento a la cima de la pila.
- Pop: Eliminar el elemento superior de la pila.
- Peek: Obtener el valor del elemento superior sin eliminarlo.
- IsEmpty: Verificar si la pila está vacía.
- IsFull: Verificar si la pila está llena (en pilas de tamaño fijo).
3.1.3 Aplicaciones
Las pilas se utilizan en compiladores, sistemas operativos y programas de aplicaciones. Por ejemplo, en la generación de código intermedio (en la construcción de compiladores) se hace uso de una pila para poder generar el código p y el código de 3 direcciones.
Implementación de pilas con la clase Stack
Java ya tiene incluida una clase que nos permite implemntar pilas de forma sencilla, incluyendo las funciones antes mencionandas al igual que otras adicionales. La creación de una pila en java se hace de la siguiente manera:
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack < String > pila = new Stack<>();
//Ingresamon elementos con el metodo push()
pila.push("Luffy"); // La pila contiene: [Luffy]
pila.push("Zoro"); // La pila contiene: [Luffy, Zoro]
pila.push("Nami"); // La pila contiene: [Luffy, Zoro, Nami]
pila.push("Sanji"); // La pila contiene: [Luffy, Zoro, Nami, Sanji]
// Obtener la cima de la pila (Último elemento agregado)
System.out.println("Cima: "+pila.peek());
// Eliminar un elemento con el métoto pop()
pila.pop(); // La pila contiene: [Luffy, Zoro, Nami]
// Despues de eliminar un elemento, la nueva cima es Nami
System.out.println("Cima: "+pila.peek());
}
}
Implementación de una pila con un TDA
Definición del TDA (Clase Personaje)
public class Personaje {
String nombre;
String ocupacion;
String cargo;
public Personaje(String n, String o, String c){
nombre = n;
ocupacion = o;
cargo = c;
}
public String getPersonaje(){
return nombre+" "+ocupacion+" "+cargo;
}
public void setPersonaje(String n, String o, String c){
nombre = n;
ocupacion = o;
cargo = c;
}
}
Definición de una pila TDA (tipo Personaje)
public class Pila {
public static void main(String[] args) {
Stack < Personaje > piratas = new Stack<>();
piratas.push(new Personaje("Boa Hancock", "Pirata", "Capitana"));
piratas.push(new Personaje("Sanji", "Pirata", "Cocinero"));
piratas.push(new Personaje("Nami", "Pirata", "Navegante"));
//Mostrar el contenido de la cima
System.out.println(piratas.peek().getPersonaje()); // Devuelve a Nami
//Quitar un elemento
piratas.pop();
//Mostrar el contenido de la cima
System.out.println(piratas.peek().getPersonaje()); // Devuelve a Sanji
}
}
La forma mas sencilla de implementar una pila en java es con el uso de la clase Stack, como se acaba de ver, pero se debe tener en cuenta que se puede definir o especificar la pilas usando listas enlazadas usando TDAs, únicamente se deben definir las clases que especifiquen el funcionamiento de una lista como una pila y demas clases que cumplan con los requerimientos que satisfagan el problema a solucionar.