Colas en Java (Queue): implementación y ejemplos

/**
 * Interfaz que define el contrato del TAD Cola (Queue).
 * Principio FIFO: First In, First Out.
 *
 * @param <E> Tipo genérico de los elementos de la cola
 */
public interface Cola<E> {

    /**
     * Inserta un elemento al final de la cola.
     * @param elemento El elemento a insertar
     */
    void encolar(E elemento);

    /**
     * Extrae y devuelve el elemento del frente.
     * @return El elemento del frente
     * @throws NoSuchElementException si la cola está vacía
     */
    E desencolar();

    /**
     * Devuelve el elemento del frente sin extraerlo.
     * @return El elemento del frente
     * @throws NoSuchElementException si la cola está vacía
     */
    E frente();

    /** @return true si la cola no tiene elementos */
    boolean estaVacia();

    /** @return El número de elementos en la cola */
    int tamaño();
}

/**
 * Nodo de una estructura enlazada.
 * Almacena un dato y una referencia al siguiente nodo.
 */
class Nodo<E> {
    E dato;
    Nodo<E> siguiente;

    Nodo(E dato) {
        this.dato = dato;
        this.siguiente = null;
    }

    Nodo(E dato, Nodo<E> siguiente) {
        this.dato = dato;
        this.siguiente = siguiente;
    }
}

import java.util.NoSuchElementException;

/**
 * Implementación del TAD Cola mediante nodos enlazados.
 * Todas las operaciones son O(1).
 */
public class ColaEnlazada<E> implements Cola<E> {

    private Nodo<E> cabecera;  // Frente: por aquí se desencola
    private Nodo<E> cola;      // Final: por aquí se encola
    private int tamaño;

    public ColaEnlazada() {
        this.cabecera = null;
        this.cola = null;
        this.tamaño = 0;
    }

    @Override
    public void encolar(E elemento) {
        Nodo<E> nuevoNodo = new Nodo<>(elemento);
        if (estaVacia()) {
            // Si la cola está vacía, cabecera y cola apuntan al mismo nodo
            cabecera = nuevoNodo;
        } else {
            // El nodo actual del final apunta al nuevo nodo
            cola.siguiente = nuevoNodo;
        }
        cola = nuevoNodo;
        tamaño++;
    }

    @Override
    public E desencolar() {
        if (estaVacia()) {
            throw new NoSuchElementException("La cola está vacía");
        }
        E dato = cabecera.dato;
        cabecera = cabecera.siguiente;
        tamaño--;
        if (estaVacia()) {
            // Si la cola queda vacía, limpiar también la referencia cola
            cola = null;
        }
        return dato;
    }

    @Override
    public E frente() {
        if (estaVacia()) {
            throw new NoSuchElementException("La cola está vacía");
        }
        return cabecera.dato;
    }

    @Override
    public boolean estaVacia() {
        return tamaño == 0;
    }

    @Override
    public int tamaño() {
        return tamaño;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Cola [frente -> ");
        Nodo<E> actual = cabecera;
        while (actual != null) {
            sb.append(actual.dato);
            if (actual.siguiente != null) sb.append(" -> ");
            actual = actual.siguiente;
        }
        sb.append(" <- final]");
        return sb.toString();
    }
}

public class PruebaColaEnlazada {
    public static void main(String[] args) {
        Cola<String> cola = new ColaEnlazada<>();

        // Encolar clientes
        cola.encolar("Ana");
        cola.encolar("Pedro");
        cola.encolar("María");
        System.out.println(cola);
        // Cola [frente -> Ana -> Pedro -> María <- final]

        // Consultar quién es el siguiente
        System.out.println("Siguiente: " + cola.frente());
        // Siguiente: Ana

        // Atender al primero
        String atendido = cola.desencolar();
        System.out.println("Atendido: " + atendido);
        // Atendido: Ana

        System.out.println(cola);
        // Cola [frente -> Pedro -> María <- final]

        System.out.println("Tamaño: " + cola.tamaño());
        // Tamaño: 2
    }
}

import java.util.NoSuchElementException;

/**
 * Implementación del TAD Cola con un array circular.
 * Capacidad fija con posibilidad de redimensionamiento.
 */
@SuppressWarnings("unchecked")
public class ColaCircular<E> implements Cola<E> {

