¿Se puede reemplazar completamente la estructura en la programación de estructuras de datos por clase?

Si usas C++ y no te importa la encapsulación, la respuesta es sí.

En el estándar C++, un tipo de clase se puede definir mediante cualquier palabra clave de estructura o clase. La única diferencia entre ellas es su nivel de acceso predeterminado (Nivel de acceso).

Sabemos que un tipo de clase puede declarar sus miembros sin un Especificador de Acceso. Para la palabra clave struct, todos los miembros que aparecen antes de una declaración de nivel de acceso tendrán un nivel de acceso público de forma predeterminada. Para la palabra clave class, el nivel de acceso es privado.

Referencia: Introducción a C++ ¿Quinta edición?§7.2 (p. 268)