Curso 2024/2025
La siguiente solución tiene coste temporal en el peor caso O(n) y en el mejor caso O(1), siendo n la talla de la cola.
void Cola::eliminar(int dato) { eliminar(dato, primero, nullptr); } void Cola::eliminar(int dato, Nodo * actual, Nodo * anterior) { if (actual == nullptr) return; if (actual->dato == dato) { if (actual == primero) primero = primero->siguiente; else anterior->siguiente = actual->siguiente; if (actual == ultimo) ultimo = anterior; delete actual; } else eliminar(dato, actual->siguiente, actual); }
El primero de esos dos métodos es público y el segundo es privado.
class Cola { struct Nodo { int dato; Nodo * siguiente; Nodo(int); }; Nodo * primero; Nodo * ultimo; void mostrar(Nodo *) const; void eliminar(int, Nodo *, Nodo *); public: Cola(); // O(1) void encolar(int); // O(1) void desencolar(); // O(1) int consultarPrimero() const; // O(1) void mostrar() const; // O(n) bool estaVacia() const; // O(1) void eliminar(int); // O(n) };