DEV Community 👩‍💻👨‍💻

Cover image for Data Structures & Algorithms in JavaScript(Stack)
Swarup Das
Swarup Das

Posted on • Updated on

Data Structures & Algorithms in JavaScript(Stack)

Hello Everyone, This is part 2 in the series of blogs about data structure and algorithms in JavaScript. Previously I have explained Array. In this blog, I will cover Stack.

What is Stack?

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). - geeksforgeeks.org

An example of stack can be a pile of books, where books are placed one above another, books can be added or remove from the top of the pile of books

List Of Operations Available

  • Push : Insert an element.
  • Pop : Remove an element
  • Peek : Get the topmost element.
  • Size : Get size of the stack.
  • isEmpty : Check if the stack is empty if empty return true else false.
  • Clear : Reset the stack.

Implementation of Stack in Javascript

There are two ways in which stack can implement in javascript one way by using Array or using javascript object( object is a set of key & value).As Array already have push method to insert an element at end of the array, pop method to remove an element, to get the length of the array it has a property length which returns the size of the array if the length is equal to zero then the array is empty. you get the full source here

Implementation of Stack using Javascript Objects

let's define ES6 class name Stack, with two properties,

  • count : It will keep track of the number of elements in the stack.
  • items : An object which will store the elements as value and count as key. Items object key will be incremental count property and value as the element store in it.

class Stack {
    constructor() {
        this.count = 0;
        this.items = {};
    }
}

Enter fullscreen mode Exit fullscreen mode

Push

To add an element to the stack we will use the count property as key for the items object & element as values. After pushing the element in the stack we will increment the count property by one.we can only add new items to the top of the stack, meaning at the end of the stack.


 push(element) {
        this.items[this.count] = element;
        this.count++;
    }

Enter fullscreen mode Exit fullscreen mode

Pop

While removing an element from the stack, there two cases:

  1. If the stack is empty, return undefined
  2. If the stack is not empty
    • Store the value of the top element i.e (count -1)
    • decrement the count property by one
    • delete element from items object and return the stored value.

As the stack uses the LIFO principle, the last item that we added is the one that is removed


   pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        let result = this.items[this.count-1];
        this.count --;
        delete this.items[this.count];

        return result;
    }
Enter fullscreen mode Exit fullscreen mode

Peek

If the stack is empty, return undefined else return the Topelement i.e (count -1)


  peek() {

        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count-1];
    }
Enter fullscreen mode Exit fullscreen mode

Size

Return count property, which keeps track of the number of elements in the stack.


size() {
        return this.count;
    }
Enter fullscreen mode Exit fullscreen mode

isEmpty & Clear

isEmpty return boolean value, if the count property is zero then true else false. And to clear the stack, we can simply reset it to the same values we used in the constructor.


 isEmpty() {
        return this.count == 0;
    }

 clear() {
    this.items = {};
    this.count = 0;
    return this.items;
    }
Enter fullscreen mode Exit fullscreen mode

We could also use the following logic to remove all elements from the stack,
respecting the LIFO behavior:

while (!this.isEmpty()) {
this.pop();
}
Enter fullscreen mode Exit fullscreen mode

you can get the full source here

Conclusion :

A stack is a data structure that uses the LIFO (Last In First Out ) principle. We can insert or remove an element from the top of the stack only

Stacks have a variety of applications in real-world problems. They can be used for backtracking problems to remember tasks or paths visited, and to undo actions.

Methods Complexity
pop O(1)
push O(1)
peek O(1)

So, stay tuned for the next blog, in which I will cover another DS Queue.

Top comments (0)

In defense of the modern web

I expect I'll annoy everyone with this post: the anti-JavaScript crusaders, justly aghast at how much of the stuff we slather onto modern websites; the people arguing the web is a broken platform for interactive applications anyway and we should start over;

React users; the old guard with their artisanal JS and hand authored HTML; and Tom MacWright, someone I've admired from afar since I first became aware of his work on Mapbox many years ago. But I guess that's the price of having opinions.