Stack and queue in typescript

JavaScript, Data Structure | Fri Aug 16 2024 | 3 min read

A queue is a linear data structure that stores the elements sequentially. It uses FIFO, First and First Out approach.
Where as, Stack follows LIFO, Last in First Out approach that is allows insertion and deletion operations from one end of the stack, that is top.

Stacks in JavaScript are basically just arrays, and that the only big difference between a stack and a queue is the order in which we remove elements.
In queue, elements are inserted or removed from two different ends.

Operation	Description	Big O
push(value)	adds an element to the collection	O(1)
pop()	removes the most recently added element	O(1)
peek()	returns the most recently added element without modifying the stack	O(1)
clear()	removes all the element in the stack	O(1)
isEmpty	checks if the stack is empty	O(1)
size	checks the size of the stack	O(1)
shift()	removes the first element from an array and returns that removed element.	O(n)
unshift()	adds new elements to the beginning of an array.	O(n)

Stack

typescript

interface IStack<T> {
  push(item: T): void;
  pop(): T | undefined;
  peek(): T | undefined;
  size(): number;
}

export class StackOn<T> implements IStack<T> {
  private stack: T[] = [];
  constructor(private capacity: number = Infinity) {}

  push(item: T): void {
    if (this.size() === this.capacity) {
      throw Error("Max capacity reached for the stack.");
    }
    this.stack.push(item);
  }
  pop(): T | undefined {
    return this.stack.pop();
  }
  peek(): T | undefined {
    return this.stack[this.size() - 1];
  }
  display(): T[] {
    return [...this.stack]
  }
  size(): number {
    return this.stack.length;
  }
}

const stackObj = new StackOn<number>();
stackObj.push(1);
stackObj.push(2);
stackObj.push(3);
console.log("Display stack elements", stackObj.display());
console.log("Stack size", stackObj.size());
stackObj.pop();
console.log("Display stack elements", stackObj.display());
console.log("Stack size",stackObj.size());

//Output
Display stack elements [ 1, 2, 3 ]
Stack size 3
Display stack elements [ 1, 2 ]
Stack size 2

Queue

typescript

export interface IQueue<T> {
  enqueue(item: T): void;
  dequeue(): T | undefined;
  size(): number;
}
class Queue<T> implements IQueue<T> {
  private queue: T[] = [];
  constructor(private capacity: number = Infinity) {}

  enqueue(item: T): void {
    if (this.size() === this.capacity) {
      throw Error("Max capacity reached for the queue.");
    }
    this.queue.push(item);
  }
  dequeue(): T | undefined {
    return this.queue.shift();
  }
  display(): T[] {
    return [...this.queue]
  }
  size(): number {
    return this.queue.length;
  }
}
const queueObj = new Queue<number>();
queueObj.enqueue(1);
queueObj.enqueue(2);
queueObj.enqueue(3);
console.log("Display queue elements ", queueObj.display());
console.log("Queue size ", queueObj.size());
queueObj.dequeue();
console.log("Display queue elements ",queueObj.display());
console.log("Queue size ",queueObj.size());

// Output
Display queue elements  [ 1, 2, 3 ]
Queue size  3
Display queue elements  [ 2, 3 ]
Queue size  2

It’s a fairly common interview question to implement a queue using a stack.

typescript

import { IQueue } from "./QueueOn";
import { StackOn } from "../Stack/Stack0n";

class QueueWithStack<T> implements IQueue<T> {
    private queue: T[] = [];
    private stack1: StackOn<T>;
    private stack2: StackOn<T>;
    constructor(private capacity: number = Infinity) {
        this.stack1 = new StackOn<T>();
        this.stack2 = new StackOn<T>();
    }
    enqueue(item: T): void {
        for(let i=0; i< this.stack2.size(); i++){
            this.stack1.push(this.stack2.pop()!);
        }
        this.stack1.push(item);
    }
    dequeue(): T | undefined {
        while(this.stack1.size() > 0){
            this.stack2.push(this.stack1.pop()!);
        }
        return this.stack2.pop();
    }
    display(): T[] {
        return this.stack2.display();
      }
    size(): number {
        return this.stack1.size();
    }

}

const queueObj = new QueueWithStack<number>();
queueObj.enqueue(1);
queueObj.enqueue(2);
queueObj.enqueue(3);
console.log("Display queue elements ", queueObj.display());
//console.log(queueObj.size());
queueObj.dequeue();
queueObj.dequeue();
console.log("Display queue elements ", queueObj.display());
//console.log(queueObj.size());

//Output

Display stack elements [ 1, 2, 3 ]
Display queue elements  [ 3 ]