Two forces are at play. Folks in favor of the traditional CS2 argue rightly that students often understand abstractions best when they "look under the hood" and become intimately familiar with how the abstractions work. Folks in favor of the newer CS2 argue rightly that students learn best what they devote most of their time and effort to, and that in current programming environments we want students to learn best how to use the tools available to them, not "reinvent the wheel".
I think that, for the near future, we need to balance these two forces by teaching the class library both at the level of use and the level of implementation. Studying a class library can mean studying implementations and analyzing their performance. Indeed, such algoritmic analysis is a necessary component in doing trade-off analysis between two candidate data structures. Studying a class library can also mean implementing applications that use data structures and analyzing how their performances vary as we vary the data structure used. Students can use knowledge gained from these two kinds of activity to make decisions about how to implement a new data structure or how to extend an existing data structure.
Can we do all of these things in one semester? With thoughtful instructional design, yes. We cannot devote fifteen weeks to any one of the topics. Instead we have to build our course around problems that challenge students and require them to make real trade-offs. We have to use a yo-yo approach in the class library, bouncing between data structure interfaces and data structure implementations. We have to stop lecturing students on material that they can read ("what is a queue?") and require them to think actively about what they read and program.
Will we bea ble to "cover" every data structure that we would like to cover? If we focus either on interface or on implementation. perhaps. Under the approach I advocate, probably not. I'd rather that my students see a smaller number of data structures, know them well, and know how to think about new data structures effectively than merely have passing familiarity with lots of interfaces or merely have passing familiarity with lots of implementation techniques.