Este problema es para el tema de árboles binarios de búsqueda (en este caso, std::set) pero eso no significa que baste *sólo* std::set.
Para modelar la cola de perritos conviene usar std::deque (en específico, std::deque<std::string>). Para lo que conviene usar std::set es para detectar los nombres duplicados.