Skip to content

Queue y Deque: El Arte de Organizar Datos (Sin Hilos)

Introducción: ¿Fila india o Baraja de cartas?

¡Hola de nuevo, equipo de desarrollo! 👨‍💻👩‍💻

Ya dominamos la LinkedList como estructura, pero hoy vamos a centrarnos en el comportamiento. Imaginad que estáis programando la lógica de una caja de supermercado. No puedes atender al último cliente primero (se armaría un escándalo). Necesitas un orden estricto: el primero que llega, es el primero que sale. Eso es una Queue (Cola).

Ahora imaginad que estáis programando el botón "Deshacer" de un editor de texto o jugando a las cartas. Lo último que hiciste es lo primero que quieres borrar. O quizá quieres hacer trampas y sacar una carta de abajo del mazo. Necesitas flexibilidad por ambos extremos. Eso es una Deque (Double Ended Queue).

Hoy vamos a ver estas interfaces puras, sin meternos en líos de concurrencia ni multihilo. Solo tú, tus datos y el orden perfecto.

Conceptos Fundamentales

Definición: Queue (Cola)

Es una interfaz que define una colección lineal ordenada. Ordena los elementos en formato FIFO (Primero en entrar, primero en salir). * Head (Cabeza): El elemento que lleva más tiempo esperando. El siguiente en salir. * Tail (Cola): Donde se añaden los nuevos elementos. * Uso típico: Cola de impresión, lista de reproducción de canciones, gestión de pedidos.

Definición: Implementaciones Comunes

Como Queue es un contrato (interface), solemos instanciarla usando: * LinkedList: La opción estándar para colas de propósito general. * PriorityQueue: Una cola "tramposa" donde salen primero los más importantes (según un criterio de orden), no los que llegaron antes. * ArrayDeque: Más rápida y moderna que LinkedList, pero no admite nulos.

Definición: Deque (Double Ended Queue)

Es una interfaz que extiende de Queue pero permite insertar, eliminar y consultar elementos por ambos extremos (cabeza y cola). * Uso típico: Pilas (Stacks - LIFO), historial de navegación, palíndromos.

Implementaciones Clave

Las dos clases principales que usaréis son: 1. LinkedList: Implementa tanto Queue como Deque. 2. ArrayDeque: Implementa Deque. Es más rápida y eficiente en memoria que LinkedList, pero no permite nulos.


Mapa Mental: Estructura de Interfaces


Desarrollo y Ejemplos Prácticos

Vamos a desglosar TODOS los métodos solicitados. Para que sea fácil de estudiar, los dividiremos en tres categorías: Insertar, Eliminar y Consultar, diferenciando siempre entre los métodos "Dramáticos" (Lanzan Excepción) y los "Tranquilos" (Devuelven valores especiales).

1. Métodos de Queue (Cola Simple)

Usaremos una LinkedList actuando como Queue para simular una Cola de Impresión.

1. Inserción: ¡Al final de la fila!

Aquí añadimos elementos a la cola (Tail).

  • add(E e): Intenta añadir. Si no puede (ej. cola con límite de capacidad), lanza una excepción IllegalStateException.
  • offer(E e): Intenta añadir. Si no puede, simplemente devuelve false. Es el método recomendado para colas con capacidad restringida.
import java.util.LinkedList;
import java.util.Queue;

public class GestionCola {
    public static void main(String[] args) {
        // Instanciamos una LinkedList pero la tratamos como Queue.
        // Polimorfismo: Solo vemos los métodos de la interfaz Queue.
        Queue<String> colaSupermercado = new LinkedList<>();

        // --- MÉTODOS DE INSERCIÓN ---

        // 1. add(E e) - El método "Exigente"
        // Añade "Cliente A" al final.
        // Si la cola tuviera un límite fijo y estuviera llena, lanzaría Exception.
        colaSupermercado.add("Cliente A (La señora de las monedas)");
        System.out.println("Añadido con add: Cliente A");

        // 2. offer(E e) - El método "Educado"
        // Intenta añadir "Cliente B". Devuelve true si lo logra.
        // Si la cola estuviera llena, devolvería false (sin errores rojos).
        boolean aceptado = colaSupermercado.offer("Cliente B (El chico de la prisa)");

        if (aceptado) {
            System.out.println("Añadido con offer: Cliente B");
        } else {
            System.out.println("Cola llena, vuelva más tarde.");
        }

        System.out.println("Estado actual: " + colaSupermercado);
        // Salida: [Cliente A..., Cliente B...]
    }
}

2. Eliminación: ¡El siguiente!

