The most common way we introduce the stack data structure is by saying it’s like a spring-loaded plate dispenser, the kind found in a cafeteria:
Indeed when I looked up stacks in an old computer architecture textbook¹ of mine I found:
stacks are frequently described by the way plates are stored and used in a cafeteria. New plates are added to the top of the stack, or pushed, and plates already on the stack move down to make room for them.
Often we augment the comparison with a diagram showing the members of the stack being pushed down or popped up²:
This is not how stacks work. If all the members moved each time we pushed or popped the stack, it would be very inefficient! Instead what happens is the members don’t move but we update a stack pointer to point to the top of the stack. Perhaps a better analogy is a deck of cards, or a stack of papers:
These seem ok, although the familiarity of the objects introduce other activities which don’t apply to stacks, like “cutting” a deck of cards or grabbing wads of paper at a time to shred before the authorities arrive.
Here’s a tip I’ve learned; when in need of a good computing metaphor, check Knuth. In this case³ he polishes up a Djikstra⁴:
A railroad yard is pretty good, perhaps a little dated and abstract for younger students though. Knuth goes on to write:
Stacks have been called push-down-lists, reversion storages, cellars, nesting stores, piles, last-in-first-out (“LIFO”) lists and even yo-yo lists…This multiplicity of names is interesting in itself, since it is evidence for the importance of the concepts.
I humbly submit that it’s evidence that computer scientists proliferate bad metaphors. In searching for alternatives, I came across this fun one from Terry Su⁵:
But who removes one pringle at a time? And what kind of psycho puts pringles back in the can? A similar analogy that avoids gluttony is a tennis ball canister:
One objection might be that people frequently invert the canister to tip all of the balls out onto the court; although they do fall out in order still. And tennis does have an air of elitism about it. How about a stack of shopping baskets?
This seems like a good candidate to me:
- Almost every student will have used one
- The baskets in the stack do not move up or down on push/pop
- In theory only one basket is removed or returned at one time
- In reality upon removal a basket will frequently stick to the one below it, making it hard to remove or bringing two baskets at a time. Thus introducing students to the concept of bugs
References
- Englander; The Architecture of Computer Hardware and System Software: An Information Technology Approach, Fourth Edition.
- Ibid.
- Knuth; The Art of Computer Programming, Third Edition.
- Djikstra; ALGOL Bulletin Supplement Number 10. ALGOL-60 Translation
- Su; Vivid Metaphor of Data Structures
Postscript
Whilst searching for images of cafeteria plate dispensers I did find this beauty, a “dish dolly” which is more like a stack than a spring-loaded plate dispenser. Unfortunately if we taught stacks as being “like dish dollies” I don’t think anybody would know what we were talking about.
Tags: data-structures knuth djikstra