Stack Data Structure | Skilled.dev
Learn

Stacks

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
A stack is a linear data structure that we use when we care most about the top item (the one that is most recently added). Adding or removing is always done at the top and happens in O(1) time. Stacks operate in last-in-first-out (LIFO) order. The last item (most recent) is the first one that will be removed.
Think of your browser's "back" button - you only care about the page you most recently visited. You add items to the stack as you visit more pages. When you click "back", the browser grabs the page from the top of the stack and displays it to you. As you continue to click back, you get the pages starting from the one most recently visited and move backward until you reach the page you first visited.
push(bottom)
top
middle
bottom

Cheat Sheet

push
pop
top (last in)
bottom (first in)
Big O Complexity
pushO(1)
popO(1)
peekO(1)
spaceO(n)
Pros 🔥
  • Fast Access at the Last Item
    We can add/remove/access the last item in O(1) time.
  • Ordered
    The data is ordered where the most recently added items are at the top of the stack, and the oldest items are at the bottom.
Cons 🤕
  • Slow Lookups
    To access any item other than the top, it will take O(n) time to iterate through the stack and find it.

Stacks in Interviews

  • Balancing brackets / parentheses ([[()]])
  • Managing minimum or maximum values
  • Build a queue using stacks

Stacks Explained

A simple real-world analogy of a stack is a pile of dirty dishes in your sink. You can continue to add a dish to the top after every meal, and when you go to clean them you start with the top dish (the last added) and work your way to the bottom (the first added). Adding or removing is always done at the top and the plates are stored linearly. If you wanted to grab a dish in the middle, you would have to remove all the ones on top of it.

Stacks are essential in computer science and foundational to how our code runs. You may have heard the terms "call stack", "stack trace", or "stack overflow". When we call functions or execute operations, they often call additional functions/operations. These accumulate in a stack until you reach the last item called. The result for this top item is calculated and then it passes that value to the item before it the stack that needed it. Our code must execute in this order since each step requires a result from another function and will work from the top of the stack down to the initial function that called it.

The example is a high-level demo of what happens with our call stack. It builds the stack up to final operation needed to calculate the total and unwinds once it gets back to the initial run function at which point it is complete.

function run(id) {
  return calculatePrice(new Item(id));
}

function calculatePrice(item) {
  return item.price + calculateTax(item.price);
}

function calculateTax(price) {
  return price * 1.1;
}

run('id1');


|  price * 1.1                           |
|  item.price + calculateTax(item.price) |
|  new Item('id1')                       |
|  calculatePrice(item)                  |
|  run('id1')                            |
------------------------------------------
   Call Stack

The call stack is this list of functions/operations that must occur in order for our code to run. A stack overflow happens when the call stack grows larger than the memory of our computer. A stack trace shows the order of the call stack when an error occurs so we can figure out where the bug happened.

Higher-level implementations of stacks we see:

  • Undo button: it stores linearly and we can get to the most recent version of a document when we hit undo
  • Back button in a browser: the pages we visit are stored as a stack
  • Messages or emails are typically presented with the most recently added first
  • Depth first search
Prev
Implement a Queue
Next
Implement a Stack

Table of Contents