Aquí sacamos al elemento que está en la cabeza (Head) para procesarlo.

  • remove(): Saca y devuelve la cabeza. Si la cola está vacía, ¡CRASH! (NoSuchElementException).
  • poll(): Saca y devuelve la cabeza. Si la cola está vacía, devuelve null.
        // ... (continuación del código anterior)

        // --- MÉTODOS DE ELIMINACIÓN ---

        // 3. remove() - El método "Arriesgado"
        // Atendemos al primero (Cliente A).
        // ¡CUIDADO! Si ejecutamos esto en una cola vacía, el programa se detiene con error.
        String atendido1 = colaSupermercado.remove(); 
        System.out.println("Atendiendo a (remove): " + atendido1);

        // 4. poll() - El método "Seguro"
        // Atendemos al siguiente (Cliente B).
        // Es ideal para bucles while, porque cuando se vacía, devuelve null y paramos.
        String atendido2 = colaSupermercado.poll();
        System.out.println("Atendiendo a (poll): " + atendido2);

        // Intento sacar a alguien más, pero la cola está vacía...
        String fantasma = colaSupermercado.poll(); 
        System.out.println("¿Queda alguien? (poll): " + fantasma); // Imprime: null

        // Si descomentamos la siguiente línea, el programa fallaría:
        // colaSupermercado.remove(); // Lanza NoSuchElementException

3. Inspección: ¿Quién va ahora?

A veces solo queremos ver quién es el siguiente sin sacarlo de la fila (quizás para preparar su pedido).

  • element(): Recupera la cabeza pero NO la elimina. Si está vacía, lanza Excepción.
  • peek(): Recupera la cabeza pero NO la elimina. Si está vacía, devuelve null.
import java.util.LinkedList;
import java.util.Queue;

public class MirandoLaCola {
    public static void main(String[] args) {
        Queue<String> impresora = new LinkedList<>();
        impresora.offer("Tesis_Final.pdf");
        impresora.offer("Meme_Gato.jpg");

        // --- MÉTODOS DE INSPECCIÓN ---

        // 5. element() - Mirada "Agresiva"
        // Mira quién es el primero. Si no hay nadie, lanza excepción.
        // Útil cuando tu lógica asegura que SIEMPRE debe haber algo.
        System.out.println("Siguiente documento (element): " + impresora.element());

        // 6. peek() - Mirada "Discreta"
        // Mira quién es el primero. Si está vacía, devuelve null.
        // Es la forma más segura de comprobar antes de procesar.
        System.out.println("Siguiente documento (peek): " + impresora.peek());

        // Demostración de que NO se han borrado:
        System.out.println("Tamaño sigue siendo: " + impresora.size()); // 2
    }
}

4. Operaciones Generales de Colección

Como Queue hereda de Collection, tenemos herramientas estándar para gestión masiva.

  • size(): Cuenta elementos.
  • isEmpty(): Verifica si está vacía.
  • contains(Object o): Busca un elemento (usa equals()).
  • iterator(): Nos da un objeto para recorrer la cola uno a uno.
  • toArray(): Convierte la cola en un Array clásico.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Iterator;
import java.util.Arrays;

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

        // 7. size() - Tamaño
        System.out.println("Hay " + numeros.size() + " números en cola.");

        // 8. isEmpty() - Verificación
        if (!numeros.isEmpty()) {
            System.out.println("La cola tiene datos.");
        }

        // 9. contains(Object o) - Búsqueda
        // Ojo: Esto puede ser lento (O(n)) en LinkedList porque recorre todo.
        boolean tieneVeinte = numeros.contains(20);
        System.out.println("¿Está el 20 esperando? " + tieneVeinte);

        // 10. iterator() - Recorrido manual
        System.out.print("Iterando la cola: ");
        Iterator<Integer> it = numeros.iterator();
        while(it.hasNext()) {
            // next() nos da el elemento y avanza el cursor
            System.out.print("[" + it.next() + "] ");
        }
        System.out.println();

        // 11. toArray() - Conversión
        // A veces necesitamos pasar los datos a una API antigua que pide arrays.
        Object[] array = numeros.toArray();
        System.out.println("Convertido a Array: " + Arrays.toString(array));

        // Limpiamos todo
        numeros.clear();
        System.out.println("Después de clear(), tamaño: " + numeros.size());
    }
}

Inline Tip: Iteración

Aunque podemos usar un bucle for-each (for (Integer n : numeros)), internamente Java usa el método iterator() que acabamos de ver. Es azúcar sintáctico. 🍬


Diagrama de Flujo: ¿Qué método elijo?

Es fácil liarse entre poll, remove, peek... Este diagrama es vuestra brújula.

