I recently took a Data Structures course and the required textbook was, to put it mildly, abysmal. The author's grasp of the language is shaky, the examples suck, and the explanations of the concepts go on and on. I can't believe I paid for this. I checked out the first edition (published in '99) and besides some color and font tweaks, nothing has changed!
Luckily, an awesome human being decided to release his Data Structures textbook as a pdf, free to the world, and, it's good. Explanations are concise and to the point and the use of the language is solid. Plus, you have your choice of C++ and Java versions of the text. While you're there, check out the AlgoViz.org link for lots of visual examples on how your favorite algorithms work.