Implement Stack data structure in javascript

Learn what is stack data structure and how to implement it in javascript.

A stack is an ordered collection of items that follow (LIFO) Last In First Out principle. The addition and removal of items take place at same end i.e at the top. The newest elements are at the top and the oldest elements are at the bottom unlike in Queue.

We have many examples of stack around us like the pile of books, a stack of trays of dishes etc.

A Stack is used by compilers in programming languages, by computer memory to store variables and functions call, in text editors to perform undo & redo operations.

List of operations performed on Stack

• push(): Adds a single or multiple items to the top of the Stack.
• pop(): Removes and Returns the top item of the Stack.
• peek(): Returns the top item of the Stack.
• isEmpty(): Returns True if Stack is empty, False otherwise.
• clear(): Removes all the items of the Stack.
• size(): Returns the length of the stack.

Creating a Stack

A classical approach

  function Stack(){
    var items = [];
    var top = 0;
    //other methods go here
  }

Push an item in the Stack

  this.push = function(element){
    items[top++] = element
  }
  //top++, first performs the operation then increment's the value

Pop an item from the Stack

  this.pop = function(){
     return items[--top];
  }
  //--top, first decrements the value then performs the operation

Peek top item from the Stack

  this.peek = function(){
     return items[top - 1];
  }

Check if Stack is empty

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

Clear the Stack

  this.clear= function(){
     top = 0;
  }

Size of the Stack

  this.size = function(){
     return top;
  }

Complete implementation of Stack

 function Stack(){
   var items = [];
   var top = 0;
   //other methods go here

   //Push an item in the Stack
   this.push = function(element){
     items[top++] = element
   }
   //top++, first performs the operation then increment's the value     

   //Pop an item from the Stack
   this.pop = function(){
     return items[--top];
   }
   //--top, first decrements the value then performs the operation
     
   //Peek top item from the Stack
   this.peek = function(){
     return items[top - 1];
   }

   //Is Stack empty
   this.isEmpty = function(){
     return top === 0;
   }     

   //Clear the Stack
   this.clear = function(){
      top = 0;
   }
     
   //Size of the Stack
   this.size = function(){
     return top;
   }
 }

Using the Stack

 var stack = new Stack();   //creating new instance of Stack
 stack.push(1);
 stack.push(2);
 stack.push(3);
 console.log(stack.peek());
 console.log(stack.isEmpty());
 console.log(stack.size());
 console.log(stack.pop());
 console.log(stack.size());
 stack.clear();
 console.log(stack.isEmpty());

 Output:
 3
 false
 3
 3
 2
 true

---

Stack data structure in JavaScript with Array

 function Stack(){
   var items = [];
   //other methods go here
 }

Push an item in the Stack

 this.push = function(element){
   items.push(element)
 }

Pop an item from the Stack

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

Peek top item from the Stack

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

Check if Stack is empty

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

Clear the Stack

 this.clear = function(){
    items.length = 0;
 }

Size of the Stack

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

Complete implementation of Stack

 function Stack(){
   var items = [];
   //other methods go here

   //Push an item in the Stack
   this.push = function(element){
     items.push(element);
   }    

   //Pop an item from the Stack
   this.pop = function(){
     return items.pop();
   }
     
   //Peek top item from the Stack
   this.peek = function(){
     return items[items.length - 1];
   }

   //Is Stack empty
   this.isEmpty = function(){
     return items.length === 0;
   }     

   //Clear the Stack
   this.clear = function(){
      items.length = 0;
   }
     
   //Size of the Stack
   this.size = function(){
     return items.length;
   }
 }

---

Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).

 var Stack = (function () {
   return function Stack(){
   var items = [];
   var top = 0;
   //other methods go here
   //Push an item in the Stack
   this.push = function(element){
     items.push(element);
   }    

   //Pop an item from the Stack
   this.pop = function(){
     return items.pop();
   }
     
   //Peek top item from the Stack
   this.peek = function(){
     return items[items.length - 1];
   }

   //Is Stack empty
   this.isEmpty = function(){
     return items.length === 0;
   }     

   //Clear the Stack
   this.clear = function(){
      items.length = 0;
   }
     
   //Size of the Stack
   this.size = function(){
     return items.length;
   }
 }})();

---

Stack data structure using ES6.

class Stack{
  constructor(){
    this.items = [];
  }
  
   //other methods go here
   //Push an item in the Stack
   push = function(element){
     this.items.push(element);
   }    

   //Pop an item from the Stack
   pop = function(){
     return this.items.pop();
   }
     
   //Peek top item from the Stack
   peek = function(){
     return this.items[this.items.length - 1];
   }

   //Is Stack empty
   isEmpty = function(){
     return this.items.length === 0;
   }     

   //Clear the Stack
   clear = function(){
      this.items.length = 0;
   }
     
   //Size of the Stack
   size = function(){
     return this.items.length;
   }
}

---

Stack using ES6 WeakMap.

const items = new WeakMap();
class Stack{
  constructor(){
    items.set(this, []);
  }
  
   //other methods go here
   //Push an item in the Stack
   push = function(element){
     let temp = items.get(this);
     temp.push(element);
   }    

   //Pop an item from the Stack
   pop = function(){
     let temp = items.get(this);
     return temp.pop();
   }
     
   //Peek top item from the Stack
   peek = function(){
     let temp = items.get(this);
     return temp[temp.length - 1];
   }

   //Is Stack empty
   isEmpty = function(){
     let temp = items.get(this);
     return temp.length === 0;
   }     

   //Clear the Stack
   clear = function(){
      let temp = items.get(this);
      temp.length = 0;
   }
     
   //Size of the Stack
   size = function(){
     let temp = items.get(this);
     return temp.length;
   }
}

---

Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression) for Stack using ES6 WeakMap.

let Stack = (() => {
  const items = new WeakMap();
  return class Stack{
    constructor(){
      items.set(this, []);
    }

     //other methods go here
     //Push an item in the Stack
     push = function(element){
       let temp = items.get(this);
       temp.push(element);
     }    

     //Pop an item from the Stack
     pop = function(){
       let temp = items.get(this);
       return temp.pop();
     }

     //Peek top item from the Stack
     peek = function(){
       let temp = items.get(this);
       return temp[temp.length - 1];
     }

     //Is Stack empty
     isEmpty = function(){
       let temp = items.get(this);
       return temp.length === 0;
     }     

     //Clear the Stack
     clear = function(){
        let temp = items.get(this);
        temp.length = 0;
     }

     //Size of the Stack
     size = function(){
       let temp = items.get(this);
       return temp.length;
     }
  }
})();

Time Complexity

---

Space Complexity

There are lots of problems where Stack can be the perfect data structure needed for the solution.

• The base converter algorithm
• Balanced Parentheses