Stacks. What are they? 🥞

Ali Bazzi — Thu, 07 Nov 2019 01:03:59 +0000

A stack is a container of objects that are inserted and removed according to the last-in-first-out principle.

This is the official definition of a stack, but let's look at a more practical in-depth definition.

Stacks

As the name suggests, you stack objects on top of each other.

1- Operations

A stack, much like any other data structure, can have some operations applied to it.

Push: Insert an object to the top of the stack.
Pop: Remove an object from the top of the stack.
Peek: Return the object at the top of the stack.

These 3 operations are the main operations for a stack. There are other operations as well, such as searching for an object, checking if the stack is empty, etc...

Having said that, do you notice anything similar between those 3 operations?

Exactly. There's only one entry and exit point in a stack and that's the TOP.

2- Implementation

Even though a stack can be implemented using arrays, I'm going to use linked lists with ES6 Classes for that.

class Node{
  constructor(data) {
    this.data = data,
    this.next = null
  }
}

Node represents an object in the stack and it has 2 properties:

data: the value of the object.
next: the next object in the stack.

class Stack{
  constructor(){
    this.top = null;
  }

  peek(){
    return this.top;
  }

  push(value){
    const newNode = new Node(value);
      if(this.top){
        newNode.next = this.top;
        this.top = newNode;
      }
      else
        this.top = newNode;
  }

  pop(){
    if(this.top)
      this.top = this.top.next;
  }
}

This is one way you can implement a stack using linked lists. Now, let's take every function and explain the logic behind it.

constructor(){
  this.top = null;
}

As mentioned earlier, we are only interested in the top of the stack, so we assign it as a property.

peek(){
  return this.top;
}

Peek: Nothing much to explain here, it returns the top and if it doesn't exist, it returns null.

 push(value){
   const newNode = new Node(value);
   if(this.top)
     newNode.next = this.top;

   this.top = newNode;
 }

Push: This function takes a value as an argument and creates a new node object having that value.
If there is a top object, assign the new node's next property to the top object.
Change the top to reference the new node.

pop(){
  if(this.top)
    this.top = this.top.next;
}

Pop: This function checks if the top object exists first. If it does, assign the next node as the top. The way JavaScript works, if it sees an object that isn't referenced anymore, it gets removed (garbage collection).

isEmpty(){
  if(this.top)
    return true;
  return false;
}

isEmpty: I have added this function, as it helps in traversing the stack. You can also implement it using the already defined peek function.

3- Use Cases

Here are some use cases of the stack:

Reversing the order: This is one of the most generic cases for the stack. Think about it, the first item to enter a stack is the last one to leave it (LIFO), so inserting objects in a specific order results in the reverse of that order.
Undoing actions: Undoing changes in your IDE or any other platform makes use of stacks. Basically, when you hit ctrl+z, the top of the stack (most recent change) gets popped.
Going back and forth in a browser: Are you starting to visualize how a stack works?
For example, assume your browser's homepage is Google. You decide to visit dev.to, Google gets added to the stack. When you press the back button, it grabs the top of the stack and displays it. i.e. Google.
Recursion: If you don't know what recursion is, uh, read about it? 🙂
It's basically a function that calls itself over and over until it reaches a base case. It uses a stack to keep track of the function calls and when it's time to process one of the instances, it pops the top call from the stack and executes it.

P.S. For real tho, recursion is an algorithm that needs a separate post to explain in detail, should it be my next post?

4- Stack Overflow

No, not the website.

What does stack overflow actually mean?

A stack has a specific memory allocated to it, so when the stack is filled and you try adding another object to it, it results in an overflow.

How can you enact a stack overflow you ask?

It's nothing too complicated really.
Take this function for example

function overflow(){
  overflow();
}

This is a recursive function, but not just any recursive function. There's no specific condition to stop the calls, this is what's known as infinite recursion.

When this function is called, the stack will look something like this

Make sure your recursive functions don't run infinitely, it's... bad.

5- Final Words

For anyone reading this, all I can say is, I'm sorry. 🙇‍♂️

On a serious note, this is my first post. Ever.

I wanted to talk about queues as well, but I felt that the post was getting a bit long. Part 2?

I hope this has helped you understand stacks a little bit more. 😊