🧮 Implementación de una Cola con Arreglos (Array Queue)

Profe Danna L. Cruz Reyes

🎯 Objetivo

Aprender a implementar una cola (Queue) desde cero usando un arreglo (array), sin usar colecciones predefinidas de Java.

🧩 Concepto general

Una cola (Queue) es una estructura de datos FIFO:
➡️ First In, First Out
El primero en entrar es el primero en salir 🧺

🪄 ¿Qué es @Override en Java?

@Override es una anotación que le dice al compilador:

“Este método ya existe en la clase padre,

y quiero redefinirlo aquí con mi propia versión.”

🧠 Ejemplo simple

class Animal {
    public void makeSound() {
        System.out.println("Sonido genérico 🐾");
    }
}

class Dog extends Animal {
    @Override
    public void makeSound() {
        System.out.println("Guau guau 🐶");
    }
}

🐶 La clase Dog hereda el método makeSound() de Animal, pero lo redefine para adaptarlo a su propio comportamiento.

🧩 ¿Qué pasaría sin @Override?

class Dog extends Animal {
    // ¡Ups! error de escritura
    public void makeSoud() { 
        System.out.println("Guau guau 🐶");
    }
}

🚨 El compilador no detectaría que el método está mal escrito y simplemente crearía uno nuevo.

🧡 Con @Override, recibirías un error que te advierte:

“Method does not override or implement a method from a supertype”

🎨 Diagrama visual

classDiagram
    class Animal {
        +makeSound() : void
    }
    class Dog {
        +makeSound() : void
    }
    Animal <|-- Dog

📚 Dog extiende Animal y sobrescribe (override) el método makeSound() heredado.

💻 Otro ejemplo: el método toString()

Por defecto, todos los objetos en Java tienen este método:

System.out.println(objeto);
// 🔹 Muestra algo como: ArrayQueue@6d06d69c

Pero podemos redefinirlo con @Override para mostrar algo más útil:

💻 Otro ejemplo: el método toString()

@Override
public String toString() {
    return Arrays.toString(items);
}

💬 Así, cuando imprimimos la cola, vemos su contenido real:

[10, 20, 30, 0, 0]

💡 En resumen

Aspecto	Descripción
💬 Qué es	Anotación para sobrescribir métodos heredados
🧱 Dónde se usa	En clases hijas que redefinen métodos (toString, equals, hashCode, etc.)
🔍 Para qué sirve	Le dice al compilador que el método ya existe y debe verificarse
⚙️ Beneficio	Evita errores, mejora la legibilidad y documenta la intención

⚙️ Tres formas de implementar una cola

1️⃣ Usando un Array

2️⃣ Usando una Lista Enlazada

3️⃣ Usando Dos Pilas (Stacks)

En este ejercicio implementaremos la primera: Array Queue 📦

🧱 Idea base

Vamos a crear una clase llamada ArrayQueue.

Esta cola debe tener los siguientes métodos:

Método	Descripción
enqueue()	Agregar un elemento al final
dequeue()	Retirar el elemento del frente
peek()	Ver el frente sin quitarlo
isEmpty()	Verificar si la cola está vacía
isFull()	Verificar si la cola está llena

🧩 Arreglo base

Imagina un arreglo de tamaño 5:

[  ,  ,  ,  ,  ]

Al inicio:

frente = 0
rear  = -1

🧠 Los elementos se agregan al final,
y se eliminan del frente — ¡sin mover físicamente los datos!

🔁 Movimiento de los punteros

flowchart LR
    subgraph Cola["🧮 Cola en Array"]
    A0["Índice 0"] --> A1["Índice 1"] --> A2["Índice 2"] --> A3["Índice 3"] --> A4["Índice 4"]
    end

    style Cola fill:#fefefe,stroke:#aaa,stroke-width:2px
    F([frente=0]) -.-> A0
    R([rear=-1]) -.-> A4

➡️ Cuando hacemos enqueue(10), movemos rear y guardamos el valor:

rear = 0
[10,  ,  ,  ,  ]

🧮 Ejemplo paso a paso

Inicialmente:
[  ,  ,  ,  ,  ]   frente=0 cola=-1

