Stacks

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

• Data can be inserted only at the end of a stack.
• Data can be deleted only from the end of a stack.
• Only the last element of a stack can be read.

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.

Our diagrams will reflect this terminology by viewing stacks as vertical arrays, like so:

As you can see, the first item in the array becomes the bottom of the stack, while the last item becomes the stack’s top.

While the restrictions of a stack seem—well—restrictive, we’ll see shortly how they’re to our benefit.

To see a stack in action, let’s start with an empty stack.

Inserting a new value into a stack is also called pushing onto the stack. Think of it as adding a dish onto the top of the dish stack.

Let’s push a 5 onto the stack:

Again, there’s nothing fancy going on here. All we’re really doing is just inserting a data element into the end of an array.

Now let’s push a 3 onto the stack:

Next, let’s push a 0 onto the stack:

Note that we’re always adding data to the top (that is, the end) of the stack. If we wanted to insert the 0 into the bottom or middle of the stack, we couldn’t, because that’s the nature of a stack: data can only be added to the top.

Removing elements from the top of the stack is called popping from the stack. Because of a stack’s restrictions, we can only pop data from the top.

Let’s pop some elements from our example stack.

First, we pop the 0:

Our stack now contains only two elements: the 5 and the 3.

Next, we pop the 3:

Our stack now only contains the 5:

A handy acronym used to describe stack operations is LIFO, which stands for last in, first out. All this means is the last item pushed onto a stack is always the first item popped from it. It’s sort of like students who slack off—they’re always the last to arrive to class but the first to leave.