December 24, 2017 · Computer Science Data Structures

Stacks as a Stack of Plates

You can think of a stack as a stack of plates. Seriously, if you've ever interacted with a stack of plates IRL, you already know everything you need to know about how to work with stacks as a data structure. So let's think about this. Imagine you're back in the college dining hall and you're standing before a stack of plates.

plates

You need to get a plate so that you can get a piece of that delicious pepperoni pizza. Which plate do you get? Nope that wasn't a trick question. Throughout my entire college career, I don't think I've ever taken a plate that wasn't at the top of the stack.

So far so good, but I'm going to ask you to stretch your imagination for a brief moment and consider this. What if you really wanted the plate at the bottom of that stack? First of all, why would anyone ever want to do such a thing? Second of all... why would anyone ever want to do such a thing?! I hear you, but just humor me for a sec here. If I really wanted the bottom plate, I can't just snatch it out directly. No matter how deft or ninjalike I am, that stack of plates is going to fall and crash. Hard. So what I need to do is take the plate at the top of the stack and place it... somewhere else. And then I repeat this until I've taken every plate but one off the top of the stack. And then finally, I can get that coveted bottom plate and get my pepperoni pizza.

What this illustrates is that I can only work with the top plate of a stack at any given time. And this is still true even if all I need is to get to the bottom plate. In that case, I still need to remove the top plate over and over and over again until I finally get to the bottom plate.

Stacks Defined

A stack is an abstract data type that is defined by two very simple rules:

  1. You can only insert at the top of the stack.
  2. You can only delete from the top of the stack.

These operations are usually called "pushing" onto the stack and "popping" from the stack. Oftentimes, you can also "peek" at a stack (read from the top of the stack). And you'll most likely also be able to check if the stack is empty.

In the dining hall pizza example, you could say that I "popped" each plate off the stack until I got to the very bottom plate. I then popped the bottom plate off as well. But instead of putting the bottom plate off to the side along with all the others, I kept the bottom plate for myself. And being the good citizen that I am, I would then "push" each plate back onto the top of the stack, leaving the stack of plates exactly as it was before sans the bottom plate.

Stacks implemented

But how is a stack implemented? A stack is an abstract data type, so it can be implemented as either a linked list or an array. Abstract means that the definition of the data structure itself is agnostic about exactly how it is implemented.

Here's a question for you. If we want to implement a stack with a linked list, what do you think the top of the stack should be? The head node or the tail node? Recall that linked lists boast O(1) inserts and deletes at the beginning of the list. If we treat the head node as the top of our stack, this makes all of our stack operations O(1)! This is perfect, so we treat the head node as the top of our stack.

linked_list_bottleneck

And what if we want to implement a stack with an array? Recall that arrays boast O(1) inserts and deletes at the end. This is because we don't need to do any shifting at the end. So it makes sense that we should treat the end of the array as the top of our stack. If we do this, all of our stack operations will again be O(1) operations.

So you can see how a stack can be implemented either as a linked list or an array. And with either implementation, we can always maintain O(1) time for all stack operations. Pretty darn cool right?

A Restricted Data Type

One thing that can be confusing about the stack is just how simple it actually is. This may be hard to wrap your head around, as there's nothing about a linked list in itself that says you can only perform operations at its beginning. Similarly, there's nothing about an array in itself that says you can only perform operations at its end. To get over this conceptual hurdle, you can think of a stack simply as a linked list or array with a very restricted API. In other words, by working with a stack, you're essentially limiting yourself to a very narrow and particular set of operations.

But why would anyone ever want to limit themselves like that?! Isn't it better to have more options?

This was my sentiment exactly when I first learned about stacks. But sometimes, performing operations at only the beginning or end of a collection is really all you need to do. And in those cases, it's really nice if all those operations can be done in O(1) time.

Furthermore, the restrictive nature of a stack very elegantly models certain real-world scenarios perfectly. What follows is a partial list of just a few of these applications.

Stacks in the Wild

  1. Your browser history. Go click on the history tab of your browser now. If this article is the last page you visited, it should be the first item on the list (the top of the stack!).
  2. The call stack of any programming environment. Execution of code relies upon something called a "call stack". You normally don't deal with the call stack directly. But sometimes you inevitably catch glimpses of it here and there. For instance, have you ever seen a stack trace? Unless you never make any mistakes when programming, I'll bet that you have. I'm also willing to bet that you've gotten a stackoverflow error if you've ever tried to implement a recursive function. So whenever you write code, you're implicitly making use of a stack all the time!
  3. Undoing a change in any document editor. Made a mistake in your google doc and want to go back? Just pop that sucker off the stack. One and done.

Again, this is just a partial list of some practical use cases of stacks. I'll leave it up to you to find more examples.

That's it!

Stacks are awesome. I'll leave you with this stackoverflow logo, which I've never actually looked at carefully until now. Have you?

stackoverflow