How to implement a stack in JavaScript

Stack

Stacks are data structures that follow the Last-In-First-Out (LIFO) principle, meaning that the last item inserted into a stack is the first one to be deleted.

In other words, a stack is a list of elements that are only accessible from one end of the list, called the Top of Stack (ToS).

A real-world example is a stack of plates. In the above image, we can see that the plate that is inserted last (put on top of the stack) is the first one to be taken off.

These are the stack operations that we are going to implement:

Push → Add an element to the stack.
Pop → Delete an element from the stack.
Peek → Get the top element of the stack.
Length → Return the length of the stack.
Search → Search for the element in the stack.
IsEmpty → Check if the stack is empty.
Print → Print the elements of the stack.

Let’s create a Stack class:

class Stack {
    constructor(){
        this.data = [];
        this.top = 0;
    }
}

The Stack class has two attributes:

data → An array in which we store the values.
top → Points to the top element index.

push(): Insert an element at the top of stack

When we push an element to the stack, we have to store it in the top data position and increment the top variable so that the top will point to the next empty place.

push(element) {
   this.data[this.top] = element;
   this.top = this.top + 1;
}

length(): Return the length of the stack

To get the length of the stack, we can return the top value.

length() {
   return this.top;
}

peek(): Get the top element of the stack

To peek at the top element of the stack, we can use the top-1 attribute of the stack class:

peek() {
   return this.data[this.top -1 ];
}

In the above code, we used top-1 because the top points to the position where the new element is to be inserted, therefore, it is the top empty location.

isEmpty(): Check if the stack is empty

If the value of the top=0, then there is no element in the stack.

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

pop(): Delete an element from the top of the stack

When we pop an element from the stack, we have to remove the element in the top position. Then, we decrement the top variable by 1 so that the top will point to the deleted element’s position.

pop() {
     this.top = this.top -1;
     return this.data.pop(); // removes the last element
}

In addition to the above code, we need to ensure that the stack is not empty. Otherwise, the value of the top will be decremented below zero.

pop() {
    if( this.isEmpty() === false ) {
       this.top = this.top -1;
       return this.data.pop(); // removes the last element
     }
}

print(): Print the elements of the stack

print() {
  var top = this.top - 1; // because top points to index where new element to be inserted
  while(top >= 0) { // print up to 0th index
    console.log(this.data[top]);
    top--;
  }
}

To print the stack in reverse order, we can use recursion:


reverse() {
   this._reverse(this.top - 1 );
}
_reverse(index) {
   if(index != 0) {
      this._reverse(index-1);
   }
   console.log(this.data[index]);
}

Let’s combine all of the code together:

class Stack {
    constructor(){
        this.data = [];
        this.top = 0;
    }
    push(element) {
      this.data[this.top] = element;
      this.top = this.top + 1;
    }
   length() {
      return this.top;
   }
   peek() {
      return this.data[this.top-1];
   }
   isEmpty() {
     return this.top === 0;
   }
   pop() {
    if( this.isEmpty() === false ) {
       this.top = this.top -1;
       return this.data.pop(); // removes the last element
     }
   }
   print() {
      var top = this.top - 1; // because top points to index where new    element to be inserted
      while(top >= 0) { // print upto 0th index
         console.log(this.data[top]);
         top--;
       }
    }
    reverse() {
       this._reverse(this.top - 1 );
    }
    _reverse(index) {
       if(index != 0) {
          this._reverse(index-1);
       }
       console.log(this.data[index]);
    }
}
console.log("Creating Stack");
let stack = new Stack();
console.log("\n-------\nStack isEmpty = ", stack.isEmpty());
console.log("Adding 1, 2, 3 to the stack");
stack.push(1);
stack.push(2);
stack.push(3);
console.log("\n-------\nStack isEmpty = ", stack.isEmpty());
console.log("\n-------\nStack Length = ", stack.length());
console.log("\n-------\nStack Peek Element = ", stack.peek());
console.log("\n-------\nStack Pop =", stack.pop());
console.log("\n-------\nStack Pop = ", stack.pop());
console.log("\n-------\nStack Pop =", stack.pop());
console.log("\n-------\nStack isEmpty = ", stack.isEmpty());

Free Resources

Attributions:

undefined by undefined

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)