The first two abstract data structures we will explore are stacks and queues, which are often thought of as a pair—like peanut butter and jelly. Why this is so may be more for historical reasons than anything else, because these two structures have quite different behaviors.

A stack is an abstract composite structure in which accesses are made at only one end. You can insert an item as the first one and you can remove the first one. This type of processing is referred to as LIFO, which stands for “last in, first out.” This design models many things in real life, such as a plate holder in a cafeteria: We can take only the top plate. When we do so, the plate below rises to the top so the next person can take one. Canned goods on a grocer’s shelf also exhibit this property. When we take the first can in a row, we are taking the last can put in that row.

Another way of stating the accessing behavior of a stack is to say that the item removed is the item that has been in the stack the shortest time. Viewing a stack from this perspective is abstract. The insertion operation has no constraints; the entire LIFO behavior is specified through the removal operation.

The mental image of the cafeteria plates has left an imprint on the traditional names used for the insertion and removal operations. Adding an item to the stack is called Push; removing an item is called Pop. We Push an item onto the stack, and we Pop an item off the stack. A stack does not have the property of length, so there is no operation that returns the number of items on the stack. We do need operations that determine whether a stack is IsEmpty, however, because trying to Pop an item when the stack is empty is an error.

Here is an algorithm that reads in numbers and prints them in reverse order using a stack. We have not colored the stack operations in red because they have already been implemented by someone else; they are ours to use. Because the more data is not relevant to our discussion, we leave it unexpanded here and in the following algorithms.

Desk-check this algorithm to convince yourself that the values are, indeed, written in reverse order.