La Pila (Stack)

Una pila es una estructura de datos lineal que sigue el principio LIFO (Last In, First Out), lo que significa que el último elemento en entrar es el primero en salir. Las operaciones se restringen a un único extremo llamado "cima" o "tope".

Operaciones fundamentales

• Push: Agrega un elemento a la cima de la pila.
• Pop: Retira el elemento situado en la cima.

Desde el punto de vista del rendimiento, las pilas son extremadamente eficientes, ya que sus operaciones básicas se ejecutan en tiempo constante O(1). A continuación, se presentan dos formas comunes de implementación.

1. Implementación basada en Listas Enlazadas

Esta aproximación utiliza nodos dinámicos, lo que permite que la pila crezca según sea necesario sin reservar memoria estática de antemano.

public class PilaEnlazada<T> {
    private class Nodo {
        T elemento;
        Nodo siguiente;

        Nodo(T elemento, Nodo siguiente) {
            this.elemento = elemento;
            this.siguiente = siguiente;
        }
    }

    private Nodo tope = null;
    private int contador = 0;

    public void push(T item) {
        tope = new Nodo(item, tope);
        contador++;
    }

    public T pop() {
        if (estaVacia()) throw new RuntimeException("Stack Underflow");
        T valor = tope.elemento;
        tope = tope.siguiente;
        contador--;
        return valor;
    }

    public boolean estaVacia() {
        return tope == null;
    }

    public int size() {
        return contador;
    }
}

2. Implementación basada en Arreglos

El uso de arreglos suele ser más rápido en términos de acceso a memoria, aunque requiere gestionar el redimensionamiento cuando la capacidad se agota.

public class PilaArray<T> {
    private T[] almacenamiento;
    private int puntero = 0;

    @SuppressWarnings("unchecked")
    public PilaArray(int capacidadInicial) {
        almacenamiento = (T[]) new Object[capacidadInicial];
    }

    public void push(T item) {
        if (puntero == almacenamiento.length) {
            escalar(almacenamiento.length * 2);
        }
        almacenamiento[puntero++] = item;
    }

    public T pop() {
        if (estaVacia()) return null;
        T item = almacenamiento[--puntero];
        almacenamiento[puntero] = null; // Evitar fugas de memoria
        return item;
    }

    private void escalar(int nuevaCapacidad) {
        @SuppressWarnings("unchecked")
        T[] nuevoArray = (T[]) new Object[nuevaCapacidad];
        System.arraycopy(almacenamiento, 0, nuevoArray, 0, puntero);
        almacenamiento = nuevoArray;
    }

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

Aplicaciones Prácticas

• Verificación de balanceo de paréntesis: Los compiladores utilizan pilas para asegurar que cada símbolo de aperutra (como {, \[, () tenga su correspondiente cierre en el orden correcto.
• Evaluación de expresiones: Transformación y cálculo de expresiones en notación postfija (Notación Polaca Inversa).

La Cola (Queue)

Una cola es una estructura de datos que opera bajo el principio FIFO (First In, First Out). El primer elemento que se inserta es el primero en ser procesado. Las inserciones ocurren en la parte psoterior (rear) y las extracciones en la parte frontal (front).

Variantes de Colas

• Cola Enlazada: Utiliza nodos y no tiene un límite de tamaño predefinido.
• Cola de Arreglo Simple: Puede sufrir de "fragmentación" si no se desplazan los elementos tras un borrado.
• Cola Circular: Optimiza el espacio reutilizando los índices vacíos al inicio del arreglo mediante aritmética modular.

1. Implemantación de Cola Enlazada

public class ColaEnlazada<T> {
    private class Nodo {
        T dato;
        Nodo sig;
        Nodo(T dato) { this.dato = dato; }
    }

    private Nodo frente, finalCola;
    private int total = 0;

    public void enqueue(T item) {
        Nodo nuevo = new Nodo(item);
        if (estaVacia()) {
            frente = nuevo;
        } else {
            finalCola.sig = nuevo;
        }
        finalCola = nuevo;
        total++;
    }

    public T dequeue() {
        if (estaVacia()) return null;
        T valor = frente.dato;
        frente = frente.sig;
        if (frente == null) finalCola = null;
        total--;
        return valor;
    }

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

2. Implementación de Cola Circular

La cola circular es la forma más eficiente de implementar este concepto sobre un arreglo fijo, evitando el desplazamiento constante de elementos.

public class ColaCircular {
    private int[] datos;
    private int inicio = 0;
    private int fin = 0;
    private int n;

    public ColaCircular(int capacidad) {
        datos = new int[capacidad];
        n = capacidad;
    }

    public boolean insertar(int valor) {
        if ((fin + 1) % n == inicio) return false; // Cola llena
        datos[fin] = valor;
        fin = (fin + 1) % n;
        return true;
    }

    public Integer extraer() {
        if (inicio == fin) return null; // Cola vacía
        int valor = datos[inicio];
        inicio = (inicio + 1) % n;
        return valor;
    }
}

Tanto las pilas como las colas son abstracciones fundamentales que permiten organizar el flujo de datos de manera predecible. Mientras que la pila es ideal para procesos recursivos y retrocesos (backtracking), la cola es indispensable para la gestión de recursos compartidos, como la planificación de procesos en sistemas operativos o la gestión de buffers de red.