Implementación en Java de Estructuras de Datos: ColaLista y ColaVec

Implementación de Estructuras de Datos tipo Cola en Java

En este documento se presentan dos formas fundamentales de implementar la estructura de datos Cola (FIFO - First In, First Out) en el lenguaje de programación Java: mediante el uso de listas enlazadas (ColaLista) y mediante el uso de vectores redimensionables (ColaVec).

Implementación basada en Listas Enlazadas: ColaLista

La clase ColaLista utiliza nodos enlazados para gestionar los elementos de manera dinámica, evitando problemas de capacidad fija inicial.

import org.mp.practicas.excepciones.*;

public class ColaLista implements Cola {
    private NodoLista cabeza;
    private NodoLista fin;
    private int tamano;

    public ColaLista() {
        cabeza = null;
        fin = null;
        tamano = 0;
    }

    public boolean esVacia() {
        return cabeza == null;
        // if (tamano == 0)
        //     return true;
        // else
        //     return false;
    }

    public Object primero() throws DesbordamientoInferiorException {
        if (esVacia())
            throw new DesbordamientoInferiorException("Cola vacía");
        return cabeza.dato;
    }

    public Object quitarPrimero() throws DesbordamientoInferiorException {
        if (esVacia())
            throw new DesbordamientoInferiorException("Cola vacía");
        tamano--;
        Object primero = cabeza.dato;
        cabeza = cabeza.siguiente;
        return primero;
    }

    public void insertar(Object x) {
        if (esVacia()) {
            fin = cabeza = new NodoLista(x);
            tamano++;
        } else {
            fin.siguiente = new NodoLista(x);
            fin = fin.siguiente;
            tamano++;
        }
    }

    public void vaciar() {
        cabeza = null;
        fin = null;
        tamano = 0;
    }

    public int tamano() {
        return tamano;
    }
}

Implementación basada en Vectores: ColaVec

La clase ColaVec utiliza un array subyacente para almacenar los elementos, implementando además una gestión dinámica de la capacidad que redimensiona automáticamente el vector cuando este se llena.

import org.mp.practicas.excepciones.*;

public class ColaVec implements Cola {
    private Object[] vector;
    private int cabeza;
    private int fin;
    private static final int TAMANO_POR_DEFECTO = 10;
    private int tamanoCola;

    public ColaVec() {
        vector = new Object[TAMANO_POR_DEFECTO];
        cabeza = 0;
        fin = -1;
        tamanoCola = 0;
    }

    public boolean esVacia() {
        if (tamanoCola == 0)
            return true;
        else
            return false;
    }

    public Object primero() throws DesbordamientoInferiorException {
        if (esVacia() == true)
            throw new DesbordamientoInferiorException("Cola vacía");
        return vector[cabeza];
    }

    public void insertar(Object x) {
        if (tamanoCola == vector.length)
            asegurarCapacidad();
        fin = incrementar(fin);
        vector[fin] = x;
        tamanoCola++;
    }

    private void asegurarCapacidad() {
        Object[] aux = new Object[vector.length * 2];
        for (int i = 0; i < tamanoCola; i++, cabeza = incrementar(cabeza)) {
            aux[i] = vector[cabeza];
        }
        vector = aux;
        cabeza = 0;
        fin = tamanoCola - 1;
    }

    private int incrementar(int n) {
        n++;
        if (n == vector.length) {
            n = 0;
        }
        return n;
    }

    public Object quitarPrimero() throws DesbordamientoInferiorException {
        if (esVacia() == true)
            throw new DesbordamientoInferiorException("Cola vacía");
        Object fuera = vector[cabeza];
        cabeza = incrementar(cabeza);
        tamanoCola--;
        return fuera;
    }

    public int tamano() {
        return tamanoCola;
    }

    public void vaciar() {
        tamanoCola = 0;
        cabeza = 0;
        fin = -1;
    }
}