Data Structures and the Java Collections Framework, Third Edition

CHAPTER 8

Stacks and Queues

In this chapter we introduce two more abstract data types: stacks and queues. Stacks and queues can be modified in only a very limited way, so there are straightforward implementations, that is, data structures, of the corresponding data types. Best of all, stacks and queues have a wide variety of applications. We'll start with stacks because a stack is somewhat easier to implement than a queue.

CHAPTER OBJECTIVES

1. Understand the defining properties of stacks and queues, and how these properties are violated by the Java Collections Framework's stack class and Queue interface.
2. For both stacks and queues, be able to develop contiguous and linked implementations that do not violate their defining properties.
3. Explore the use of stacks in the implementation of recursion and in converting from infix notation to postfix notation.
4. Examine the role of queues in computer simulation.

8.1 Stacks

A stack is a finite sequence of elements in which the only element that can be removed is the element that was most recently inserted. That element is referred to as the top element on the stack.

For example, a tray-holder in a cafeteria holds a stack of trays. Insertions and deletions are made only at the top. To put it another way, the tray that was most recently put on the holder will be the next one to be removed. This defining property of stacks is sometimes called "Last In, First Out," or LIFO. In keeping with this view, an insertion is referred to as a push, and ...