Javascript: Data Structures - Stack

Javascript: Data Structures - Stack

Implementing a stack in Javascript.

First Things First...

Before we go into building them we should understand what stacks are. "Stack" is a term used to describe a specific type of data structure in which the last element to enter the stack is the first one to leave it. A simple conceptualization of this concept is to imagine a stack of books on a desk.

stack of books.jpg

If you wanted to take a book from this stack you would have to lift books off the top until you get to the desired book (assuming you aren't allowed to take them from the sides). And if you wanted to add books to this stack you would have to place one on top. Stacks in data structures also work in the same way.

Stacks in data structures have a limited bottom, meaning no operation can be performed at the bottom of the stack. All operations on a stack are to be performed at the top. The two basic operations are known as "push" and "pop", but we will also look at "peek" and "isEmpty".

Right into the Code

Alright, now that we have a basic understanding of what stacks are let's get into how we can implement them in Javascript. We will be looking at two ways to implement a stack.

  • Using arrays & built in functions

  • Using Classes to build our own stack class

Implementing a Stack Using Arrays & Built in Functions

If you have the basic understanding of arrays this will be a simple concept to understand and code. The idea here is to initialize an array and use built in functions on that array to create a stack.

let stack = [1,2,3,4,5];

Once the array has been initialized we can use the built in functions "arrayname.push()" and "arrayname.pop()" to either push an element into the stack or pop the top element.

stack.push(6);
console.log(stack);
stack.push(7);
console.log(stack);
stack.pop();
console.log(stack);

This code would display

[1,2,3,4,5,6]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6]

Apart from the push and pop operations we can also easily implement the peek and isEmpty operations on an array.

return stack[stack.length -1];

The code above would return the value of the last element on the stack acting as the peek operation.

if(!stack.length){
  return true;
}else{
  return false;
}

The code above would return a Boolean value of true or false based on whether the stack is empty or has elements in it.

That was easy, now let's look at how we can do that with classes.

Implementing a Stack Using Classes

The idea here is pretty much the same. The only difference is we are going to be implementing the stack using a class and creating an object whenever we need a new stack. We must first create a class, and then customize the initialization in the constructor.

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

This will create an array every time the Stack object is initialized. Now we can go on to create the functions for the basic operations.

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

    push(elem){
        this.stack.push(elem);
    }
}

The push function now pushes whatever is passed into it into the "stack" array that is created whenever a new Stack object is created.

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

    push(elem){
        this.stack.push(elem);
    }

    pop(){
        if(!this.stack.length){
            return null;
        } else{
            return this.stack.pop();
        }
    }
}

This simple pop function uses an if statement to find out if the stack is empty or not. If the stack is empty it returns "null" and if it is not empty it returns the top most element.

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

    push(elem){
        this.stack.push(elem);
    }

    pop(){
        if(!this.stack.length){
            return null;
        } else{
            return this.stack.pop();
        }
    }

    peek(){
        if(!this.stack.length){
            return null;
        } else{
            return this.stack[this.stack.length - 1];
        }      
    }
}

A peek function to get the value of the top most element in the stack. Like the previous pop function this function checks if the stack is empty or not. If it is empty the peek function also returns null since there is no value to return. If it is not empty it returns the value of the top most element without removing it from the stack.

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

    push(elem){
        this.stack.push(elem);
    }

    pop(){
        if(!this.stack.length){
            return null;
        } else{
            return this.stack.pop();
        }
    }

    peek(){
        if(!this.stack.length){
            return null;
        } else{
            return this.stack[this.stack.length - 1];
        }      
    }

    isEmpty(){
        if(!this.stack.length){
            return true;
        } else{
            return false;
        }
    }
}

Last but not least we add in an isEmpty function to check whether a given stack object is empty or not. This function returns true when the stack is empty and false when the stack is not empty.

Now all that is left to do is initialize an object and perform the operations on it.

let stk = new Stack;

console.log(stk.isEmpty()); //true

stk.push(21); //pushes 21
console.log(stack); //[21]

stk.push(22);//pushes 22
console.log(stack); //[21, 22]

stk.push(23);//pushes 23
console.log(stack); //[21, 22, 23]

stk.pop();//pops 23
console.log(stack); //[21, 22]

console.log(stk.peek()); // 22
console.log(stk.isEmpty()); //false

Well done! Now you know how to implement a stack using Javascript arrays and Javascript classes.

Did you find this article valuable?

Support Nail the Code by becoming a sponsor. Any amount is appreciated!