Lecture 248:- Queue Adt

A Queue is an Abstract Data Type (ADT) that follows the First-In-First-Out (FIFO) principle. It means that the element that is added first will be the first one to be removed. Think of it like a line in a store, where the person who comes first will be the first one to be served.

The primary operations that can be performed on a Queue are:

1. enqueue(element): Adds an element to the end of the queue.
2. dequeue(): Removes and returns the element from the front of the queue.
3. front(): Returns the element at the front of the queue without removing it.
4. isEmpty(): Checks if the queue is empty.
5. size(): Returns the number of elements in the queue.

Queues can be implemented using arrays or linked lists. Here's an example of a simple Queue implementation using arrays in C++:

cppCopy code

#include <iostream> const int MAX_SIZE = 100; class Queue { private:    int arr[MAX_SIZE];    int frontIdx;    int rearIdx; public:    Queue() {        frontIdx = -1;        rearIdx = -1;    }    bool isEmpty() {        return (frontIdx == -1 && rearIdx == -1);    }    bool isFull() {        return (rearIdx + 1) % MAX_SIZE == frontIdx;    }    void enqueue(int element) {        if (isFull()) {            std::cout << "Queue is full. Cannot enqueue." << std::endl;            return;        }        if (isEmpty()) {            frontIdx = 0;        }        rearIdx = (rearIdx + 1) % MAX_SIZE;        arr[rearIdx] = element;    }    void dequeue() {        if (isEmpty()) {            std::cout << "Queue is empty. Cannot dequeue." << std::endl;            return;        }        if (frontIdx == rearIdx) {            frontIdx = -1;            rearIdx = -1;        } else {            frontIdx = (frontIdx + 1) % MAX_SIZE;        }    }    int front() {        if (isEmpty()) {            std::cout << "Queue is empty." << std::endl;            return -1; // Assuming -1 is not a valid element in the queue.        }        return arr[frontIdx];    }    int size() {        if (isEmpty()) {            return 0;        }        return (rearIdx >= frontIdx) ? (rearIdx - frontIdx + 1) : (MAX_SIZE - frontIdx + rearIdx + 1);    } }; int main() {    Queue queue;    queue.enqueue(10);    queue.enqueue(20);    queue.enqueue(30);    std::cout << "Front element: " << queue.front() << std::endl;    queue.dequeue();    std::cout << "Front element after dequeue: " << queue.front() << std::endl;    std::cout << "Queue size: " << queue.size() << std::endl;    return 0; }

This implementation of a Queue uses an array with a fixed maximum size (MAX_SIZE). It maintains frontIdx and rearIdx to keep track of the front and rear elements in the queue. The circular nature of the queue is handled using the modulo operator %.

The enqueue() function adds an element to the end of the queue, the dequeue() function removes the element from the front, and the front() function returns the front element without removing it. The isEmpty() and isFull() functions check if the queue is empty or full, respectively. The size() function returns the number of elements in the queue.

In the main function, we demonstrate how to use the Queue by enqueueing and dequeueing elements and checking the front element and queue size.