While arrays allow us to add or remove elements at any index, sometimes we need a data structure where we have more control over adding and removing items. In this article, I am going to explain what stacks are, how we can use them to address this sort of problem, and provide examples of implementation.

What is a Stack?

A stack is an ordered collection of items that follows the last in, first out (LIFO) principle. In other words, the addition and removal of items happen at the same end. The newest elements are near the top of the stack and the oldest are near the base. You can think of a stack as a stack of books or even your browser history (the browser’s back button).

The Pros and Cons of Stacks

Stacks allow for constant time when adding and removing elements. This is due to the fact that you don’t need to shift elements around to add and remove them from the stack.

The downside of stacks is that they don’t offer constant-time access to the nth element in the stack, unlike an array. This means it could take O(n) time to retrieve an element where n is the number of elements in the stack.

Creating an Array-based Stack Class

I encourage you to try this on your own if you haven’t before since it is a great way to learn about how stacks work and to experiment with this essential data structure.

class Stack {
  constructor() {
    this.items = [];
  }
}

In our example, we are using an array to store the elements of the stack. Since the stack follows the LIFO principle however, we will need to limit the functionalities that will be available for the insertion and removal of elements. The following methods will be available in the Stack class:

• push(element(s)): add an element (or several elements) to the top of the stack.
• pop(): remove the top element of the stack and return the removed element.
• peek(): return the top element of the stack without modifying the stack itself.
• isEmpty(): return true if the stack does not contain any elements, false if the stack’s size is greater than 0.
• clear(): remove all elements from the stack.
• size(): return the number of elements in the stack (similar to the length property of an array). If you want some practice, I challenge you to implement the methods mentioned above on your own. If you don’t want spoilers, stop scrolling!

class Stack {
    constructor() {
        this.items =[];
    }

    push(item) {
        return this.items.push(item);
    }

    pop() {
        return this.items.pop();
    }

    peek() {
        return this.items[this.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    clear() {
        this.items = [];
    }

    size()  {
        return this.items.length;
    }
}

Solving Problems Using Stacks

Stacks can be applied to a variety of real-world problems. They can be used for backtracking problems, remembering paths taken, and to undo actions. I will go over one example and encourage you to try solving others on your own, perhaps through HackerRank.

Convert Decimal Numbers to Binary

To convert a decimal number into a binary representation, we can divide the number by 2 (since binary is a base 2 number system) until the division result is 0. For example:

Here is a solution using a stack:

function decimalToBinary(num) {
    const remStack = [];
    let number = num;
    let rem;
    let binaryString = '';

    while (number > 0) {
        rem = Math.floor(number % 2);
        remStack.push(rem);
        number = Math.floor(number / 2);
    }

    while (remStack.length !== 0) {
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

In this algorithm, while the division result is not zero, we get the remainder of the division (modulo - mod), and push it to the stack and update the number that will be divided by 2. Then, we pop the elements from the stack until it is empty, concatenating the elements that were removed from the stack to a string.

Conclusion

In this article, we learned about the stack data structure, implemented our own algorithm that represents a stack using arrays, and we did a practice problem. To learn more, I recommend checking out some of these resources:

• How to Implement a Stack by Prashant Yadav of freeCodeCamp
• Stacks in JavaScript by Loiane Groner from the textbook, Learning JavaScript Data Structures and Algorithms