graph TD
    Start((Inicio)) --> Action["¿Qué quieres hacer?"]

    Action -- Meter Dato --> Insert[Inserción]
    Action -- Sacar Dato --> Remove[Eliminación]
    Action -- Solo Mirar --> Inspect[Inspección]

    Insert --> I_Q["¿Es crítico si falla?"]
    I_Q -- "Sí, quiero Excepción" --> I_Ex["add"]
    I_Q -- "No, avísame con false" --> I_Safe["offer"]

    Remove --> R_Q["¿La cola podría estar vacía?"]
    R_Q -- "No, seguro hay datos" --> R_Ex["remove"]
    R_Q -- "Quizás, quiero evitar error" --> R_Safe["poll"]

    Inspect --> In_Q["¿La cola podría estar vacía?"]
    In_Q -- "No, seguro hay datos" --> In_Ex["element"]
    In_Q -- "Quizás, devuelve null" --> In_Safe["peek"]


2. Métodos de Deque (Doble Extremo)

Definición: Deque

Viene de "Double Ended Queue" (Cola de doble extremo). Es una interfaz que extiende de Queue. A diferencia de una cola normal (que es solo FIFO), una Deque permite insertar, inspeccionar y eliminar elementos tanto por el principio (Head) como por el final (Tail).

Definición: ArrayDeque

Es la implementación de Deque basada en un array redimensionable (como ArrayList, pero circular internamente). * Ventaja clave: Es más rápida que Stack y que LinkedList para operaciones de cola/pila. * Restricción importante: NO admite elementos null.

Mapa Mental: El Ecosistema Deque

Aquí usamos ArrayDeque (más eficiente). Imaginad una Baraja de Cartas.

A. Inserción en Extremos (Insert First/Last)

Dramático (Excepción) Seguro (Return false/null) Ubicación
addFirst(e) offerFirst(e) Principio (Arriba)
addLast(e) offerLast(e) Final (Abajo) 
import java.util.ArrayDeque;
import java.util.Deque;

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

        // Inserción al PRINCIPIO (Arriba del mazo)
        baraja.addFirst("As de Corazones"); // void / Excepción si falla
        boolean ok1 = baraja.offerFirst("Rey de Picas"); // boolean

        // Inserción al FINAL (Abajo del mazo)
        baraja.addLast("2 de Tréboles"); // void / Excepción si falla
        boolean ok2 = baraja.offerLast("Joker"); // boolean

        System.out.println(baraja);
        // Orden: [Rey de Picas, As de Corazones, 2 de Tréboles, Joker]
    }
}

B. Eliminación en Extremos (Remove First/Last)

Dramático (Excepción) Seguro (Return null) Ubicación
removeFirst() pollFirst() Principio
removeLast() pollLast() Final 
import java.util.ArrayDeque;
import java.util.Deque;

public class EjemploRemovalDeque {
    public static void main(String[] args) {
        Deque<String> baraja = new ArrayDeque<>();
        baraja.add("Carta 1");
        baraja.add("Carta 2");

        // Sacar de ARRIBA (First)
        String c1 = baraja.removeFirst(); // Lanza Excepción si vacía
        String c2 = baraja.pollFirst();   // Devuelve null si vacía

        // Sacar de ABAJO (Last) - Intentamos sacar de lista vacía
        // String error = baraja.removeLast(); // ¡CRASH! NoSuchElementException
        String seguro = baraja.pollLast();    // null, todo bien.

        System.out.println("Seguro: " + seguro);
    }
}

C. Inspección en Extremos (Get/Peek First/Last)

Dramático (Excepción) Seguro (Return null) Ubicación
getFirst() peekFirst() Principio
getLast() peekLast() Final 
import java.util.ArrayDeque;
import java.util.Deque;

public class EjemploInspectionDeque {
    public static void main(String[] args) {
        Deque<String> historial = new ArrayDeque<>();
        historial.add("Google.com");
        historial.add("Youtube.com");

        // Mirar el primero (First - Google)
        System.out.println("First (Dramático): " + historial.getFirst());
        System.out.println("First (Seguro): " + historial.peekFirst());

        // Mirar el último (Last - Youtube)
        System.out.println("Last (Dramático): " + historial.getLast());
        System.out.println("Last (Seguro): " + historial.peekLast());

        // No modifican la lista, solo miran.
        System.out.println("Tamaño sigue siendo: " + historial.size());
    }
}

1. Inserción (Insertion): Llenando la baraja

Aquí metemos datos. Podemos hacerlo como una cola normal o especificando el extremo.

