Data Structures Implementation in JavaScript or TypeScript

/**
 * Stack Class Definition:
 * - Initialize an empty array to store items and a variable to track size.
 * - Push: Add an element to the front of the array and increment size.
 * - Pop: Remove the first element if the stack is not empty and decrement size.
 * - isEmpty: Check if the size is zero to determine if the stack is empty.
 * - getSize: Return the current size of the stack.
 * - Peek: Return the first element if the stack is not empty.
 * - Clear: Reset the array and size if the stack is not empty.
 * - Contains: Check if the stack includes a specific value.
 * - ToString: Return a string representation of the stack.
 * - Clone: Perform a shallow clone of the stack's items.
 */

class Stack<T> {
  private size: number;
  private items: T[];

  constructor() {
    this.size = 0;
    this.items = [];
  }

  push(value: T): void {
    this.items.push(value);
    this.size++;
  }

  pop(): void {
    if (this.isEmpty()) {
      throw new Error("Stack underflow: cannot pop from an empty stack");
    }
    this.items.pop();
    this.size--;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }

  getSize(): number {
    return this.size;
  }

  peek(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  clear(): void {
    if (this.isEmpty()) {
      throw new Error("Stack empty: Can not clear empty stack");
    }
    this.items = [];
    this.size = 0;
  }

  contains(value: T): boolean {
    if (this.isEmpty()) {
      return false;
    }
    return this.items.includes(value);
  }

  toString(): string {
    return JSON.stringify(this.items);
  }

  clone(): T[] {
    return [...this.items]; // shallow cloning
  }
}

const stack = new Stack<number>(); // Generic type in this case it is number type

stack.push(1);
stack.push(2);
console.log("Stack Size:", stack.getSize());
console.log("Stack Peek:", stack.peek());
console.log("Stack Contains 2:", stack.contains(2));
console.log("Stack Contents:", stack.toString());

stack.pop();
console.log("Stack Size after Pop:", stack.getSize());
console.log("Is Stack Empty:", stack.isEmpty());

stack.clear();
console.log("Stack Size after Clear:", stack.getSize());

/**
 * Queue Class Definition:
 * - Initialize an empty array to store items and a variable to track size.
 * - Enqueue: Add an element to the end of the array and increment size.
 * - Dequeue: Remove the first element if the queue is not empty and decrement size.
 * - isEmpty: Check if the size is zero to determine if the queue is empty.
 * - getSize: Return the current size of the queue.
 * - Peek: Return the first element if the queue is not empty.
 */

class Queue<T> {
  private items: T[];
  private size: number;

  constructor() {
    this.items = [];
    this.size = 0;
  }

  enqueue(value: T): void {
    this.items.push(value);
    this.size++;
  }

  dequeue(): void {
    if (this.isEmpty()) {
      throw new Error("Dequeue operation on an empty queue");
    }
    this.items.shift();
    this.size--;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }

  getSize(): number {
    return this.size;
  }

  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[0];
  }
}

const queue = new Queue<number>(); // Generic type in this case it is number type

queue.enqueue(1);
queue.enqueue(2);
console.log("Front of the queue:", queue.peek());
console.log("Queue size:", queue.getSize());

queue.dequeue();
console.log("Front of the queue after dequeue:", queue.peek());
console.log("Is the queue empty?", queue.isEmpty());

/**
 * Priority Queue Class Definition:
 * - Initialize an empty array to store items as priority-value pairs and a variable to track size.
 * - Enqueue: Add an element with a priority, maintaining order based on priorities.
 * - Dequeue: Remove the element with the highest priority if the queue is not empty and decrement size.
 * - isEmpty: Check if the size is zero to determine if the priority queue is empty.
 * - getSize: Return the current size of the priority queue.
 * - Peek: Return the element with the highest priority without removal if the priority queue is not empty.
 */

type PriorityQueueItem<T> = [number, T];

class PriorityQueue<T> {
  private items: PriorityQueueItem<T>[];
  private size: number;

  constructor() {
    this.items = [];
    this.size = 0;
  }

