Curso 2024/2025
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) };