Stack

Table of contents

• Introduction
• Where is stack used
• List of operations on a stack
• Javascript implementaion of a stack using array
• Javascript implementaion of a stack using linked list
• Leetcode stack problems
• Time / Space Complexity (Worst case)

Introduction

Stack is a data structure which contains a linear sequence of elements. It is usually LIFO (Last in first out). Real life examples may be found all around you like a stack of books or a stack of plates. Learn how to implement a stack in javascript.

Cool fact: A stack overflow is a runtime error that occurs when a program runs out of memory in the call stack.

Where is stack used

• Infix to postfix conversion.
• Used to check for balanced parenthesis.
• Used for handling temporary data and function calls in an operating system.
• Undo / Redo operations in apps.
• Backward / Forwards navigation in browsers.

List of operations on a stack

• push( ) : Adds an element on the top of a stack.
• pop( ) : Removes an element from the top of a stack.
• peek( ) : Returns the top element from a stack.
• size( ) : Returns the number of elements in a stack.
• isEmpty( ) : Returns whether the stack is empty or not.

Javascript implementaion of a stack using array

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

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

  push(value) {
    this.items.push(value);
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

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

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

  toString() {
    return this.items.toString();
  }
}

Javascript implementaion of a stack using linked list

See linked list implementation here Linked List

import { LinkedList } from '@/LinkedList';

class Stack {
  constructor() {
    this.items = new LinkedList();
  }

  isEmpty() {
    return !this.items.head;
  }

  push(value) {
    this.items.prepend(value);
  }

  pop() {
    return this.items.deleteHead();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.head.value;
  }

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

  toArray() {
    return this.items.toArray();
  }

  toString() {
    return this.items.toString();
  }
}

Usage

const stack = new Stack();
stack.push(1);   
stack.push(2);   
stack.peek();    
stack.pop();     
stack.size();    
stack.isEmpty(); 

Leetcode stack problems

• 20. Valid Parentheses

Time / Space Complexity (Worst case)