Stacks and Queues

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.