Stack Data Structure

Part 1: How To Implement A Stack Using Arrays

Stack is a data structure that follows the Last-In/First-Out principle(popularly known as LIFO), meaning the most recently added element is the first to remove.

Stacked plates

List of Stack Operations

//Add an item in the stack
.push() 

//Remove an item from the end of the stack
// if the stack is empty, this method will return undefined
.pop() 

//Return the top element of the stack
.peek() or .top()

//Check to see if stack is empty. 
//Returns true if the stack is empty
.isEmpty()

//Check to see if the stack is full. 
// Used when you have placed a limit on the data
.isFull()

//Removes all the data from the stack
.clear()

Implement Stack Using Array

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

    // add an element 
    push(element){
      this.items.push(element)
    }

   // remove an element 
    pop(){
      return this.items.pop()
    }

    // return the number of elements
    size(){
      return this.items.length
    }

    // view the last element 
    peek(){
      return this.items[this.items.length - 1];
    }

    // deletes all elements
    clear(){
      this.items.length = 0;
      console.log("Stack is cleared")
    }

    // check to see if stack is empty
    isEmpty(){
      return this.items.length === 0;
    }
}

//create new instance of stack class
  let stack1 = new Stack()
  stack1.push(10)
  stack1.push(20)
  stack1.push(30)

Time Complexity:

Time Complexity

Space Complexity: O(N)

Applications of Stack Data Structure

Example 1: Reverse A String

const reverse = (string) =>{
    let stack = [];
    
    // push each element to stack as you iterate through string
    for(let i =0; i < string.length; i++){
      stack.push(string[i]);
    }

    //pop each element from the stack and store it into a variable
     let reversedString = '';
     while(stack.length > 0){
       reverseString += stack.pop();
     }
    return reversedString
}

//TIME COMPLEXITY: 0(N)
//SPACE COMPLEXITY: 0(N)

Example 2: Check Valid Parenthesis

//check to see if every open bracket in a string 
//has a corresponding closing bracket

//Process
    //create a hashMap that contains the different types of bracket
      // along with their corresponding closing bracket
    // define a stack and set it equal to an empty array
    // loop through each character of the given string
      // if the character matches any key in the hashMap
          // push its value to the empty stack
      // Else if the character matches the last element of the stack
          // check to make sure stack is not empty
          // remove the last element from the stack 
      // Else, return false
          // meaning the character doesn't match the element at the top of stack
    // Once you have looped through all the characters in the given string
        //return true if the length of the stack if equal to 0

const isValid = (s) => {

  const hashMap = {"(":")", 
                   "{": "}",
                   "[": "]"
                  }
  let stack =[];

  for( let char of s){
      if (hashMap[char]){
        //character is an open bracket
        stack.push(hashMap[char])
      } else if(stack.length > 0 && stack[stack.length - 1] === char){
        //character is a closing bracket and the top of the stack matches
        stack.pop()
      } else {
        //character is a closing brack and the top of the stack doesnt match
        return false
      }
  }
    //will return true if the length of the stack is equal to 0
    return stack.length === 0
}

//TIME COMPLEXITY: 0(N)
//SPACE COMPLEXITY: 0(N)

Check out Part 2: How To Implement A Stack Using Linked List

Citation

https://www.simplilearn.com/tutorials/data-structure-tutorial/stacks-in-data-structures#:~:text=The%20stack%20data%20structure%20is,of%20money%2C%20and%20many%20more.

How to implement a stack in vanilla JavaScript and ES6

Photo by Mick Haupt on Unsplash