    private static final int CAPACIDAD_INICIAL = 16;
    private E[] datos;
    private int frente;     // Índice del primer elemento
    private int numElementos;
    private int capacidad;

    public ColaCircular() {
        this(CAPACIDAD_INICIAL);
    }

    public ColaCircular(int capacidad) {
        this.capacidad = capacidad;
        this.datos = (E[]) new Object[capacidad];
        this.frente = 0;
        this.numElementos = 0;
    }

    @Override
    public void encolar(E elemento) {
        if (numElementos == capacidad) {
            redimensionar(capacidad * 2);
        }
        // El índice del final se calcula a partir de frente + numElementos
        int indiceFinal = (frente + numElementos) % capacidad;
        datos[indiceFinal] = elemento;
        numElementos++;
    }

    @Override
    public E desencolar() {
        if (estaVacia()) {
            throw new NoSuchElementException("La cola está vacía");
        }
        E dato = datos[frente];
        datos[frente] = null;  // Permitir recolección de basura
        frente = (frente + 1) % capacidad;
        numElementos--;
        return dato;
    }

    @Override
    public E frente() {
        if (estaVacia()) {
            throw new NoSuchElementException("La cola está vacía");
        }
        return datos[frente];
    }

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

    @Override
    public int tamaño() {
        return numElementos;
    }

    /**
     * Redimensiona el array circular preservando el orden FIFO.
     */
    private void redimensionar(int nuevaCapacidad) {
        E[] nuevoArray = (E[]) new Object[nuevaCapacidad];
        for (int i = 0; i < numElementos; i++) {
            nuevoArray[i] = datos[(frente + i) % capacidad];
        }
        datos = nuevoArray;
        frente = 0;
        capacidad = nuevaCapacidad;
    }
}

import java.util.*;

public class EjemplosQueue {
    public static void main(String[] args) {

        // 1. LinkedList como Queue (la más versátil)
        Queue<String> colaLinked = new LinkedList<>();
        colaLinked.offer("Primero");
        colaLinked.offer("Segundo");
        colaLinked.offer("Tercero");
        System.out.println("Poll: " + colaLinked.poll());   // Primero
        System.out.println("Peek: " + colaLinked.peek());   // Segundo

        // 2. ArrayDeque como Queue (más eficiente que LinkedList)
        Queue<Integer> colaArray = new ArrayDeque<>();
        colaArray.offer(10);
        colaArray.offer(20);
        colaArray.offer(30);
        System.out.println("Poll: " + colaArray.poll());    // 10

        // 3. PriorityQueue (ordenada por prioridad natural)
        Queue<Integer> colaPrioridad = new PriorityQueue<>();
        colaPrioridad.offer(30);
        colaPrioridad.offer(10);
        colaPrioridad.offer(20);
        System.out.println("Poll: " + colaPrioridad.poll()); // 10 (menor)

        // 4. Recorrer una cola sin destruirla
        System.out.println("Contenido colaLinked:");
        for (String elemento : colaLinked) {
            System.out.println("  " + elemento);
        }
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

public class EjemploDeque {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Insertar por ambos extremos
        deque.offerFirst("B");    // [B]
        deque.offerFirst("A");    // [A, B]
        deque.offerLast("C");     // [A, B, C]
        deque.offerLast("D");     // [A, B, C, D]

        System.out.println(deque); // [A, B, C, D]

        // Extraer por ambos extremos
        System.out.println("Primero: " + deque.pollFirst()); // A
        System.out.println("Último: " + deque.pollLast());   // D
        System.out.println(deque); // [B, C]

        // Usar como pila (LIFO)
        deque.push("X");          // Equivale a offerFirst
        System.out.println("Pop: " + deque.pop()); // X (pollFirst)
    }
}

import java.util.PriorityQueue;
import java.util.Comparator;

public class SistemaUrgencias {

