La manera más fácil de resolver esta tarea es usando std::deque<std::string>, de modo que nosotros no tengamos que preocuparnos del manejo de la memoria. Al igual que std::vector, podemos copiar std::string's libremente y la biblioteca se encarga de apartar la memoria necesaria. Por ejemplo:

   std::deque<std::string> d;
   std::string s;
   
   std::cin >> s;    // leemos la cadena, el usuario ingresa "pablo"
   d.push_back(s);   // guardamos una copia de "pablo" en la parte trasera de la doble cola
   
   std::cin >> s;    // leemos la cadena (sobreescribiendo el valor anterior), el usuario ingresa "juan"
   d.push_front(s);  // guardamos una copia de "juan" en la parte frontal de la doble cola
   
   for (int i = 0; i < d.size( ); ++i) {     // d.size( ) vale 2 porque estamos guardando dos elementos
      std::cout << d[i] << " ";              // d[0] valdrá "juan", d[1] valdrá "pablo"
   }