TypeScript: Implement a Circular Queue using Arrays

1. Introduction

A Circular Queue is a linear data structure that follows the FIFO (First In First Out) principle but wraps around once the end is reached. Unlike a regular queue, in a circular queue, the position next to the last element is the first element. Implementing a Circular Queue with arrays can be efficient for data storage, as we can make use of the entire array's capacity.

2. Program Overview

Our TypeScript program will implement a basic Circular Queue with arrays. 

Key operations include enqueue (adding an item), dequeue (removing an item), and displaying the queue.

3. Code Program

class CircularQueue {
    private items: (number | null)[];
    private front: number;
    private rear: number;
    private capacity: number;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.items = Array(this.capacity).fill(null);
        this.front = -1;
        this.rear = -1;
    }

    // Add an item to the queue
    enqueue(item: number): void {
        if ((this.front === 0 && this.rear === this.capacity - 1) || (this.rear === (this.front - 1) % (this.capacity - 1))) {
            console.log('Queue is full');
            return;
        }

        if (this.front === -1) {
            this.front = this.rear = 0;
            this.items[this.rear] = item;
        } else if (this.rear === this.capacity - 1 && this.front !== 0) {
            this.rear = 0;
            this.items[this.rear] = item;
        } else {
            this.rear += 1;
            this.items[this.rear] = item;
        }
    }

    // Remove an item from the queue
    dequeue(): void {
        if (this.front === -1) {
            console.log('Queue is empty');
            return;
        }

        const item = this.items[this.front];
        this.items[this.front] = null;
        if (this.front === this.rear) {
            this.front = -1;
            this.rear = -1;
        } else if (this.front === this.capacity - 1) {
            this.front = 0;
        } else {
            this.front += 1;
        }
        console.log(`Removed element = ${item}`);
    }

    // Display the queue elements
    display(): void {
        if (this.front === -1) {
            console.log('Queue is empty');
            return;
        }

        if (this.rear >= this.front) {
            for (let i = this.front; i <= this.rear; i++) {
                console.log(this.items[i]);
            }
        } else {
            for (let i = this.front; i < this.capacity; i++) {
                console.log(this.items[i]);
            }

            for (let i = 0; i <= this.rear; i++) {
                console.log(this.items[i]);
            }
        }
    }
}

// Test the Circular Queue
const queue = new CircularQueue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.display();
queue.dequeue();
queue.display();
queue.enqueue(6);
queue.display();

4. Step By Step Explanation

1. We define a class CircularQueue to encapsulate the operations and properties of the circular queue.

2. The items array will hold the queue elements, while the front and rear pointers determine the start and end of the queue. The capacity property will indicate the maximum size of our queue.

3. In the enqueue method:

• We first check if the queue is full. If full, no item is added.
• If it's the first item, both front and rear pointers point to the first position.
• If the rear pointer has reached the end of the array, and there's space at the beginning, we wrap around.d. Otherwise, we simply increment the rear pointer and add the item.

4. In the dequeue method:

• If the queue is empty, there's nothing to dequeue.
• We remove the item at the front pointer.
• If there's only one item, we reset the pointers. If the front pointer is at the end, we wrap it around. Otherwise, we increment the front pointer.

5. The display method displays all the elements in the queue. Based on the position of the front and rear pointers, it may need to loop through part or all of the array, possibly wrapping from end to beginning.