My First Data Structure: Stacks

Recently, I was on LeetCode attempting to solve the problem Valid Parentheses. After spending too much time struggling, writing solutions that might work on my repl, but fail the tests, attempting even to use recursion, I realized I needed help. And that help was stacks.

Mad Stacks

What is a stack?

A stack is a linear data structure, very similar to a queue. The big difference between stacks and queues, however, is the order in which items are added and removed. In a stack, the last item added will be the first item removed (think of it like a stack of plates: to get to the plate on the bottom, you have to take all of the other plates off the top, first). This order is commonly referred to as either FILO (first in, last out) or LIFO (last in, first out).

stack diagram

To add an item to a stack, we refer to this as pushing. Similarly, removing an item from a stack is called popping.

Stacks are ultimately really useful. Take, for example, your browser history. Your browser stores the websites you’ve visited in the same way records are added to a stack. If you hit the back button, you don’t return to the first place you visited in your browser, but the most recent.

Using Stacks: Word Reversal

One of the simplest applications of a stack is using it to reverse a string or an array:

reverseArray = (arr) => {
  let stack = []
  
  while (arr.length > 0) {
    stack.push(arr.shift())
  }
  
  while (stack.length > 0 ) {
    arr.push(stack.pop())
  }
  
  return arr
}

Here, we push all of the elements in our original array (check out this explanation on the shift method if you’re unfamiliar with how that method works!) into our stack in the original order. Then, we can use the array pop method which will remove and return the last element from our array. As we empty our stack, we add the elements back to our original array, though this time, thanks to LIFO, in reverse order.

Stacks + Valid Parentheses

You might remember that I started this post by saying that I used stacks to solve LeetCode’s Valid Parentheses problem. I’ve decided not to go over my solution in this post as I was unable, ultimately, to solve this problem on my own. If you’re curious how to solve this problem and have been struggling for a while (seriously, now that you know about stacks, please go try it on your own first!) then, I’d recommend taking a look at this super helpful solution that ultimately got me to understand how this algorithm works.

Melissa McCarthy + Stacks

Sources

Concepts of Stack in Data Structure