Fundamentos de Estructuras de Datos: Pilas, Colas y Recursividad en Programación

Estructuras de Datos

Una estructura de datos es una representación de datos junto con las operaciones permitidas sobre dichos datos. Es una colección de datos a los que hacemos referencia bajo un nombre (pueden ser simples o estructurados).

Colecciones Genéricas

Las colecciones genéricas o predeterminadas permiten forzar la seguridad de los tipos en tiempo de compilación en las colecciones.

Pilas (Stack)

Una pila (stack) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In, First Out: último en entrar, primero en salir). Permite almacenar y recuperar datos.

Operaciones Fundamentales de la Pila

push(dato) - Añadir elemento

Si (estaLlena()) entonces
  escribir "Desbordamiento (Stack Overflow)"
sino
  tope = tope + 1
  Pila[tope] = dato
finSi

pop() - Extraer elemento

Si (estaVacia()) entonces
  escribir "Subdesbordamiento (Stack Underflow)"
  regresar NULO // O un valor especial que indique error
sino
  dato = Pila[tope]
  tope = tope - 1
  regresar dato
finSi

estaVacia() - Comprobar si la pila está vacía

Si (tope == -1) entonces // Asumiendo que -1 indica pila vacía
  regresar verdadero
sino
  regresar falso
finSi

estaLlena() - Comprobar si la pila está llena

Si (tope == CAPACIDAD_MAXIMA - 1) entonces // CAPACIDAD_MAXIMA es el tamaño del arreglo
  regresar verdadero
sino
  regresar falso
finSi

Aplicaciones de las Pilas

• Llamadas a subprogramas
• Recursividad
• Tratamiento de expresiones aritméticas
  • Notación polaca
  • Análisis sintáctico

Implementación de Pila en Java

public class Pila<T> {
    private T[] pila;
    private int tope;
    private static final int CAPACIDAD_POR_DEFECTO = 10;

    @SuppressWarnings("unchecked")
    public Pila(int capacidad) {
        if (capacidad <= 0) {
            // Considerar lanzar IllegalArgumentException
            System.out.println("Capacidad debe ser positiva, usando capacidad por defecto.");
            this.pila = (T[]) new Object[CAPACIDAD_POR_DEFECTO];
        } else {
            this.pila = (T[]) new Object[capacidad];
        }
        this.tope = -1; // Pila inicialmente vacía
    }

    public Pila() {
        this(CAPACIDAD_POR_DEFECTO);
    }

    public void push(T objeto) {
        if (estaLlena()) {
            System.out.println("Desbordamiento (Pila llena)");
        } else {
            tope++;
            pila[tope] = objeto;
        }
    }

    public T pop() {
        if (estaVacia()) {
            System.out.println("Subdesbordamiento (Pila vacía)");
            return null;
        } else {
            T objeto = pila[tope];
            pila[tope] = null; // Facilitar al recolector de basura
            tope--;
            return objeto;
        }
    }

    public boolean estaLlena() {
        return tope == pila.length - 1;
    }

    public boolean estaVacia() {
        return tope == -1;
    }

    // Método adicional útil
    public T peek() {
        if (estaVacia()) {
            System.out.println("Pila vacía, no se puede hacer peek");
            return null;
        }
        return pila[tope];
    }
}

Recursividad

La recursividad es una técnica de programación donde un método se llama a sí mismo para resolver un problema. El problema se resuelve dividiéndolo en subproblemas idénticos pero de menor tamaño. La manera en la cual el tamaño del problema disminuye asegura que el caso base (la condición de terminación) eventualmente se alcanzará. Es una técnica de programación muy potente que puede ser usada en lugar de la iteración.

Tipos de Recursividad

Directa

El subprograma se llama directamente a sí mismo.

Indirecta

Un subprograma llama a otro subprograma y este, a su vez, llama al primero.

Colas (Queue)