  enqueue(item: PriorityQueueItem<T>) {
    if (this.isEmpty()) {
      this.items.push(item);
    } else {
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        if (item[0] < this.items[i][0]) {
          this.items.splice(i, 0, item);
          added = true;
          break;
        }
      }
      if (!added) {
        this.items.push(item);
      }
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Dequeue operation on an empty queue");
    }
    this.items.shift();
    this.size--;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[0][1];
  }
}

const priorityQueue = new PriorityQueue<string>(); // Generic type in this case it is string type

priorityQueue.enqueue([1, "Ramu"]);
priorityQueue.enqueue([2, "Kumar"]);
console.log("Front of the priorityQueue:", priorityQueue.peek());
console.log("Queue size:", priorityQueue.getSize());

priorityQueue.dequeue();
console.log("Front of the priorityQueue after dequeue:", priorityQueue.peek());
console.log("Is the priorityQueue empty?", priorityQueue.isEmpty());

/**
 * LNode Class Definition:
 * - Represents a node with a value and a reference to the next node.
 *
 * LinkedList Class Definition:
 * - Initialize the head as null.
 * - Push: Add a new node with the given value to the end of the list.
 * - Pop: Remove and return the value of the last node in the list.
 * - ToArray: Convert the linked list to an array.
 * - Delete: Remove the first occurrence of a node with the given value.
 * - Print: Output the values of all nodes in the list.
 * - Find: Check if a node with the given value exists in the list.
 * - Reverse: Reverse the order of nodes in the list.
 * - Size: Return the number of nodes in the list.
 */

