A Common-Sense Guide to Data Structures and Algorithms

Stacks

A stack stores data in the same way that arrays do—it’s simply a list of elements. The one catch is that stacks have the following three constraints:

• Data can only be inserted at the end of a stack.
• Data can only be read from the end of a stack.
• Data can only be removed from the end of a stack.

You can think of a stack as an actual stack of dishes: you can’t look at the face of any dish other than the one at the top. Similarly, you can’t add any dish except to the top of the stack, nor can you remove any dish besides the one at the top. (At least, you shouldn’t.) In fact, most computer science literature refers to the end of the stack as its top, and the beginning of the stack as its bottom.

While these restrictions seem—well—restrictive, ...