Interview Prep: What Is a Stack?

Interview Prep: Implement a Stack

Oh boy! Are you like me and looking for your first software engineering job. Maybe you’re even a new code school grad?

I’ve had about a dozen “first” interviews now and they’ve each consisted of an online coding test mostly hosted on HackerRank. All of them require solid knowledge of data structures and algorithms. If you can’t pass this test, it seems like you’d never get to a second interview where you might be able to finally talk about your projects or code. Problem is, my code school didn’t teach me data structures or algorithms (nor do I think they should have!) so I’m learning on my own. What’s funny about the whole matter is that most software engineers I’ve spoken to tell me they don’t use that stuff on a daily basis, and if they do need it, they can google it up in less time than it takes an async JS function to run on even a slow server! Be that as it may, I think I’m stuck with this new learning task if I want a job. So let’s dive in and talk about one very fun data structure that’s in this canon of data structures and algorithms: a stack.

What Is a Stack, Exactly?

Glad you asked! Since I’m a big foodie, I like to think of a stack in terms of food. Just imagine yourself standing in front of a griddle on Sunday morning cooking up some pancakes. Cook up your first pancake and put it on a plate. Then a second one--put it on the same plate on top of the first. The third pancake you cook up goes on top of the second, and so on, until you have a nice big stack of pancakes. That is a stack.

But there’s more! Let’s make some observations about our pancake stack. There are only certain ways we can manipulate our stack. For one thing, the only pancake we can really see is the top pancake. The others are hidden below that top pancake. If we want to change the number of pancakes in our stack we really only have two choices: we can either 1) add a pancake to the top of the stack or 2) take that top pancake off the stack and serve it up to some hungry person. If we wanted to see a pancake in the middle of the stack, we simply cannot do that. We’ll have to keep taking pancakes off the top until we get down to the pancake we were interested in.

Oh yes, two other things we could do with our pancake stack: we can have a look at, or peek at, our top pancake (to check if it’s golden brown enough) and we can also check to see if the stack is empty (all pancakes were duly consumed).

Before we move on, let’s summarize the main operations or methods we can perform on our pancake stack. I’ll even add a techie-sounding name for each operation

1. We can add a pancake to the stack. Let’s call this method push().

2. We can take off a pancake from the stack. Let’s call this method pop().

3.We can just look at our top pancake. Let’s call this method peek().

4.We can check to see if there are no more pancakes left on the plate. Let’s call this method isEmpty().

I didn’t mention this above, but we could also keep track of how many pancakes we have on the stack. How about we call this method height().

Advantages and Disadvantages Of a Stack

We can only manipulate the top element of a stack, so that makes it superfast access. Our push() and pop() methods will have O(1) time complexity--and it doesn’t get any better than that.

Of course, the trade off to that quick access to the top element of a stack is that you cannot randomly access any other element below the top. If you did, you’d have to start removing each item from the top until you got to the element you were looking for. Hmmmm...sounds like an O(n) time complexity operation.

You might think that this stack thing is just a ginned-up array. After all, both the array and the stack are list-y type data containers. Well, you’d have a point, actually. But the stack has a space complexity advantage over an array.

Think of a normal array as a chocolate bar like this:

The chocolate bar is a certain size and has to be stored as such--you just can’t break it into smaller pieces. It must be stored in consecutive bits of memory.

In contrast, the stack is not a chocolate bar but can be broken up and can be stored in non-consecutive bits of memory. (Think of how you stuff things here and there in your closet when you are pressed for space). Stacks are really where it’s at when it comes to memory complexity.

And there you have it--a conceptual overview of stacks. Today stacks, tomorrow…..

Happy Interviews!