This chapter introduces two important interfaces, Stack and Queue. Each corresponds to a data structure holding a collection of objects, ordered by when they were inserted into the structure. A stack gives us access to only the newest (most recently inserted) object, whereas a queue gives us access to only the oldest object.
Section 4.1 introduces the Stack interface. We discuss how a stack behaves, putting off the implementation until later chapters. Generic classes, new to Java 1.5, are introduced in this section. We use stacks in the solitaire card game Idiot's Delight. Section 4.2 explores another important stack application: the call stack, which Java uses to keep track of all of the methods running at a given time. Knowing about the call stack helps us to understand many other principles and Java features, such as exceptions. Exceptions, introduced in Section 4.3, provide a way to recover gracefully from errors. Section 4.4 discusses the Queue interface and uses it in the game of War.
The Stack Interface |
Part I: Object-Oriented Programming
Encapsulation
Polymorphism
Inheritance
Part II: Linear Structures
Stacks and Queues
Array-Based Structures
Linked Structures
Part III: Algorithms
Analysis of Algorithms
Searching and Sorting
Recursion
Part IV: Trees and Sets
Trees
Sets
Part V: Advanced Topics
Advanced Linear Structures
Strings
Advanced Trees
Graphs
Memory Management
Out to the Disk
Part VI: Appendices
A. Review of Java
B. Unified Modeling Language
C. Summation Formulae
D. Further Reading
Index