Queue

A queue is a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end.

The element which is first pushed into the order, the delete operation is first performed on that.

Implementation:

Using Linked List:

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.front = null; // Pointer to the front of the queue
        this.rear = null; // Pointer to the rear of the queue
        this.size = 0; // Number of elements in the queue
    }

    enqueue(element) {
        const newNode = new Node(element);
        if (this.isEmpty()) {
            this.front = newNode;
            this.rear = newNode;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
        }
        this.size++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Underflow";
        }
        const removedElement = this.front.data;
        if (this.front === this.rear) {
            // If there's only one element in the queue
            this.front = null;
            this.rear = null;
        } else {
            this.front = this.front.next;
        }
        this.size--;
        return removedElement;
    }

    frontElement() {
        if (this.isEmpty()) {
            return "No elements in Queue";
        }
        return this.front.data;
    }

    isEmpty() {
        return this.size === 0;
    }

    printQueue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        let current = this.front;
        let result = "";
        while (current !== null) {
            result += current.data + " ";
            current = current.next;
        }
        return result.trim();
    }
}

// Example usage:
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("Queue:", queue.printQueue()); // Output: Queue: 1 2 3
console.log("Front element:", queue.frontElement()); // Output: Front element: 1
console.log("Dequeued element:", queue.dequeue()); // Output: Dequeued element: 1
console.log("Queue after dequeue:", queue.printQueue()); // Output: Queue: 2 3

Using Arrays:

class Queue {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Underflow";
        }
        return this.items.shift();
    }

    front() {
        if (this.isEmpty()) {
            return "No elements in Queue";
        }
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    printQueue() {
        let str = "";
        for (let i = 0; i < this.items.length; i++) {
            str += this.items[i] + " ";
        }
        return str;
    }
}

// Example usage:
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("Queue:", queue.printQueue()); // Output: Queue: 1 2 3
console.log("Front element:", queue.front()); // Output: Front element: 1
console.log("Dequeued element:", queue.dequeue()); // Output: Dequeued element: 1
console.log("Queue after dequeue:", queue.printQueue()); // Output: Queue: 2 3

Types:

• Input Restricted Queue: This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends.

• Output Restricted Queue: This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.

• Circular Queue: This is a special type of queue where the last position is connected back to the first position. Here also the operations are performed in FIFO order.

• Double-Ended Queue (Dequeue): In a double-ended queue the insertion and deletion operations, both can be performed from both ends.

• Priority Queue: A priority queue is a special queue where the elements are accessed based on the priority assigned to them.

Queues Good at 😀:

• Fast Operations

• Fast Peek

• Ordered

Queues Bad at 😒:

• Slow Lookup

Both arrays and linked lists can be used to implement queues, and the choice between them depends on the specific requirements of your application. Here's a comparison:

1. Array-based Queue:

   • Pros:

     • Simple to implement.

     • Random access to elements by index.

     • Typically more memory-efficient than linked lists due to contiguous memory allocation.

   • Cons:

     • Insertion and deletion at the beginning of the array (enqueue and dequeue operations) can be inefficient because it requires shifting all elements.

     • Resizing the array can be expensive if it needs to grow/shrink frequently.

2. Linked List-based Queue:

   • Pros:

     • Efficient enqueue and dequeue operations, as they involve simple pointer manipulation at the beginning and end of the list.

     • Dynamic memory allocation, so no need to resize like arrays.

   • Cons:

     • Requires additional memory overhead for storing pointers/references.

     • No random access to elements, traversal is necessary to access elements at arbitrary positions.

Choosing Between Them:

• Use an array-based queue if:

  • You have a fixed-size queue or a reasonable upper bound on the queue size.

  • Random access to elements or memory efficiency is important.

  • You expect frequent accesses to elements by index.

• Use a linked list-based queue if:

  • You need dynamic resizing and don't want to worry about resizing arrays.

  • You have frequent insertions and deletions at both ends of the queue.

  • Memory overhead is not a concern or is justified by other factors.

In general, if you're working with small queues or have a fixed-size queue, an array-based implementation may suffice. However, for larger queues or scenarios with frequent insertions and deletions, a linked list-based implementation might be more efficient.