    record Paciente(String nombre, int gravedad) {}

    public static void main(String[] args) {
        // Mayor gravedad = mayor prioridad (orden descendente)
        PriorityQueue<Paciente> urgencias = new PriorityQueue<>(
            Comparator.comparingInt(Paciente::gravedad).reversed()
        );

        urgencias.offer(new Paciente("Ana", 3));      // Leve
        urgencias.offer(new Paciente("Pedro", 9));     // Crítico
        urgencias.offer(new Paciente("María", 5));     // Moderado
        urgencias.offer(new Paciente("Juan", 10));     // Emergencia

        System.out.println("Orden de atención:");
        while (!urgencias.isEmpty()) {
            Paciente p = urgencias.poll();
            System.out.printf("  %s (gravedad: %d)%n", p.nombre(), p.gravedad());
        }
        // Juan (10), Pedro (9), María (5), Ana (3)
    }
}

import java.util.*;

/**
 * Sistema de gestión de turnos con doble cola:
 * - Cola de prioridad para clientes VIP (ordenados por antigüedad VIP)
 * - Cola estándar FIFO para clientes normales
 * Los clientes VIP siempre se atienden antes que los normales.
 */
public class SistemaAtencionCliente {

    record Cliente(String nombre, boolean esVip, int antiguedadVip) {}

    private final Queue<Cliente> colaNormal;
    private final PriorityQueue<Cliente> colaVip;
    private int turnoActual;

    public SistemaAtencionCliente() {
        this.colaNormal = new ArrayDeque<>();
        // Mayor antigüedad = mayor prioridad
        this.colaVip = new PriorityQueue<>(
            Comparator.comparingInt(Cliente::antiguedadVip).reversed()
        );
        this.turnoActual = 0;
    }

    public void llegarCliente(String nombre, boolean esVip, int antiguedad) {
        turnoActual++;
        Cliente cliente = new Cliente(nombre, esVip, antiguedad);
        if (esVip) {
            colaVip.offer(cliente);
            System.out.printf("[Turno %d] Cliente VIP '%s' (antigüedad: %d años)%n",
                turnoActual, nombre, antiguedad);
        } else {
            colaNormal.offer(cliente);
            System.out.printf("[Turno %d] Cliente '%s'%n", turnoActual, nombre);
        }
    }

    public Cliente atenderSiguiente() {
        // Prioridad: primero VIP, luego normales
        Cliente siguiente;
        if (!colaVip.isEmpty()) {
            siguiente = colaVip.poll();
        } else if (!colaNormal.isEmpty()) {
            siguiente = colaNormal.poll();
        } else {
            System.out.println("No hay clientes en espera.");
            return null;
        }
        String tipo = siguiente.esVip() ? "VIP" : "Normal";
        System.out.printf(">> Atendiendo a %s [%s]%n", siguiente.nombre(), tipo);
        return siguiente;
    }

    public int clientesEnEspera() {
        return colaNormal.size() + colaVip.size();
    }

    public static void main(String[] args) {
        SistemaAtencionCliente sistema = new SistemaAtencionCliente();

        // Llegan clientes en distintos momentos
        sistema.llegarCliente("Laura", false, 0);
        sistema.llegarCliente("Miguel", false, 0);
        sistema.llegarCliente("Elena", true, 5);      // VIP 5 años
        sistema.llegarCliente("Carlos", false, 0);
        sistema.llegarCliente("Sofía", true, 12);      // VIP 12 años

        System.out.println("\nClientes en espera: " + sistema.clientesEnEspera());
        System.out.println("\n--- Orden de atención ---");

        while (sistema.clientesEnEspera() > 0) {
            sistema.atenderSiguiente();
        }
        // Sofía VIP (12 años), Elena VIP (5 años),
        // Laura, Miguel, Carlos (orden FIFO)
    }
}