Typescript Data Structures: Stack and Queue

One of the most exciting things about Typescript is that it encourages developers to think in terms of "blueprints" rather than writing code straight away. In today's post, we will start talking about the data structures and their implementations in Typescript. We will begin by discussing stacks and queues as well as looking into some basics of abstract classes.

Table of content

1. Stack
2. Queue
3. Abstract Classes

Stack

A stack is an elementary data structure, that is often described as LIFO (last in first out). An item that was added the last is the first to be retrieved. Usually, stacks have the following methods:

1. push adds an item to the stack
2. pop returns the last added item and remove it from the stack
3. peek (optional) returns the last added item without removing it from the stack

Stack also has some properties:

1. storage represents all stacked items
2. capacity (optional) is a number of items a stack can fit

Let's define a generic interface for the Stack:

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

Typescript interfaces don't allow to define private properties, therefore storage and capacity are omitted in IStack interface.

Now as we have an interface in place we can implement it and create our Stack class.

class Stack<T> implements IStack<T> {
  private storage: T[] = [];

  constructor(private capacity: number = Infinity) {}

  push(item: T): void {
    if (this.size() === this.capacity) {
      throw Error("Stack has reached max capacity, you cannot add more items");
    }
    this.storage.push(item);
  }

  pop(): T | undefined {
    return this.storage.pop();
  }

  peek(): T | undefined {
    return this.storage[this.size() - 1];
  }

  size(): number {
    return this.storage.length;
  }
}

const stack = new Stack<string>();
stack.push("A");
stack.push("B");

stack.size(); // Output: 2
stack.peek(); // Output: "B"
stack.size(); // Output: 2
stack.pop();  // Output: "B"
stack.size(); // Output: 1

Two noticeable things are happening in that example:

1. Constructor assignment constructor(private capacity: number = Infinity) {} is a short-hand for assigning a property in the constructor.
2. Implementation of a generic interface by a class with a generic type. new Stack<string>() will implement an interface IStack<string>. Typed passed to the class will also be used in the interface.

Implementing an interface is a type-safe way to ensure that all required methods are available in the class.

Queue

Queues are very similar to the stacks, but they handle items FIFO (first in first out). Items will be retrieved from the queue in the same order as they were added. Queues have the following methods:

1. enqueue adds an item to the queue
2. dequeue retrieves an item from the queue
3. size returns the size of the queue

Let's start with an interface:

interface IQueue<T> {
  enqueue(item: T): void;
  dequeue(): T | undefined;
  size(): number;
}

Here is the implementation:

class Queue<T> implements IQueue<T> {
  private storage: T[] = [];

  constructor(private capacity: number = Infinity) {}

  enqueue(item: T): void {
    if (this.size() === this.capacity) {
      throw Error("Queue has reached max capacity, you cannot add more items");
    }
    this.storage.push(item);
  }
  dequeue(): T | undefined {
    return this.storage.shift();
  }
  size(): number {
    return this.storage.length;
  }
}

const queue = new Queue<string>();

queue.enqueue("A");
queue.enqueue("B");

queue.size();    // Output: 2
queue.dequeue(); // Output: "A"
queue.size();    // Output: 1

Abstract Classes

At this point, we can already notice some patterns. Both stacks and queues have storage and capacity properties as well as the size method.
Luckily in Typescript, we can use abstract classes. Abstract classes have a major difference from regular JS classes -- they cannot be directly instantiated. They can only be extended.

abstract class Collection<T> {
  protected storage: T[] = [];

  size(): number {
    return this.storage.length;
  }
  abstract isFull(): boolean;
}

1. protected property or method restricts its usage to the derived classes only.
2. abstract methods shall be implemented in the derived class and serve as a blueprint.

Now let's look at how Stack and Queue classes can be implemented with the help of the abstract Collection class.

Stack

class StackCollection<T> extends Collection<T> implements IStack<T> {
  constructor(private capacity: number = Infinity) {
    super();
  }

  push(item: T) {
    if (this.isFull()) {
      throw Error("Stack has reached max capacity, you cannot add more items");
    }
    // In the derived class, we can access protected properties of the abstract class
    this.storage.push(item);
  }

  pop(): T | undefined {
    return this.storage.pop();
  }

  peek(): T | undefined {
    return this.storage[this.size() - 1];
  }

  // Implementation of the abstract method
  isFull(): boolean {
    return this.capacity === this.size();
  }
}

Queue

class QueueCollection<T> extends Collection<T> implements IQueue<T> {
  constructor(private capacity: number = Infinity) {
    super();
  }
  enqueue(item: T): void {
    if (this.isFull()) {
      throw Error("Queue has reached max capacity, you cannot add more items");
    }
    // In the derived class, we can access protected properties of the abstract class
    this.storage.push(item);
  }
  dequeue(): T | undefined {
    return this.storage.shift();
  }

  // Implementation of the abstract method
  isFull(): boolean {
    return this.capacity === this.size();
  }
}

Today we talked about elementary data structures and their implementation in Typescript. If you want to learn something specific about Typescript or webdev in general, leave a comment and let's discuss it together.

If you liked my post, please spread a word and follow me on Twitter 🚀 for more exciting content about web development.