Algoritmos y Estructuras de Datos (VJ1215)

Las siguientes soluciones tienen coste temporal en el peor caso O(n) y en el mejor caso O(1), siendo n la talla de la cola más pequeña.

Aquí se ilustra cómo resolver el problema sin el atributo laTalla, aunque teniéndolo sería mejor empezar devolviendo false si las tallas de las colas difieren (para reducir el coste temporal en ese caso).

bool Cola::colasIguales(const Cola & otraCola) const {

   return colasIguales(primero, otraCola.primero);

}

bool Cola::colasIguales(Nodo * n1, Nodo * n2) const {

   if (n1 == nullptr && n2 == nullptr)
      return true;

   if (n1 == nullptr || n2 == nullptr)
      return false;

   return n1->dato == n2->dato && colasIguales(n1->siguiente, n2->siguiente);

}
      

Alternativamente, utilizando de otro modo operadores lógicos:

bool Cola::colasIguales(const Cola & otraCola) const {

   return colasIguales(primero, otraCola.primero);

}

bool Cola::colasIguales(Nodo * n1, Nodo * n2) const {

   return (n1 == nullptr && n2 == nullptr )
      || (n1 != nullptr
	  && n2 != nullptr
	  && n1->dato == n2->dato
	  && colasIguales(n1->siguiente, n2->siguiente));

}
      

Observa que, en estas soluciones, lo primero que hace el método recursivo es comprobar si cualquiera de los punteros que le pasan vale nullptr. Haciéndolo así, no es necesario tratar, antes de pasárselos, los casos en que primero o siguiente valen nullptr.

El primero de esos dos métodos es público y el segundo es privado. Observa que debes poner los const, & y * en Cola.h igual que en Cola.cpp:

class Cola {

   struct Nodo {
      int dato;
      Nodo * siguiente;
      Nodo(int);
   };

   Nodo * primero;
   Nodo * ultimo;

   void mostrar(Nodo *) const;
   bool colasIguales(Nodo *, 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 colasIguales(const Cola &) const; // O(n)

};