🚀 Supercharge Your Career — Explore Preparation tools like Free AI Mock Interviews, Job Tracker, Resume & Cover Letter Builder, and much more!
Data Structure and Algorithm
Data Structure
Stack
Stack

Stack Data Structure in JavaScript

1 What is a Stack?

A Stack is a linear data structure that follows a particular order in which the operations are performed.

LIFO (Last In First Out): This strategy states that the element that is inserted last will come out first. You can take a pile of plates kept on top of each other as a real-life example. The plate which we put last is on the top and since we remove the plate that is at the top, we can say that the plate that was put last comes out first.

2 Basic Operations on Stack

In order to make manipulations in a stack, there are certain operations provided to us:

  • push() to insert an element into the stack
  • pop() to remove an element from the stack
  • top() Returns the top element of the stack.
  • isEmpty() returns true if stack is empty else false.
  • size() returns the size of stack.

Push

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

Algorithm for push:

begin
  if stack is full
    return
  endif
  else
    increment top
    stack[top] assign value
  end else
end procedure

Pop

Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

Algorithm for pop:

begin
  if stack is empty
    return
  endif
  else
    store value of stack[top]
    decrement top
    return value
  end else
end procedure

Top

Returns the top element of the stack.

Algorithm for Top:

begin
  return stack[top]
end procedure

IsEmpty

Returns true if the stack is empty, else false.

Algorithm for isEmpty:

begin
  if top < 1
    return true
  else
    return false
end procedure

Understanding stack practically:

There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow the LIFO/FILO order.

3 Complexity Analysis

OperationsComplexity
push()O(1)
pop()O(1)
isEmpty()O(1)
size()O(1)

4 Types of Stacks

  • Register Stack: This type of stack is also a memory element present in the memory unit and can handle a small amount of data only. The height of the register stack is always limited as the size of the register stack is very small compared to the memory.
  • Memory Stack: This type of stack can handle a large amount of memory data. The height of the memory stack is flexible as it occupies a large amount of memory data.

5 Array Implementation of Stack

Below is the implementation of Stack using Array. For that we basically need to design our own stack class and include stack functionalities like push, pop, peek etc.

class MyStack {
  constructor(c) {
    this.cap = c;
    this.arr = [];
    this.top = -1;
  }
  
  push(x) {
    if (this.top === this.cap - 1) {
      console.log("Stack is full");
      return;
    }
    this.top++;
    this.arr[this.top] = x;
  }
  
  pop() {
    if (this.top === -1) {
      console.log("Stack is Empty");
      return -1e9;
    }
    let res = this.arr[this.top];
    this.top--;
    return res;
  }
  
  peek() {
    if (this.top === -1) {
      console.log("Stack is Empty");
      return -1e9;
    }
    return this.arr[this.top];
  }
  
  size() {
    return this.top + 1;
  }
  
  isEmpty() {
    return this.top === -1;
  }
}
 
// Example usage
let s = new MyStack(5);
s.push(10);
s.push(20);
console.log(s.pop()); // 20
console.log(s.peek()); // 10

Advantages of array implementation:

  • Easy to implement.
  • Memory is saved as pointers are not involved.

Disadvantages of array implementation:

  • It is not dynamic.
  • It doesn't grow and shrink depending on needs at runtime. (Note: We can implement dynamic size stack by using Vector in C++ and ArrayList in Java. In JavaScript, arrays are natively dynamic!)

6 Applications of Stack

Application of Stack Data Structure:

  • Stack is used for evaluating expression with operands and operations.
  • Matching tags in HTML and XML
  • Undo function in any text editor.
  • Infix to Postfix conversion.
  • Stacks are used for backtracking and parenthesis matching.
  • Stacks are used for conversion of one arithmetic notation to another arithmetic notation.
  • Stacks are useful for function calls, storing the activation records and deleting them after returning from the function. It is very useful in processing the function calls.
  • Stacks help in reversing any set of data or strings.
  • To manage recursion, stack data structure is used to account for the previous state of the recursion call.

Application of Stack in real life:

  • CD/DVD stand.
  • Stack of books in a book shop.
  • Undo and Redo mechanism in text editors.
  • The history of a web browser is stored in the form of a stack.
  • Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.
  • YouTube downloads and Notifications are also shown in LIFO format (the latest appears first).

Advantages of Stack:

  • Stack helps in managing data that follows the LIFO technique.
  • Stacks are being used for systematic Memory Management.
  • It is used in many virtual machines like JVM.
  • When a function is called, the local variables and other function parameters are stored in the stack and automatically destroyed once returned from the function. Hence, efficient function management.
  • Stacks are more secure and reliable as they do not get corrupted easily.
  • Stack allows control over memory allocation and deallocation.
  • Stack cleans up the objects automatically.
  • Stacks are used to convert infix expressions to postfix or prefix expressions. This is especially useful in parsing expressions in compilers, where the stack helps manage the order of operations and parentheses, enabling efficient evaluation of expressions.

7 Interview Problem: Balanced Parenthesis

Given an expression string exp, write a program to examine whether the pairs and the orders of "{", "}", "(", ")", "[", "]" are correct in the given expression.

Example:

  • Input: exp = "[()]{}{[()()]()}" Output: Balanced Explanation: all the brackets are well-formed
  • Input: exp = "[(])" Output: Not Balanced Explanation: 1 and 4 brackets are not balanced because there is a closing ']' before the closing ')'

Check for Balanced Bracket expression using Stack:

The idea is to put all the opening brackets in the stack. Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration, in the end if the stack is empty, it means all brackets are well-formed. Otherwise, they are not balanced.

Algorithm:

  • Declare a character stack (say temp).
  • Now traverse the string exp.
    • If the current character is a starting bracket ('(' or '{' or '[') then push it to stack.
    • If the current character is a closing bracket (')' or '}' or ']') then pop from stack and if the popped character is the matching starting bracket then fine.
    • Else brackets are Not Balanced.
  • After complete traversal, if there is some starting bracket left in stack then Not balanced, else Balanced.
class MyStack {
  constructor(c) {
    this.cap = c;
    this.arr = [];
    this.top = -1;
  }
  
  push(x) {
    if (this.top === this.cap - 1) { return; }
    this.top++;
    this.arr[this.top] = x;
  }
  
  pop() {
    if (this.top === -1) { return null; }
    let res = this.arr[this.top];
    this.top--;
    return res;
  }
  
  isEmpty() {
    return this.top === -1;
  }
}
 
function isBalanced(exp) {
  let stack = new MyStack(exp.length);
  
  for (let i = 0; i < exp.length; i++) {
    let char = exp[i];
    
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else {
      if (stack.isEmpty()) return "Not Balanced";
      
      let topChar = stack.pop();
      if (
        (char === ')' && topChar !== '(') ||
        (char === '}' && topChar !== '{') ||
        (char === ']' && topChar !== '[')
      ) {
        return "Not Balanced";
      }
    }
  }
  
  return stack.isEmpty() ? "Balanced" : "Not Balanced";
}
 
// Output
console.log(isBalanced("[()]{}{[()()]()}")); // Balanced

Time Complexity: O(N), Iteration over the string of size N one time. Auxiliary Space: O(N) for stack.

Circular Linked ListQueue