Una cola (queue) es una estructura de datos lineal donde los elementos se insertan por un extremo (final o rear) y se eliminan por el otro extremo (frente o front). Una cola es una colección de objetos que son insertados y removidos de acuerdo al principio FIFO (First In, First Out: primero en entrar, primero en salir).

Tipos de Colas

• Colas simples
• Colas circulares
• Colas dobles (o bicola)
• Colas con prioridad

Colas Simples

En una cola simple, los elementos se añaden por el final y se eliminan por el frente. Si se implementa con un arreglo de tamaño fijo, puede sufrir de "desperdicio" de espacio a medida que el frente avanza.

Implementación de Cola Simple en Java

public class ColaSimple<T> {
    private T[] cola;
    private int inicio; // Índice del primer elemento
    private int fin;    // Índice del siguiente espacio disponible para insertar
    private int capacidad;

    @SuppressWarnings("unchecked")
    public ColaSimple(int max) {
        this.capacidad = max;
        this.cola = (T[]) new Object[capacidad];
        this.inicio = 0;
        this.fin = 0;
    }

    public void insertarDato(T dato) {
        if (fin == capacidad) { // La cola está llena si fin alcanza la capacidad
            // Podríamos verificar si inicio > 0 para compactar, pero es una cola "simple"
            System.out.println("Desbordamiento (Cola simple llena)");
        } else {
            cola[fin] = dato;
            fin++;
        }
    }

    public T eliminarDato() {
        if (inicio == fin) { // La cola está vacía si inicio alcanza a fin
            System.out.println("Subdesbordamiento (Cola simple vacía)");
            return null;
        } else {
            T dato = cola[inicio];
            cola[inicio] = null; // Facilitar al recolector de basura
            inicio++;
            // Opcional: resetear punteros si la cola se vacía para reutilizar el array desde el principio
            if (inicio == fin) {
                inicio = 0;
                fin = 0;
            }
            return dato;
        }
    }

    public boolean estaVacia() {
        return inicio == fin;
    }

    public boolean estaLlena() {
        return fin == capacidad;
    }
}

Colas Circulares

Una cola circular (o buffer circular) utiliza un arreglo de tamaño fijo de manera más eficiente, tratando los límites del arreglo como si estuvieran conectados (el final con el principio). Esto evita el desperdicio de espacio de las colas simples implementadas con arreglos.

Implementación de Cola Circular en Java

public class ColaCircular<T> {
    private T[] cola;
    private int inicio;         // Índice del primer elemento
    private int fin;            // Índice del último elemento insertado
    private int numElementos;
    private int capacidadTotal;

    @SuppressWarnings("unchecked")
    public ColaCircular(int capacidad) {
        this.capacidadTotal = capacidad;
        this.cola = (T[]) new Object[capacidadTotal];
        this.inicio = 0;
        this.fin = -1; // Indica que la cola está vacía inicialmente
        this.numElementos = 0;
    }

    public void insertar(T dato) {
        if (estaLlena()) {
            System.out.println("Desbordamiento (Cola circular llena)");
        } else {
            fin = (fin + 1) % capacidadTotal;
            cola[fin] = dato;
            numElementos++;
        }
    }

    public T eliminar() {
        if (estaVacia()) {
            System.out.println("Subdesbordamiento (Cola circular vacía)");
            return null;
        } else {
            T dato = cola[inicio];
            cola[inicio] = null; // Facilitar al recolector de basura
            inicio = (inicio + 1) % capacidadTotal;
            numElementos--;
            if (estaVacia()) { // Si se vació, resetear fin para la próxima inserción
                fin = -1; // y inicio ya estaría en 0 (o próximo a serlo si capacidad es 1)
                inicio = 0; // Asegurar consistencia
            }
            return dato;
        }
    }

    public boolean estaVacia() {
        return numElementos == 0;
    }

    public boolean estaLlena() {
        return numElementos == capacidadTotal;
    }

    // Método adicional útil
    public T frente() {
        if (estaVacia()) {
            return null;
        }
        return cola[inicio];
    }
}