🔁 Invertir una Cola en Java

Profe Danna L. Cruz Reyes

🎯 Objetivo

Aprender a invertir una cola (Queue) usando solo los métodos:

• add()

• remove()

• isEmpty()

🧩 Enunciado del problema

El entrevistador te da una cola con los elementos:

[10, 20, 30]

donde 10 es el frente de la cola.

🎯 Queremos invertirla para obtener:

[30, 20, 10]

💡 Restricciones

Solo puedes usar:

• add() para agregar elementos.

• remove() para sacar elementos.

• isEmpty() para verificar si la cola está vacía.

🚫 Nada de acceder por índice ni usar peek(), size(), etc.

🧠 Pista conceptual

Piensa en cómo se invierte una cadena de texto:

1. Tomas el primer carácter.

2. Inviertes el resto.

3. Lo colocas al final.

💫 Exactamente esa lógica aplicaremos aquí con recursión.

🧱 Estructura base

import java.util.*;

public class ReverseQueue {

    public static void reverse(Queue<Integer> queue) {
        if (queue.isEmpty())
            return;

        int front = queue.remove();
        reverse(queue);
        queue.add(front);
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);

        System.out.println("Cola original: " + queue);
        reverse(queue);
        System.out.println("Cola invertida: " + queue);
    }
}

🚀 Salida esperada

Cola original: [10, 20, 30]
Cola invertida: [30, 20, 10]

⚙️ Paso a paso visual

Paso	Acción	Cola actual
1️⃣	remove(10) → llamada recursiva	[20, 30]
2️⃣	remove(20) → llamada recursiva	[30]
3️⃣	remove(30) → llamada recursiva	[]
4️⃣	cola vacía → retorno	[]
5️⃣	add(30)	[30]
6️⃣	add(20)	[30, 20]
7️⃣	add(10)	[30, 20, 10]

Recursión en acción

public static void reverse(Queue<Integer> queue) {
    if (queue.isEmpty())
        return;

    // 1️⃣ Sacar el frente
    int front = queue.remove();

    // 2️⃣ Llamada recursiva: invierte el resto
    reverse(queue);

    // 3️⃣ Volver a agregar al final
    queue.add(front);
}

💬 Cada llamada queda “en pausa” hasta que la cola esté vacía, y luego se van apilando las inserciones en orden inverso 🌀

🪄 Analogía con invertir una cadena

"ABC"

→ remove('A')
→ reverse("BC")
     → remove('B')
     → reverse("C")
         → remove('C')
         → reverse("")
         → add('C')
     → add('B')
→ add('A')

📦 Resultado: "CBA"

📦 Igual ocurre con [10, 20, 30] → [30, 20, 10]

💡 Alternativa (con pila auxiliar)

Si el entrevistador no limita las operaciones:

public static void reverse(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<>();

    while (!queue.isEmpty())
        stack.push(queue.remove());

    while (!stack.isEmpty())
        queue.add(stack.pop());
}

🔁 Misma lógica, pero usando una estructura auxiliar explícita (Stack).

⚖️ Diferencia entre FIFO y LIFO

Estructura	Significado	Orden de procesamiento	Ejemplo cotidiano
🧺 Queue	First In, First Out	El primero en entrar es el primero en salir.	Fila del banco 🏦
📚 Stack	Last In, First Out	El último en entrar es el primero en salir.	Pila de platos 🍽️

Conceptos reforzados

✅ Recursión como estructura auxiliar implícita (pila de llamadas)

✅ Diferencia entre FIFO (Queue) y LIFO (Stack)

✅ Pensamiento algorítmico sin índices ni accesos directos

🎬 Resumen visual final

🧱 remove(10)
    🧱 remove(20)
        🧱 remove(30)
            ⚪ cola vacía
        🔁 add(30)
    🔁 add(20)
🔁 add(10)

✅ Resultado: [30, 20, 10]

👩‍💻 Código completo (para ejecutar)

import java.util.*;

public class ReverseQueue {

    public static void reverse(Queue<Integer> queue) {
        if (queue.isEmpty())
            return;
        int front = queue.remove();
        reverse(queue);
        queue.add(front);
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Cola original: " + queue);
        reverse(queue);
        System.out.println("Cola invertida: " + queue);
    }
}

🌈 Resultado final

Acción	Resultado
Original	[10, 20, 30]
Invertida	[30, 20, 10]

✨ ¡Y así se invierte una cola con estilo, lógica y recursión! 💫