Queue

In a queue, elements are added at one end called the rear or tail, and removed from the other end called the front or head, following the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed.

Some important characteristics of a queue are:

It is a dynamic data structure, meaning that its size can change during program execution.

It has a fixed memory allocation, which means that its size is limited.

It supports two operations: enqueue (to add an element to the rear of the queue) and dequeue (to remove the front element from the queue).

It can be implemented using arrays or linked lists.

The main operations on a queue are:

enqueue(element): Add an element to the back of the queue.

dequeue(): Remove and return the element at the front of the queue.

front(): Return the element at the front of the queue without removing it.

empty(): Check if the queue is empty.

A queue data structure has many real-life applications. Here are a few examples:

Waiting Lines: Queues are often used to manage waiting lines, such as at a grocery store or amusement park. Customers are added to the end of the queue and served in a first-in, first-out (FIFO) order.

Printers: Printers use a queue to manage print jobs. When a user sends a print job, it gets added to the queue. The printer then processes the jobs in the order they were received.

Messaging: Messaging apps like WhatsApp and Facebook Messenger use queues to manage messages. When a user sends a message, it gets added to a queue and is delivered to the recipient in the order it was sent.

Traffic Management: Traffic lights use queues to manage traffic flow. The traffic on each side of the intersection is queued, and the traffic light switches between the queues to manage traffic flow.


#include <iostream>
using namespace std;

#define MAX_SIZE 100

class Queue {
private:
    int front;
    int rear;
    int arr[MAX_SIZE];
public:
    Queue() {
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return front == -1 && rear == -1;
    }

    bool isFull() {
        return rear == MAX_SIZE - 1;
    }

    void enqueue(int x) {
        if (isFull()) {
            cout << "Queue overflow!" << endl;
            return;
        }
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear++;
        }
        arr[rear] = x;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow!" << endl;
            return -1;
        }
        int item = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return item;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << endl; // 10
    cout << q.peek() << endl; // 20
    cout << q.dequeue() << endl; // 20
    cout << q.dequeue() << endl; // 30
    cout << q.dequeue() << endl; // Queue underflow!
    return 0;
}

This implementation uses an array of size MAX_SIZE to store the elements of the queue, and the variables front and rear to keep track of the indices of the front and rear elements, respectively. The functions isEmpty() and isFull() check if the queue is empty or full, respectively.

The enqueue() function adds an element to the rear of the queue, and the dequeue() function removes and returns the front element.

The peek() function returns the value of the front element without removing it from the queue. Finally, the main() function demonstrates the usage of the queue.

PRACTICE PROBLEMS :

Implement Stack using Queues

Stock span problem