class LNode<T> {
  value: T;
  next: LNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList<T> {
  head: LNode<T> | null;

  constructor() {
    this.head = null;
  }

  push(value: T): void {
    const newLNode = new LNode(value);
    if (!this.head) {
      this.head = newLNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newLNode;
    }
  }

  pop(): T | null {
    let current = this.head;
    let prev: LNode<T> | null = null;

    if (!current) {
      return null;
    }

    while (current.next) {
      prev = current;
      current = current.next;
    }

    if (!prev) {
      this.head = null;
    } else {
      prev.next = null;
    }

    return current.value;
  }

  toArray(): T[] {
    let current = this.head;
    const result: T[] = [];

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  delete(value: T): T | null {
    let current = this.head;
    let prev: LNode<T> | null = null;

    while (current && current.value !== value) {
      prev = current;
      current = current.next;
    }

    if (current) {
      if (!prev) {
        this.head = current.next;
      } else {
        prev.next = current.next;
      }

      return current.value;
    }

    return null;
  }

  print(): void {
    let current = this.head;

    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }

  find(value: T): boolean {
    let current = this.head;

    while (current) {
      if (current.value === value) {
        return true;
      }
      current = current.next;
    }

    return false;
  }

  reverse(): void {
    let current = this.head;
    let prev: LNode<T> | null = null;

    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    this.head = prev;
  }

  size(): number {
    let count = 0;
    let current = this.head;

    while (current) {
      count++;
      current = current.next;
    }

    return count;
  }
}

const linkedList = new LinkedList<number>();

linkedList.push(1);
linkedList.push(2);
linkedList.push(3);

console.log("Original Linked List:");
linkedList.print();

const poppedValue = linkedList.pop();
console.log(`Popped Value: ${poppedValue}`);

console.log("\nLinked List After Pop:");
linkedList.print();

const arrayRepresentation = linkedList.toArray();
console.log("\nArray Representation of Linked List:", arrayRepresentation);

/**
 * TreeNode Class Definition:
 * - Define a class for tree nodes with left, right, and value properties.
 *
 * BinarySearchTree Class Definition:
 * - Initialize the tree with a null root.
 * - Insert: Add a new node with the given value while maintaining the BST property.
 * - Find: Search for a node with the given value and return the value if found, else -1.
 * - GetMin: Find and return the minimum value in the BST.
 * - GetMax: Find and return the maximum value in the BST.
 * - Remove: Remove a node with the given value while maintaining the BST property.
 * - BreadthFirstSearch: Traverse the tree in breadth-first order and return an array of values.
 * - DepthFirstSearchPreOrder: Traverse the tree in pre-order and return an array of values.
 * - DepthFirstSearchInOrder: Traverse the tree in in-order and return an array of values.
 * - DepthFirstSearchPostOrder: Traverse the tree in post-order and return an array of values.
 */

class TreeNode<T> {
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  value: T;

  constructor(value: T) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree<T> {
  root: TreeNode<T> | null;

  constructor() {
    this.root = null;
  }

  insert(value: T): BinarySearchTree<T> | undefined {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let current: TreeNode<T> | null = this.root;

    while (true) {
      if (value === current.value) return undefined;
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  find(value: T): T | -1 {
    let current: TreeNode<T> | null = this.root;
    if (!current) return -1;

    while (current) {
      if (value === current.value) return current.value;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return -1;
  }

  getMin(): T | undefined {
    let current: TreeNode<T> | null = this.root;

    while (current?.left) {
      current = current.left;
    }
    return current?.value;
  }

  getMax(): T | undefined {
    let current: TreeNode<T> | null = this.root;

    while (current?.right) {
      current = current.right;
    }
    return current?.value;
  }

  remove(value: T): void {
    let current: TreeNode<T> | null = this.root;
    this.root = this.removeNode(current, value) as TreeNode<T>;
  }

  removeNode(node: TreeNode<T> | null, value: T): TreeNode<T> | null {
    if (!node) return null;

    if (value < node.value) {
      node.left = this.removeNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.removeNode(node.right, value);
    } else {
      if (!node.left) {
        return node.right;
      } else if (!node.right) {
        return node.left;
      }

      node.value = this.getMinValue(node.right) as T;

      node.right = this.removeNode(node.right, node.value);
    }
    return node;
  }

  private getMinValue(node: TreeNode<T>): T | undefined {
    let current: TreeNode<T> = node;
    while (current.left) {
      current = current.left;
    }
    return current.value;
  }

  breadthFirstSearch(): T[] {
    const queue: TreeNode<T>[] = [];
    const visited: T[] = [];
    let current: TreeNode<T> | null = this.root;

    if (!current) return visited;

    queue.push(current);

    while (queue.length) {
      current = queue.shift() as TreeNode<T>;
      visited.push(current.value);

      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }
    return visited;
  }

  depthFirstSearchPreOrder(): T[] {
    const visited: T[] = [];
    this.traversePreOrder(this.root, visited);
    return visited;
  }

  private traversePreOrder(node: TreeNode<T> | null, visited: T[]): void {
    if (node) {
      visited.push(node.value);
      this.traversePreOrder(node.left, visited);
      this.traversePreOrder(node.right, visited);
    }
  }

  depthFirstSearchInOrder(): T[] {
    const visited: T[] = [];
    this.traverseInOrder(this.root, visited);
    return visited;
  }

  private traverseInOrder(node: TreeNode<T> | null, visited: T[]): void {
    if (node) {
      this.traverseInOrder(node.left, visited);
      visited.push(node.value);
      this.traverseInOrder(node.right, visited);
    }
  }

  depthFirstSearchPostOrder(): T[] {
    const visited: T[] = [];
    this.traversePostOrder(this.root, visited);
    return visited;
  }

  private traversePostOrder(node: TreeNode<T> | null, visited: T[]): void {
    if (node) {
      this.traversePostOrder(node.left, visited);
      this.traversePostOrder(node.right, visited);
      visited.push(node.value);
    }
  }
}

const tree = new BinarySearchTree<number>(); // Generic type in this case it is number type
tree.insert(5);
tree.insert(3);
tree.insert(1);
tree.insert(7);
tree.insert(2);

tree.breadthFirstSearch(); // [ 5, 3, 7, 1, 2 ]
tree.depthFirstSearchPreOrder(); // [ 5, 3, 1, 2, 7 ]
tree.depthFirstSearchInOrder(); // [ 1, 2, 3, 5, 7 ]
tree.depthFirstSearchPostOrder(); // [ 2, 1, 3, 7, 5 ]

tree.getMin(); // 1
tree.getMax(); // 7

// Tree representation
/*
            5
        3       7
    2
1
*/

/**
 * Graph Class Definition:
 * - Initialize an adjacency list using a Map to store vertices and their neighbors.
 * - Add Vertex: Add a new vertex to the graph.
 * - Add Edge: Connect two vertices by adding edges.
 * - Remove Vertex: Remove a vertex and its associated edges.
 * - Remove Edge: Remove an edge between two vertices.
 * - Get Vertices: Return an array of all vertices in the graph.
 * - Get Edges: Return an array of all edges in the graph.
 * - Has Vertex: Check if a vertex exists in the graph.
 * - Has Edge: Check if an edge exists between two vertices.
 * - Get Neighbors: Return an array of neighbors for a given vertex.
 * - Is Empty: Check if the graph is empty.
 * - Clear: Remove all vertices and edges from the graph.
 * - Size: Return the number of vertices in the graph.
 * - Depth-First Search: Traverse the graph using depth-first search.
 * - Breadth-First Search: Traverse the graph using breadth-first search.
 */

class Graph<T> {
  private adjacencyList: Map<T, Set<T>>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex: T): this {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, new Set());
    }
    return this;
  }

  addEdge(vertex1: T, vertex2: T): this {
    this.addVertex(vertex1).addVertex(vertex2);

    this.adjacencyList.get(vertex1)!.add(vertex2);
    this.adjacencyList.get(vertex2)!.add(vertex1);
    return this;
  }

  removeVertex(vertex: T): this {
    if (this.adjacencyList.has(vertex)) {
      for (const adjacentVertex of this.adjacencyList.get(vertex)!) {
        this.removeEdge(vertex, adjacentVertex);
      }
      this.adjacencyList.delete(vertex);
    }
    return this;
  }

  removeEdge(vertex1: T, vertex2: T): this {
    if (this.adjacencyList.has(vertex1) && this.adjacencyList.has(vertex2)) {
      this.adjacencyList.get(vertex1)!.delete(vertex2);
      this.adjacencyList.get(vertex2)!.delete(vertex1);
    }
    return this;
  }

  getVertices(): T[] {
    return [...this.adjacencyList.keys()];
  }

  getEdges(): [T, T][] {
    const edges: [T, T][] = [];
    for (const [vertex, neighbors] of this.adjacencyList) {
      for (const neighbor of neighbors) {
        edges.push([vertex, neighbor]);
      }
    }
    return edges;
  }

  hasVertex(vertex: T): boolean {
    return this.adjacencyList.has(vertex);
  }

  hasEdge(vertex1: T, vertex2: T): boolean {
    return (
      this.adjacencyList.has(vertex1) &&
      this.adjacencyList.get(vertex1)!.has(vertex2)
    );
  }

  getNeighbors(vertex: T): T[] {
    return [...this.adjacencyList.get(vertex)!];
  }

  isEmpty(): boolean {
    return this.adjacencyList.size === 0;
  }

  clear(): this {
    this.adjacencyList.clear();
    return this;
  }

  size(): number {
    return this.adjacencyList.size;
  }

  depthFirstSearch(startVertex: T, callback: (vertex: T) => void): this {
    const visited = new Set<T>();

    function traverse(vertex: T): void {
      visited.add(vertex);
      callback(vertex);

      for (const neighbor of this.adjacencyList.get(vertex)!) {
        if (!visited.has(neighbor)) {
          traverse.call(this, neighbor);
        }
      }
    }

    traverse.call(this, startVertex);
    return this;
  }

  breadthFirstSearch(startVertex: T, callback: (vertex: T) => void): this {
    const visited = new Set<T>();
    const queue: T[] = [startVertex];
    visited.add(startVertex);

    while (queue.length > 0) {
      const currentVertex = queue.shift()!;
      callback(currentVertex);

      for (const neighbor of this.adjacencyList.get(currentVertex)!) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return this;
  }
}

const graph = new Graph<string>(); // Generic type in this case it is number type

graph
  .addVertex("A")
  .addVertex("B")
  .addVertex("C")
  .addEdge("A", "B")
  .addEdge("B", "C")
  .depthFirstSearch("A", (vertex) => console.log(`Visited ${vertex} in DFS`))
  .breadthFirstSearch("A", (vertex) => console.log(`Visited ${vertex} in BFS`));