Object-Oriented Data Structures Using Java, 3rd Edition

Object-Oriented Data Structures Using Java, 3rd Edition

English | 2012 | ISBN: 978-1-4496-1354-9 | 802 Pages | PDF | 33 MB

Continuing the success of the popular second edition, the updated and revised Object-Oriented Data Structures Using Java, Third Edition is sure to be an essential resource for students learning data structures using the Java programming language. It presents traditional data structures and object-oriented topics with an emphasis on problem-solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors introduce and expand upon the use of many Java features including packages, interfaces, abstract classes, inheritance, and exceptions. Numerous case studies provide readers with real-world examples and demonstrate possible solutions to interesting problems. The authors’ lucid writing style guides readers through the rigor of standard data structures and presents essential concepts from logical, applications, and implementation levels. Key concepts throughout the Third Edition have been clarified to increase student comprehension and retention, and end-of-chapter exercises have been updated and modified. New and Key Features to the Third Edition: -Includes the use of generics throughout the text, providing the dual benefits of allowing for a type safe use of data structures plus exposing students to modern approaches. -This text is among the first data structures textbooks to address the topic of concurrency and synchonization, which are growing in the importance as computer systems move to using more cores and threads to obtain additional performance with each new generation. Concurrency and synchonization are introduced in the new Section 5.7, where it begins with the basics of Java threads. -Provides numerous case studies and examples of the problem solving process. Each case study includes problem description, an analysis of the problem input and required output, and a discussion of the appropriate data structures to use. -Expanded chapter exercises allow you as the instructor to reinforce topics for your students using both theoretical and practical questions. -Chapters conclude with a chapter summary that highlights the most important topics of the chapter and ties together related topics. Instructor Resources: -Answers to the exercises in the text -Glossary of terms -PowerPoint Lecture Outlines -Test bank


The complexities of today require many people to engage in multitasking. For example, right now you may be texting on your phone while watching TV and eating lunch, all at the same time you are doing your data structures homework! Computers also multitask. A computer system can be printing a document, burning a CD, and interacting with a user all at the same time.

Many computer programs require multitasking capabilities. For example, a game program might have separate code sequences to react to changes in user input, to detect collisions between the objects in the game, and to update a scoreboard reflecting the game status. For such a game to be playable each of the code sequences must be active simultaneously and they must interact with each other. Programs that perform this way are called concurrent programs.

Concurrent programs are very common—programs that control systems, provide games, support work productivity, or allow communication are usually concurrent. On a
single processor system concurrency is achieved through the interleaving of the instructions of the various code sequences. The computer jumps back and forth among code sequences, executing a “few” instructions from one sequence, and then a “few” from another sequence, and so on. On systems with dual processors, quad processors, or higher levels of physical support for parallelism the concurrency can be “real.” The computer’s operating system hides the presence or absence of physical concurrency support from the program designer so that as programmers we need not be concerned with the details of that support.

A formal study of program concurrency is typically provided in operating systems, database, or algorithm courses within a computing curriculum and is beyond the scope of this book. However, in this section we introduce the topic by:

  • Defining terminology related to concurrency.
  • Showing how to indicate that parts of a Java program should be executed concurrently.
  • Explaining how concurrent code sequences might interfere with each other.
  • Demonstrating how to synchronize the execution of the code sequences so that such interference does not occur.

Java Threads

The Java concurrency mechanism we present is the thread. Every Java program that executes has a thread, the “main” thread of the program. The main thread has the ability to generate additional threads. When this occurs the various threads of the program run concurrently. The program terminates when all of its threads terminate.

We create thread objects by first defining a class that implements the Java library’s Runnable interface. Such classes must provide a public r un method. As an example see
the following Increase class that accepts a Counter object and an integer a mount through its constructor, and provides a run method that increments the Counter object
the number of times indicated by the value of a mount.