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.

bool Cola::buscar(int dato) const {

   return buscar(dato, primero);

}

bool Cola::buscar(int dato, Nodo * n) const {

   if (n == nullptr)
      return false;
  
   if (n->dato == dato)
      return true;

   return buscar(dato, n->siguiente);

}
      

Alternativamente, utilizando operadores lógicos (y teniendo en cuenta que se evalúan en cortocircuito):

bool Cola::buscar(int dato) const {

   return buscar(dato, primero);

}

bool Cola::buscar(int dato, Nodo * n) const {

   return n != nullptr && (n->dato == dato || buscar(dato, n->siguiente));

}
      

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;
   bool buscar(int, Nodo *) const;

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)
   bool buscar(int) const;       // O(n)

};