Queue

A queue is a data structure that follows the principle of First In First Out (FIFO).

An example in real life is a literal queue or line of people waiting to make their order at Starbucks or McDonald's. Another example is in call center systems, in which customers are put on hold and are serviced in a queue order whenever a service representative is available.

Example Use Cases#

Just like in real life, the queue data structure is used whenever we need a collection in which the first item that was added will also be the first to get out, while the rest wait for their turn.

The most common use case is when a resource is shared by multiple "consumers" (CPU task scheduling, printer & disk queue, routers/switches in networks).

Queue Methods#

1. enqueue(item) - pushes an item to the end of the queue.
2. dequeue() - removes and returns the first item from the queue.
3. front() - returns the first item, without removing it from the queue.
4. size
5. isEmpty()

Queue Data Structure Implementation in TypeScript#

Just like the set data structure example, a queue can be implemented in TypeScript using an array. But again, the performance will have issues with an array implementation.

With an array implementation, you'll have a constant time complexity O(1) for access, but the rest of the methods such as shift, unshift, delete, etc. will have O(n).

So I will skip the array version for queue, and instead go straight to a linked list implementation.

You can refer to linked list to get an idea of how a linked list works, as well as the LinkedList class we'll use below.

interface IQueue<T> {
    enqueue(item: T): void;
    dequeue(): T | null;
    front(): T | null;
    isEmpty(): boolean;
    size: number;
}
class Queue<T> implements IQueue<T> {
    private items: LinkedList<T>;
    size: number;
    constructor() {
        this.items = new LinkedList<T>();
        this.size = 0;
    }
    enqueue(item: T): void {
        this.items.insertAt(item, this.size);
        this.size++;
    }
    dequeue(): T | null {
        const tail = this.items.getLast() as T;
        if (!!tail) {
            this.items.remove(tail);
            this.size--;
            return tail;
        }
        return null;
    }
    front(): T | null {
        return this.items.getFirst() as T;
    }
    isEmpty(): boolean {
        return this.size === 0;
    }
}

TODO Priority Queue Data Structure Implementation in TypeScript#

A priority queue extends the features of a basic queue, by supporting the concept of priorities.

When adding an item to a priortiy queue, you also define its priority in the queue. The higher the priority, the closer they are to the beginning of the queue.

If all items have the same priority value, then the priority queue will behave like a regular queue.