Part 1— Stack Data Structure in js

Introduction

Stack is a data structure that stores data in LIFO(Last In First Out) order i.e. last value inserted will be at the top and the first one to come out. It is one of the linear data structures i. e. data is stored in a particular order. Only the top item of a stack is accessible at a time. Imagine a stack of plates. In order to add or remove a plate from the stack, you will have to start from the top.

Operations

There are 2 primary operations in a Stack. Push operation and pop operation. We can add additional methods to check if the stack is empty, peek a value, print stack values, etc.

Implementation

We can simply create a stack with the Array Data structure. Array supports push and pop methods by default. In order to support additional methods, we will create a Stack Object with the methods we need. Our stack API will have the following methods:

push
pop
peek
isEmpty
search

Implementation goes as below:

function Stack(){
   this.items = [];
}
Stack.prototype.isEmpty = function(){
   return this.items.length === 0;
}
Stack.prototype.push = function(item){
   this.items.push(item)
}
Stack.prototype.pop = function(){
   if(this.isEmpty){
      return "Empty Array";
   }
   return this.items.pop();
}
Stack.prototype.peek = function(){
   if(this.isEmpty){
      return "Empty Stack";
   }
   return this.items[this.items.length - 1]
}
Stack.prototype.search = function(item){
   if(this.isEmpty){
      return "Empty Stack";
   }
   for(let i = 0; i < this.items.length; i++){
      if(this.items[i] === item){
      return `item ${item} found at index ${i}`;
   }
   return "item ${item} not found in the stack"
}

Time Complexity

Access and Search Operation

In order to access an element in the stack, we have to keep removing elements until we find the one we are looking for. The worst-case is element is present at the bottom of stack.N movements are required. The best case is element is present at the top hence 1 movement is required. The average case is n/2 which can be represented asymptotically as O(n);

Insert, delete and peek Operation

Insertion, deletion and peek can only be done from the top of the stack hence time complexity will be O(1).

Usage

Stacks are commonly used in lots of complex algorithms to reduce the complexity of the problems. Below is a list of some common problems which use the stack. I will recommend you to practice solutions of each of these problems to master stack and its applications.

1. Implement Stack using queue
2. The stock-span problem
3. UNDO functionality
4. Parentheses checker
5. Expression parsing

Conclusion

In this section, we got a good understanding of stack as an abstract data type, its implementation, and common applications. Before moving further, my recommendation would be to practice its implementation and related problems to get a good hold of it. In the next section, we will continue our exploration with other linear and non-linear data structures. Stay tuned!