Stack

Today we will talk about stacks, why? Well, because stacks are a mandatory data structure to know as it powers most of what we see in the modern web, do i need to say more than the JavaScript stack?

So what is a stack? Well a stack is a collection of items that will be handled in a particular order, LIFO, which stands for last in first out kind of like a stack of plates, the first one you stack will be the last one to be washed otherwise it'd be pretty annoying right?

Implementation

Now that we know what a stack is we will implement it together. We essentially have two possibilities, one which consists of simply using an array with it's built in capabilities and its drawbacks and the second one with a custom data structure.

Built in array

What built in methods could we use from array to build a stack? Keep in mind that we should apply the Last in, first out strategy. Well i know two perfect methods for this:

• push: method that adds an item to the end of the array
• pop: method which removes the last item from the array

const stack = [];
stack.push(1); // [1]
stack.push(2); // [1,2]
stack.pop(); // [1]

Custom data structure

Now on to our second solution, creating our own data structure, the stack class which is essentially a linked list, meaning it has a head (storing the first item), a tail (storing the last one) and a length property (I'll let you guess this one).

class Stack {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

As mentioned, a stack is composed of items and more specifically nodes which are represented like that:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Here, every node has two properties a value and a next which holds the next item.

Now from there we only need two methods, we'll call them the same as for arrays push and pop but you can call them however you want.

Push

function push(value) {
  const newNode = new Node(value);
  if (this.length === 0) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    const temp = this.head;
    this.head = newNode;
    this.head.next = temp;
  }
  this.length++;
  return this.length;
}

Explanation

So here quite simple we create a new node with the provided value, from there we have two cases to handle:

• the stack is empty, we set our head and tail to be our newNode
• otherwise, we set the second node to be the current head before replacing it with the new node

Once done we take care of bookkeeping by increasing the length and return it.

Pop

function pop() {
  if (this.length === 0) return null;
  const toRemove = this.head;
  if (this.length === 1) {
    this.tail = null;
  }
  this.head = this.head.next;
  this.length--;
  return toRemove;
}

Explanation

A few cases to handle:

• Stack is empty: return null.
• Only one node: set tail to null before removing the head.
• More than one node: set head to head.next (the previous second node becomes the new top).

Once done we decrement the length and return the removed node.

So that's all we need:

const stack = new Stack();
stack.push(1); // 1
stack.push(2); // 2
stack.pop(); // Node {value: 2, next: null}

Performance considerations

With both solutions, both function are extremely efficient it's always constant time, no need to reassign every node's index. For this particular use case a singly linked list is perfect. But if you wanted to do some lookup inside the stack,traversing would be required and you should consider using another data structure.

• Push: O(1) for adding an element to the end of the stack.
• Pop: O(1) for removing an element from the end of the stack.

Practical Use Cases

Stacks are widely used in programming due to their simplicity and efficiency. Here are some common use cases:

• Function Call Management
• Undo/Redo Operations
• Browser History
• Recursion

Conclusion

Congrats 🎉 you made it through I hope you learned a lot, I certainly did and if you have any suggestions, improvements or anything that comes to your mind don't hesitate to write! I'll reply asap!

Happy coding