Métodos:
* add(E e) / addLast(E e): Añade al final. Excepción si falla.
* offer(E e) / offerLast(E e): Añade al final. false si falla.
* addFirst(E e): Añade al principio. Excepción si falla.
* offerFirst(E e): Añade al principio. false si falla.

Ejemplo 1: Gestión de Tareas (Priority Tasks)

Imaginad un sistema donde entran tareas normales (al final) y tareas urgentes (al principio).

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

public class TaskManager {
  public static void main(String[] args) {
    // Creamos un ArrayDeque. No necesitamos definir tamaño inicial.
    Deque<String> tareas = new ArrayDeque<>();

    // --- Inserción Estándar (Al final) ---
    // add(E e): Lanza excepción si no hay espacio (raro en ArrayDeque)
    tareas.add("Revisar correos"); 

    // offer(E e): Devuelve true/false. Más seguro.
    boolean aceptada = tareas.offer("Actualizar Java"); 

    // addLast y offerLast hacen EXACTAMENTE lo mismo que add y offer
    tareas.addLast("Limpiar escritorio");
    tareas.offerLast("Ir a por café");

    // --- Inserción Prioritaria (Al principio) ---
    // ¡Jefe entra en la oficina! Tarea urgente al principio (Head)
    tareas.addFirst("URGENTE: Servidor caído");

    // offerFirst devuelve false si fallara (ej. deque con capacidad limitada)
    tareas.offerFirst("SUPER URGENTE: Fuego en la sala de servidores");

    System.out.println("Lista de tareas: " + tareas);
    // Salida esperada: 
    // [SUPER URGENTE..., URGENTE..., Revisar..., Actualizar..., Limpiar..., Ir a por café]
  }
}

2. Eliminación (Removal): Repartiendo cartas

Sacamos elementos. Si es una Cola (FIFO), sacamos del principio. Si es Pila (LIFO), también del principio (pero habríamos insertado al principio).

Métodos:
* remove() / removeFirst(): Saca del principio. Excepción si vacía.
* poll() / pollFirst(): Saca del principio. null si vacía.
* removeLast(): Saca del final. Excepción si vacía.
* pollLast(): Saca del final. null si vacía.

Ejemplo 2: El Historial de Navegación (Undo/Redo)

Vamos a simular un botón de "Deshacer" (sacar lo último que entró).

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

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

    // Llenamos el historial
    historial.push("google.com");   // push() es alias de addFirst()
    historial.push("youtube.com");
    historial.push("stackoverflow.com");

    // Estructura actual: [stackoverflow, youtube, google] -> Principio a la izq

    // --- Eliminación Dramática (Exceptions) ---
    try {
      // remove() y removeFirst() son lo mismo: sacan la cabeza
      String paginaActual = historial.removeFirst(); 
      System.out.println("Saliendo de: " + paginaActual); // stackoverflow.com
    } catch (NoSuchElementException e) {
      System.out.println("Historial vacío.");
    }

    // --- Eliminación Prudente (Null safe) ---
    // poll() y pollFirst() son lo mismo.
    String anterior = historial.pollFirst(); 
    System.out.println("Volviendo a: " + anterior); // youtube.com

    // --- Operación desde el final (Tail) ---
    // Imaginad que el historial tiene un límite y borramos lo más antiguo
    String masVieja = historial.pollLast(); // Saca del final
    System.out.println("Olvidando la página más vieja: " + masVieja); // google.com

    // Ahora está vacía. Veamos qué pasa.
    System.out.println("¿Queda algo? " + historial.poll()); // null
    // System.out.println(historial.remove()); // ¡ESTO EXPLOTA!
  }
}


3. Inspección (Inspection): Solo mirando

Queremos ver qué hay sin tocar nada.

Métodos:
* element() / getFirst(): Mira el principio. Excepción si vacía.
* peek() / peekFirst(): Mira el principio. null si vacía.
* getLast(): Mira el final. Excepción si vacía.
* peekLast(): Mira el final. null si vacía.

Ejemplo 3: El Portero de Discoteca

Comprobamos quién es el primero y el último de la fila.

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

public class ClubQueue {
  public static void main(String[] args) {
    Deque<String> filaVip = new ArrayDeque<>();
    filaVip.add("Celebridad A");
    filaVip.add("Celebridad B");
    filaVip.add("Yo (Colado)");

    // --- Mirar al Principio ---
    // peek() y peekFirst() devuelven null si no hay nadie, no arriesgan.
    System.out.println("Siguiente en entrar: " + filaVip.peek()); 
    // element() y getFirst() lanzan error si está vacía.
    System.out.println("Siguiente (Confirmado): " + filaVip.getFirst());

    // --- Mirar al Final ---
    // ¿Quién es el último pringado de la fila?
    System.out.println("Último de la fila: " + filaVip.peekLast());

    // Limpiamos la sala
    filaVip.clear();

    // Prueba de fuego
    if (filaVip.peekFirst() == null) {
      System.out.println("La fila está vacía (Comprobado con peek).");
    }

    // filaVip.getLast(); // ¡ESTO LANZARÍA EXCEPCIÓN NoSuchElementException!
  }
}

