DEV Community

Cover image for Implementing Stacks with JavaScript
Christina
Christina

Posted on

Implementing Stacks with JavaScript

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!

illustration of push and pop on a stack

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:

decimal to binary conversion 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:

Top comments (5)

Collapse
 
linkstrifer profile image
Link Strifer

The class stack implementation has some errors, this.stack doesn't exist, also This.items should be this.items

gist

Collapse
 
christinamcmahon profile image
Christina

Thanks for pointing that out, I accidentally posted the wrong version from when I was playing around with some things. I corrected it!

Collapse
 
hayrettinsalgin profile image
hayrettin

thank you

Collapse
 
sauloco profile image
Saulo Vargas

And we can do something similar for queues right?

Collapse
 
christinamcmahon profile image
Christina

Yes just remember LIFO (last in, first out) for stacks and FIFO (first in, first out) for queues! General ideas are very similar though! I may write a post about Queues in the future if I think they're different enough to deserve a post.