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.

Comments

[Ajesh DS]

Great article and really helpful for someone like me who's starting out with TS. I had a question though, in Queues the enqueue and dequeue operations are supposed to be O(1)complexity right? So when we use this.storage.shift() , isn't that O(n) in worst case?

[Gleb Irovich]

Hey! Thanks for reading! Well spotted, I checked out the docs again and shift indeed has O(n) time complexity. Probably implementing a queue with an array was a bad idea. I need to revisit this topic 😅😅

[Ritik Jaiswal]

We can easily implement it with a doubly linked list and provide it head and tail.
in arrays it hard to implement the O(1) behaviour.

Having a dynamic array and just neglecting the start reference would do the trick but it does not actually delete the element it just makes you feet the element is deleted.

[Rafarel]

Hi Great article mate !

I think you forgot to specify the undefined return value in the IQueue dequeue signature to match the Array shift return value type.

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

[Gleb Irovich]

Hey Rafarel!

Thank you. Great catch with the missing undefined return type. I updated the post!

[Rafarel]

You are welcome Gleb!

I adapted the enqueue method because I had the need to replace some item in my queue when enqueued. So I added a replacement predicate function as an optional parameter I works great for my use case. It's like enqueue or update :)

/**
 * Enqueue an item.
 * If a replacement predicate is defined, item will replace another already enqueued if predicate match.
 * @param item
 * @param replacementPredicate
 */
enqueue(item: T, replacementPredicate?: (value: T) => boolean): void
{
    if (typeof replacementPredicate === "function")
    {
        for (let i = 0; i < this.storage.length; i++)
        {
            if (replacementPredicate(this.storage[i]))
            {
                //console.log("Replacement predicate match for", item)
                this.storage[i] = item
                return
            }
        }
    }

    if (this.size() === this.capacity) throw Error("Queue has reached max capacity, you cannot add more items")

    this.storage.push(item)
}

[Gleb Irovich]

well done. I need to mention, that one of the benefits of the queue is that insertion and deletion is very efficient - O(1). However when you add search-replace your enqueue method will become O(n).
Could you share your use-case?

[Rafarel]

Yes of course. It is a multiplayer game with rounds. Player can submit an action for every round and can update their played action if the opponent haven't submit it's choice of action or if an action is currently processed. Actions are processed server side asynchronously. When an action is processed for a given game the other actions are queued to be processed in order. So, if the player one submit his action, during the processing time of the first player action, other actions are enqueued. In the meantime, player two send an action, then changes his mind to another action, only the second action needs to be processed so I have to replace the first choice of the player two in the queue because it is for the same game & round, the first choice doesn't need to be processed anymore. i don't know if it is clear enough, I had hard times solving this problem :)

[Cole Bienek]

Thanks for this. I am a JS dev migrating to TS for a new job. This was a great place to start!