enqueue(10):
[10,  ,  ,  ,  ]   frente=0 cola=0

enqueue(20):
[10, 20,  ,  ,  ]  frente=0 cola=1

enqueue(30):
[10, 20, 30,  ,  ] frente=0 cola=2

🧱 Eliminación (dequeue)

Cuando retiramos (dequeue()):

dequeue()  → 10
frente se mueve → 1

[10, 20, 30,  ,  ] frente=1cola=2

🔹 El valor 10 sigue en memoria, pero ya no forma parte de la cola lógica.

💡 Problema con la implementación básica

Si hacemos varios dequeue(), el puntero frente seguirá avanzando…

[10, 20, 30,  ,  ]
frente=3 cola=4

😱 ¡A pesar de tener espacios vacíos, el arreglo parece lleno!

🧩 Solución: usar índices circulares (modulares).

🔁 Cola circular (Circular Queue)

Cuando rear llega al final, puede volver al inicio:

rear = (rear + 1) % items.length;
frente = (frente + 1) % items.length;

De esta forma, reutilizamos los espacios liberados. ♻️

💻 Código completo (ArrayQueue.java)

public class ArrayQueue {
    private int[] items;
    private int frente;
    private intcola;
    private int count;

    public ArrayQueue(int capacity) {
        items = new int[capacity];
        frente = 0;
       cola = -1;
        count = 0;
    }

    public void enqueue(int item) {
        if (isFull())
            throw new IllegalStateException("Cola llena");

       cola = (rear + 1) % items.length;
        items[rear] = item;
        count++;
    }

    public int dequeue() {
        if (isEmpty())
            throw new IllegalStateException("Cola vacía");

        int value = items[frente];
        frente = (frente + 1) % items.length;
        count--;
        return value;
    }

    public int peek() {
        if (isEmpty())
            throw new IllegalStateException("Cola vacía");
        return items[frente];
    }

    public boolean isEmpty() { return count == 0; }
    public boolean isFull() { return count == items.length; }

    @Override
    public String toString() {
        return java.util.Arrays.toString(items);
    }
}

🧠 Visualización circular

flowchart LR
    subgraph Circular["🔄 Cola Circular (capacidad = 5)"]
    A["20"] --> B["30"] --> C["40"] --> D[" "] --> E["10"]
    end

    F([frente=4]) -.-> E
    R([rear=2]) -.-> C

👁‍🗨️

• frente apunta al inicio lógico
• rear apunta al último elemento insertado
• Al llegar al final, rotan al inicio

🧪 Ejemplo de uso

public static void main(String[] args) {
    ArrayQueue queue = new ArrayQueue(5);
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    System.out.println(queue); // [10, 20, 30, 0, 0]

    queue.dequeue();
    queue.dequeue();
    System.out.println(queue); // [10, 20, 30, 0, 0] (pero lógicamente: [30])

    queue.enqueue(40);
    queue.enqueue(50);
    System.out.println(queue); // circularmente llena
}

⚖️ Comparación rápida: FIFO vs LIFO

Estructura	Significado	Orden de salida	Ejemplo
🧺 Queue	First In, First Out	Sale el primero que entró	Fila del banco 🏦
📚 Stack	Last In, First Out	Sale el último que entró	Pila de platos 🍽️

flowchart LR
    subgraph FIFO["🧺 Queue (FIFO)"]
        A1["Entra 10"] --> A2["Entra 20"] --> A3["Entra 30"]
        A3 -->|Sale primero 10| A4["[20, 30]"]
    end

    subgraph LIFO["📚 Stack (LIFO)"]
        B1["Apila 10"] --> B2["Apila 20"] --> B3["Apila 30"]
        B3 -->|Sale primero 30| B4["[20, 10]"]
    end

🏁 Conclusión

✨ Con esta implementación:

• Usamos un array circular para manejar eficientemente el espacio.

• Controlamos la cola con dos punteros: frente y rear.

• Practicamos conceptos de:

  • Modularidad ( % )
  • Manejo de excepciones
  • Reutilización de memoria

💡 Ideal para entrevistas y evaluaciones de estructuras de datos.

🎬 ¡Nuestra ArrayQueue ya está lista para la acción! 🚀