Pilas#
Introducción#
Las pilas son estructuras de datos fundamentales en la programación que siguen el principio de LIFO (Last In, First Out), es decir, el último elemento en entrar es el primero en salir. Esto las hace útiles para resolver problemas en los que la última acción realizada debe ser la primera en revertirse, como en la función «deshacer» de los editores de texto o la navegación de un historial de páginas web.
En esta clase, exploraremos el concepto de pilas, sus operaciones básicas y cómo implementarlas en Java utilizando la clase Stack del paquete java.util y cómo podemos implementarlas manualmente. Al final de la clase, aplicaremos estos conceptos para resolver un problema práctico.
Algunos ejemplos de pilas son:
Esta clase abordará los conceptos de las pilas, su implementación en Java, y ejemplos prácticos que ilustran su uso.
Objetivos#
Comprender el concepto de pilas y su estructura de datos.
Implementar y utilizar pilas en Java.
Aprender las operaciones básicas de una pila:
push,pop,peek,isEmpty.Aplicar pilas en problemas comunes de programación.
Desarrollar una implementación manual de una pila.
¿Qué es una Pila?#
Una pila es una estructura de datos abstracta que permite almacenar y recuperar elementos de manera organizada. En una pila, las operaciones de inserción y eliminación se realizan únicamente en la parte superior. Las principales operaciones de una pila son:
push(elemento): Inserta un nuevo elemento en la parte superior de la pila.
pop(): Elimina y devuelve el elemento en la parte superior de la pila.
peek(): Devuelve el elemento en la parte superior de la pila sin eliminarlo.
isEmpty(): Verifica si la pila está vacía.
Ejemplo de pila en la vida real#
Imagina una pila de platos. El último plato que se apila será el primero en retirarse, siguiendo el principio LIFO.
Tipos de Operaciones en una Pila#
push: Agrega un elemento a la pila.
pop: Remueve el elemento en la parte superior de la pila.
peek: Obtiene el valor en la parte superior sin removerlo.
isEmpty: Comprueba si la pila está vacía.
Implementación de Pilas en Java#
Implementación Simple#
A continuación, se presenta una implementación simple de una pila utilizando una clase genérica en Java.
// Clase PilaGenérica
public class PilaGenerica<T> {
private Object[] elementos;
private int capacidad;
private int cima;
// Constructor
public PilaGenerica(int tamaño) {
capacidad = tamaño;
elementos = new Object[capacidad];
cima = -1;
}
// Método para agregar un elemento a la pila
public void push(T elemento) {
if (cima == capacidad - 1) {
System.out.println("La pila está llena. No se puede agregar el elemento.");
return;
}
elementos[++cima] = elemento;
System.out.println("Elemento " + elemento + " agregado a la pila.");
}
// Método para retirar un elemento de la pila
public T pop() {
if (isEmpty()) {
System.out.println("La pila está vacía. No se puede retirar ningún elemento.");
return null;
}
return (T) elementos[cima--];
}
// Método para obtener el elemento en la cima de la pila sin retirarlo
public T peek() {
if (isEmpty()) {
System.out.println("La pila está vacía. No hay elementos en la cima.");
return null;
}
return (T) elementos[cima];
}
// Método para verificar si la pila está vacía
public boolean isEmpty() {
return cima == -1;
}
// Método para obtener el tamaño de la pila
public int size() {
return cima + 1;
}
}
Edita y prueba el código
// Agrega tu código aquí
Ejemplo de Uso#
A continuación, se presenta un ejemplo de cómo utilizar la clase PilaGenerica para almacenar y manejar una pila de enteros.
// Clase Principal para probar la pila
public class Principal {
public static void main(String[] args) {
PilaGenerica<Integer> pila = new PilaGenerica<>(5);
// Agregar elementos a la pila
pila.push(10);
pila.push(20);
pila.push(30);
// Mostrar el elemento en la cima
System.out.println("Elemento en la cima: " + pila.peek());
// Retirar un elemento
System.out.println("Elemento retirado: " + pila.pop());
// Mostrar el tamaño de la pila
System.out.println("Tamaño de la pila: " + pila.size());
// Retirar todos los elementos
while (!pila.isEmpty()) {
System.out.println("Elemento retirado: " + pila.pop());
}
// Intentar retirar un elemento de una pila vacía
pila.pop();
}
}
Edita y prueba el código
// Agrega tu código aquí
Implementemos la clase del libro guía:
import java.util.ArrayList;
public class GenericStack<E> {
private ArrayList<E> list = new ArrayList<>();
public int getSize() {
return list.size();
}
public E peek() {
return list.get(getSize() - 1);
}
public void push(E o) {
list.add(o);
}
public E pop() {
E o = list.get(getSize() - 1);
list.remove(getSize() - 1);
return o;
}
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString() {
return "stack: " + list.toString();
}
}
Crea una clase llamada TestStack que cree dos pilas con diferente tipo de elementos, agrega unos archivos, imprime la lista, y elimina elementos de esta.
// Agrega tu código aquí
¿Qué diferencia hay entre esta clase y la primera?
Implementación con Nodos#
// Clase Nodo que contiene el dato y una referencia al siguiente nodo
class Nodo<T> {
T dato; // Dato que almacenará el nodo
Nodo<T> siguiente; // Referencia al siguiente nodo en la pila
// Constructor
public Nodo(T dato) {
this.dato = dato;
this.siguiente = null;
}
}
// Clase Pila que utiliza nodos
public class Pila<T> {
private Nodo<T> cima; // Referencia al nodo que está en la cima de la pila
private int tamanio; // Variable para llevar el tamaño de la pila
// Constructor: Inicializa la pila vacía
public Pila() {
this.cima = null; // La pila comienza vacía, por lo que la cima es nula
this.tamanio = 0; // Tamaño de la pila es 0
}
// Método para agregar un elemento a la pila (Push)
public void push(T dato) {
Nodo<T> nuevoNodo = new Nodo<>(dato); // Crear un nuevo nodo con el dato
nuevoNodo.siguiente = cima; // El siguiente nodo del nuevo es el que era la cima
cima = nuevoNodo; // Actualizamos la cima para que sea el nuevo nodo
tamanio++; // Incrementamos el tamaño de la pila
}
// Método para remover y devolver el elemento en la cima de la pila (Pop)
public T pop() {
if (isEmpty()) {
System.out.println("Error: La pila está vacía.");
return null; // Devuelve null si la pila está vacía
}
T dato = cima.dato; // Obtener el dato del nodo en la cima
cima = cima.siguiente; // Mover la cima al siguiente nodo
tamanio--; // Reducimos el tamaño de la pila
return dato; // Devolvemos el dato del nodo removido
}
// Método para ver el elemento en la cima sin removerlo (Peek)
public T peek() {
if (isEmpty()) {
System.out.println("Error: La pila está vacía.");
return null; // Devuelve null si la pila está vacía
}
return cima.dato; // Devuelve el dato del nodo en la cima
}
// Método para verificar si la pila está vacía
public boolean isEmpty() {
return cima == null; // Si la cima es null, entonces la pila está vacía
}
// Método que devuelve el tamaño actual de la pila
public int size() {
return tamanio; // Devuelve el número de elementos en la pila
}
// Método para imprimir el contenido de la pila
@Override
public String toString() {
if (isEmpty()) {
return "La pila está vacía.";
}
StringBuilder sb = new StringBuilder();
Nodo<T> actual = cima;
while (actual != null) {
sb.append(actual.dato).append("\n");
actual = actual.siguiente;
}
return sb.toString();
}
}
Explicación de la clase Pila#
Atributos:
cima: Referencia al nodo en la parte superior de la pila.tamanio: Contador del número de elementos en la pila.
Métodos:
push(T dato): Añade un nuevo elemento a la cima de la pila.pop(): Elimina y devuelve el elemento en la cima de la pila. Si la pila está vacía, se muestra un mensaje de error.peek(): Devuelve el elemento en la cima sin eliminarlo. También muestra un mensaje de error si la pila está vacía.isEmpty(): Devuelvetruesi la pila está vacía, yfalseen caso contrario.size(): Devuelve el número de elementos en la pila.toString(): Recorre la pila y crea una representación en cadena de sus elementos.
Ejemplo#
// Aquí el código de prueba
Aplicaciones#
Las pilas tienen diversas aplicaciones en la programación, algunas de las más comunes son:
Deshacer y Rehacer: Las aplicaciones que permiten «deshacer» (undo) y «rehacer» (redo) utilizan pilas para almacenar las acciones del usuario.
Evaluación de expresiones aritméticas: Al evaluar expresiones aritméticas o convertir notaciones infijas a postfijas, las pilas se utilizan para gestionar los operadores y operandos.
Recorrido en profundidad: En el recorrido de estructuras como árboles o grafos, se puede utilizar una pila para implementar la búsqueda en profundidad (DFS).
Comprobación de paréntesis balanceados: Al analizar expresiones, se utiliza una pila para verificar si los paréntesis están correctamente balanceados.
Otras Aplicaciones#
Reversa de cadenas.
Palíndromes.
Historial de navegación en navegadores web.
Evaluación de programas en lenguajes de programación.
Conversión de expresiones.
Resolución de laberintos.
Gestión de la memoria.
Recursividad.
Seguimiento de llamadas a funciones.
Servicio de interrupciones de hardware.
Resolución de problemas combinatorios mediante backtracking.
Pilas de Java#
Ahora revisemos una implementación más completa y robusta para una pila. Para ello, utilizaremos la clase de vector:
Figura 39 Here is my figure caption!#
Con esta clase en mente, ahora definiremos las pilas heredando algunos métodos y atributos de la clase Vector.
Figura 40 Here is my figure caption!#
Ahora, implementa un código que pruebe la clase pilas que viene con java, Stack.java. Creen dos pilas con diferentes tipos de objetos.
// Agrega tu código aquí
Ejercicio Preparatorio#
Conclusiones#
Las pilas son una estructura de datos fundamental que permite resolver problemas en los que el último elemento en agregarse es el primero en ser procesado. Al comprender su funcionamiento, podemos aplicarlas en la solución de diversos problemas que involucran la reversión de acciones, la evaluación de expresiones y el manejo de recursividad. En Java, la clase Stack del paquete java.util simplifica su implementación, pero también es importante entender cómo implementar pilas manualmente para aprender sobre la gestión de memoria y el control de datos en estructuras más complejas.