4. Gestión General y Conversión

Métodos comunes de la interfaz Collection.

Métodos:
* size(): Entero con el número de elementos.
* isEmpty(): Booleano (true si size es 0).
* contains(Object o): Booleano. Busca con .equals().
* iterator(): Devuelve un iterador estándar.
* toArray(): Devuelve un Object[] con los datos.

Ejemplo 4: Añadiendo números

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Arrays;

public class CollectionMethods {
  public static void main(String[] args) {
    Deque<Integer> numeros = new ArrayDeque<>();
    numeros.add(10);
    numeros.add(20);
    numeros.add(30);

    // 1. Información Básica
    System.out.println("Tamaño: " + numeros.size()); // 3
    System.out.println("¿Está vacía? " + numeros.isEmpty()); // false
    System.out.println("¿Contiene el 20? " + numeros.contains(20)); // true

    // 2. Convertir a Array
    Object[] arraySimple = numeros.toArray();
    System.out.println("Array: " + Arrays.toString(arraySimple));

    // 3. Iterador
    System.out.print("Recorriendo: ");
    Iterator<Integer> it = numeros.iterator();
    while (it.hasNext()) {
      Integer n = it.next();
      System.out.print(n + " - ");
    }
    // Salida: 10 - 20 - 30 -
  }
}


Diagrama Mermaid: Resumen Visual de Métodos

Para no liarnos con tantos nombres parecidos, este diagrama os salvará la vida en el examen.

graph TD
    subgraph "Queue & Deque Operations"
    direction LR

    A[Operación] --> B{¿Qué pasa si falla/está vacía?}

    B -- "Lanza Excepción 💥" --> C[Grupo ADD / REMOVE / GET-ELEMENT]
    B -- "Devuelve null/false 🛡️" --> D[Grupo OFFER / POLL / PEEK]

    C --> C1[add / addFirst / addLast]
    C --> C2[remove / removeFirst / removeLast]
    C --> C3[element / getFirst / getLast]

    D --> D1[offer / offerFirst / offerLast]
    D --> D2[poll / pollFirst / pollLast]
    D --> D3[peek / peekFirst / peekLast]
    end

Tabla Comparativa: ¿Cuál usar?

No se trata solo de gustos, sino de robustez en el código.

Escenario Método recomendado Razón
Inicialización garantizada add, remove, getFirst Si sabes seguro que hay datos, la excepción te avisa de un bug lógico.
Flujo incierto offer, poll, peek Si es normal que la cola esté llena o vacía y quieres controlarlo con un if.
Pilas (Stacks) push (equivale a addFirst), pop (removeFirst) Nombres más semánticos para estructuras LIFO.
Colas (Queues) offer, poll Estándar de la industria para procesamiento FIFO.

Consejo Pro: LinkedList vs ArrayDeque

  • Usa ArrayDeque por defecto. Es más rápida y consume menos memoria porque usa un array redimensionable internamente en vez de crear nodos dispersos.
  • Usa LinkedList SOLO si necesitas implementar una List a la vez (acceso por índice get(i)) o si necesitas insertar elementos null (ArrayDeque prohíbe los nulos).


Aplicación en el Mundo Real

  1. Algoritmo de Búsqueda en Anchura (BFS): Cuando un GPS busca una ruta o un algoritmo busca amigos en común en una red social, utiliza una Queue.

    • Empieza por TI. Añade tus amigos a la cola.
    • Saca al primero (poll), comprueba si es el destino.
    • Si no, añade los amigos de ese amigo a la cola (offer).
    • Al ser FIFO, explora por "círculos" o niveles de cercanía.

  2. Palíndromos y Análisis de Texto: Para comprobar si una palabra es un palíndromo ("DABALE ARROZ A LA ZORRA EL ABAD"), puedes cargar los caracteres en un Deque.

    • Comparas pollFirst() (primera letra) con pollLast() (última letra).
    • Si son iguales, sigues. Si llegas al centro, es palíndromo.

  3. Gestor de Impresión (Spooler): Es el ejemplo clásico. Varios usuarios envían documentos. Se almacenan en una Queue. El servicio de impresión hace un bucle infinito while(!queue.isEmpty()) haciendo poll() para imprimir uno a uno en orden de llegada.

Para Saber Más