
1034 CHAPTER 14 An Introduction to Data Structures
14.3 Implementing a Stack Using a Linked List
Imagine a group of college students on a spring break, sharing an apartment.
After they eat, they typically pile up the dirty dishes in the kitchen sink.Another
meal is consumed, and more dirty dishes are piled on top of the existing ones.
At the top of the pile is the dirty dish that was placed there last. Soon the stu-
dents run out of clean dishes, and somebody will have to start cleaning them.
He or she will start by cleaning the dish at the top of the pile, that is, the last dish
placed on the pile. That approach is called last in, first out, or LIFO ...