For an overview of Java, the book resource you cited (Deitel Java - How to Program), is an excellent source. I would suggest that you use it to familiarize yourself with the very basics of Java.

You don't have to go through the entire book cover to cover, but enough of it that you are at least familiar with basic java concepts and syntax. With that, proceed immediately to Android specific programming.

I had suggested some resources for starting out with Android development which you may want to look at: https://news.ycombinator.com/item?id=7016067