Typescript Data Structures: Stack and Queue
Tags: typescript, javascript, tutorial, beginners
Published: 2020-07-13 17:54:51

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](#stack)
2. [Queue](#queue)
3. [Abstract Classes](#abstractClasses)

### <a name="stack"></a>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:
```typescript
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.
```typescript
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.

### <a name="queue"></a>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:
```typescript
interface IQueue<T> {
  enqueue(item: T): void;
  dequeue(): T | undefined;
  size(): number;
}
```
Here is the implementation:
```typescript
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
```

### <a name="abstractClasses"></a>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.
```typescript
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
```typescript
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
```typescript
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](https://twitter.com/gleb_irovich) 🚀 for more exciting content about web development.