Algoritmos y Estructuras de Datos (VJ1215)

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)

};