Constance is OK, but unlikely to be used.
Connie is also OK, but only as a nn for
Constance.
Queenie is awful. So is
Queen, which I suppose is just another word name really, but it does sound very pretentious and silly. DH had to lecture once at a uni not his own, and one of his students was named
Queen Elizabeth Lastname. She went by
Queen Elizabeth, and he said it embarrassed him to call her by name.
Does anyone know if
Queenie originated because in the 19th century parents wanted to name their daughters after
Queen Victoria but felt that
Victoria was or should be her personal property. So they used
Queenie instead, as a sort of nn not just for
Queen but for
Victoria. I'm sure I read that somewhere, but I've lost the reference and never saw it again.