We continue our study of ADTs with the Stack ADT in this chapter. As we did
in Chapter 18, we start with the definition of the Stack ADT and present two
different implementations. We conclude the chapter with sample applications of
the Stack ADT.
The Stack ADT is modeled after a physical stack of items, such as a stack
of pancakes or a stack of plates. If you were asked to remove any plate from a stack
of plates, which one would you remove? The topmost one, of course. Similarly,
the most effortless place to add a new plate is at the top of the stack. Like its physical
counterpart, the defining feature of the Stack ADT is its restrictive insertion
and removal operations. An item can only be added to the top of the stack, and
only the topmost item of the stack can be removed. Because of this restriction, the
Stack ADT is quite simple. And consequently, its implementations are relatively
straightforward, compared to the List ADT. As simple as it may be, the Stack ADT
is remarkably versatile and useful in many diverse types of applications.
