What is Queue ?

Queue ek linear data structure hai jo FIFO (First In First Out) principle pe kaam karta hai.

Matlab jo element sabse pehle aata hai, wahi sabse pehle nikalta bhi hai, bilkul waise jaise ek line (queue) me log khade hote hain.

Real-life example:

Cinema ticket counter par jo pehle line me aaya, usko pehle ticket milega.

Queue ke Advantages

1. FIFO Logic

• Ye natural order follow karta hai, pehle aaya pehle gaya.
• Real-world scenarios ke liye best hota hai jaise printers, task scheduling .

2. Efficient Insertion/Deletion

• Queue me insertion aur deletion O(1) time me hota hai (front aur rear se).
• Ye performance-critical applications ke liye useful hai.

3. Resource Management

• Operating systems tasks, jobs, aur processes ko manage karne ke liye queues ka use karte hain.

Queue ke Disadvantages

1. Random Access Allowed Nahi Hai

• Aap kisi bhi middle element ko directly access nahi kar sakte jaise array me karte ho.
• Har access FIFO ke sequence me hi hota hai.

2. Static Queue me Fixed Size Hota Hai

• Agar aap array-based queue banate ho to size fix hota hai, aur queue overflow ka issue aa sakta hai.
• Isliye dynamic queue ya circular queue preferred hai.

3. Memory Waste ho sakti hai

• Simple array queue me agar elements remove ho jaate hain to space reuse nahi hoti jiski wajah underflow ka issue ho sakta hai (except in circular queue).

Applications of Queue

1. Operating System

• Process scheduling (Round Robin, FCFS scheduling) me queues ka use hota hai.

2. Print Queue

• Jo documents pehle print ke liye bheje jaate hain, unhe pehle hi print kiya jaata hai.

3. Call Center System

• Pehle call aaya, pehle attend kiya gaya, this is FIFO using queue.

4. Data Stream Handling

• Streaming data (jaise audio/video) ko buffer me queue ki tarah manage kiya jaata hai.

5. Breadth First Search (BFS) in Graphs

• Graph traversal algorithms jaise BFS me queue ka use hota hai.

Queue Implementation using Array

#include <iostream>
using namespace std;

#define SIZE 100

class Queue {
private:
    int arr[SIZE];
    int front, rear;

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    // Enqueue operation
    void enqueue(int val) {
        if (rear == SIZE - 1) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        if (front == -1) front = 0;
        arr[++rear] = val;
        cout << val << " enqueued." << endl;
    }

    // Dequeue operation
    void dequeue() {
        if (front == -1 || front > rear) {
            cout << "Queue Underflow!" << endl;
            return;
        }
        cout << arr[front++] << " dequeued." << endl;
    }

    // Peek front element
    int peek() {
        if (front == -1 || front > rear) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return arr[front];
    }

    // Display all elements
    void display() {
        if (front == -1 || front > rear) {
            cout << "Queue is empty." << endl;
            return;
        }
        cout << "Queue elements: ";
        for (int i = front; i <= rear; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    q.display();

    q.dequeue();
    q.display();

    return 0;
}

Explanation:

Queue using Array Kya Hai?

• Array ka use karke hum queue banate hain jisme elements ek fixed size ke array me store hote hain.
• Queue me front aur rear two pointers hote hain:
• front → jahan se element nikale jaate hain wo hota hai dequeue.
• rear → jahan par naye elements add kiye jaate hain wo hota hai enqueue

Code Walkthrough & Explanation

#define SIZE 100

Hum ek macro define kar rahe hain SIZE = 100, matlab queue ka maximum size 100 hoga. Ye humari array-based queue ki limit ko define karta hai.

Class Declaration

class Queue {
private:
    int arr[SIZE];
    int front, rear;

Yahan humne 3 cheezein define ki hain:

• arr[SIZE] → array jisme elements store honge.
• front → wo index jahan se elements remove honge.
• rear → wo index jahan par naye elements insert honge.

public:
    Queue() {
        front = -1;
        rear = -1;
    }

Constructor me front aur rear ko -1 set kiya gaya hai, iska matlab hai queue abhi empty hai.

Enqueue Operation

void enqueue(int val) {
    if (rear == SIZE - 1) {
        cout << "Queue Overflow!" << endl;
        return;
    }
    if (front == -1) front = 0;
    arr[++rear] = val;
    cout << val << " enqueued." << endl;
}

Explanation:

• Pehle check hota hai:
• rear == SIZE - 1
• Agar rear end me pahuch gaya, matlab queue full hai → Overflow.
• Agar front == -1, iska matlab pehla element insert ho raha hai. To front ko 0 kar dete hain.
• ++rear → Rear increment ho gaya aur val ko us position par insert kiya gaya.

Time Complexity: O(1) – Kyunki sirf ek element add ho raha hai.

Dequeue Operation

void dequeue() {
    if (front == -1 || front > rear) {
        cout << "Queue Underflow!" << endl;
        return;
    }
    cout << arr[front++] << " dequeued." << endl;
}

Explanation:

• Pehle check hota hai:
• front == -1 → queue empty hai
• front > rear → saare elements dequeue ho chuke hain

In dono cases me Underflow print hota hai.

• Agar element hai, to arr[front++] se element print bhi hota hai aur front ek position aage chala jaata hai.

Time Complexity: O(1) – Ek element remove ho raha hai.

Peek (Front Element)

int peek() {
    if (front == -1 || front > rear) {
        cout << "Queue is empty." << endl;
        return -1;
    }
    return arr[front];
}

Explanation:

• Ye function top/front element return karta hai without removing.
• Underflow condition ke liye check hota hai.
• Otherwise, arr[front] return karta hai.

Display Elements

void display() {
    if (front == -1 || front > rear) {
        cout << "Queue is empty." << endl;
        return;
    }
    cout << "Queue elements: ";
    for (int i = front; i <= rear; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Explanation:

• Queue me jitne elements front se rear tak hain, unhe print karta hai.
• Agar queue empty hai to message print karta hai.

Time Complexity: O(n) – Kyunki har element traverse hota hai.

Main Function Example

int main() {
    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    q.display();

    q.dequeue();
    q.display();

    return 0;
}

Output:

10 enqueued.

20 enqueued.

30 enqueued.

Queue elements: 10 20 30

10 dequeued.

Queue elements: 20 30

Limitations of Array-Based Queue

1. Fixed Size
2. Queue overflow ho sakti hai agar rear last index tak pahuch jaye.
3. Space Wastage
4. Jab hum elements dequeue karte hain, front aage badhta hai par unused space arr[] me rehti hai.
5. Example: 10 dequeue hone ke baad uski space wapas use nahi hoti.
6. Solution:

• Circular Queue ya Linked List Queue ka use karna chahiye, jo memory ko efficiently use karte hain.

Circular Queue, Jab Normal Queue Fail Ho Jaaye!

Circular Queue Kya Hoti Hai?

Circular Queue ek advanced version hai normal queue ka, jisme last position connect hoti hai first position se, isliye ise “circular” bola jaata hai.

Problem in Normal Queue:

Normal queue me jab rear end tak pahuch jaata hai aur hum elements dequeue kar chuke hote hain, to free space hone ke bawajood bhi hum naye element nahi dal sakte.

Example:

Queue: [ _, _, _, _, 50 ]

Front = 4, Rear = 4 (5th position full)

Queue me space hai, lekin rear end tak pahuch gaya, so no enqueue — yeh hai normal queue ki limitation.

Circular Queue is the Solution:

• Circular queue me jab rear last index tak pahuchta hai, to wo wapis 0th index pe jaa sakta hai (agar empty ho to).
• Isse space efficiently use hoti hai.

FIFO But Circular Style

• Insertion (enqueue) happens at rear
• Deletion (dequeue) happens at front
• But jab zarurat hoti hai, rear begining mein aa jata hai.

Circular Queue Implementation (Using Array)

#include <iostream>
#define SIZE 5
using namespace std;

class CircularQueue {
private:
    int arr[SIZE];
    int front, rear;

public:
    CircularQueue() {
        front = -1;
        rear = -1;
    }
    // Check if queue is full
    bool isFull() {
        return (front == 0 && rear == SIZE - 1) || (rear + 1) % SIZE == front;
    }
    // Check if queue is empty
    bool isEmpty() {
        return front == -1;
    }
    // Enqueue
    void enqueue(int val) {
        if (isFull()) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % SIZE;
        }
        arr[rear] = val;
        cout << val << " enqueued." << endl;
    }
    // Dequeue
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return;
        }
        cout << arr[front] << " dequeued." << endl;
        if (front == rear) {
            front = rear = -1; // only one element was present
        } else {
            front = (front + 1) % SIZE;
        }
    }
    // Display queue
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return;
        }
        cout << "Queue elements: ";
        int i = front;
        while (true) {
            cout << arr[i] << " ";
            if (i == rear) break;
            i = (i + 1) % SIZE;
        }
        cout << endl;
    }
};

int main() {
    CircularQueue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50); // Full

    q.display();

    q.dequeue();
    q.dequeue();

    q.enqueue(60);
    q.enqueue(70);

    q.display();

    return 0;
}

Output:

10 enqueued.

20 enqueued.

30 enqueued.

40 enqueued.

50 enqueued.

Queue Overflow!

10 dequeued.

20 dequeued.

60 enqueued.

70 enqueued.

Queue elements: 30 40 50 60 70 

Explanation:

Initialization:

front = -1;
rear = -1;

• Jab queue create hoti hai, front aur rear dono -1 hote hain.
• Matlab: Queue is empty.

q.enqueue(10);

if (isEmpty()) → true
=> front = 0; rear = 0;
=> arr[0] = 10;

• Queue empty thi, to front/rear dono 0 ho jaate hain.
• 10 value queue me add hoti hai.

Output: 10 enqueued.

q.enqueue(20);

rear = (rear + 1) % SIZE = (0 + 1) % 5 = 1;
arr[1] = 20;

• 20 ko rear position par daala gaya.

Output: 20 enqueued.

q.enqueue(30);

rear = (1 + 1) % 5 = 2;
arr[2] = 30;

Output: 30 enqueued.

q.enqueue(40);

rear = (2 + 1) % 5 = 3;
arr[3] = 40;

Output: 40 enqueued.

q.enqueue(50);

rear = (3 + 1) % 5 = 4;
arr[4] = 50;

Output: 50 enqueued.

q.enqueue(60); → Queue Overflow

isFull() becomes true:
(front == 0 && rear == 4) → true

• Rear last index tak pahuch gaya (4) aur front abhi bhi 0 hai → full.
• Circular space abhi tak create nahi hui (kyunki dequeue nahi hua).

Output: Queue Overflow!

q.display();

Queue: 10 20 30 40 50

• Front = 0
• Rear = 4
• Queue elements from front to rear print hote hain.

Output: Queue elements: 10 20 30 40 50

q.dequeue(); (removes 10)

front = (0 + 1) % 5 = 1;

• Front move karke next index par chala gaya.
• 10 removed from front.

Output: 10 dequeued.

q.dequeue(); (removes 20)

front = (1 + 1) % 5 = 2;

• 20 bhi remove ho gaya.
• Front now at index 2.

Output: 20 dequeued.

q.enqueue(60);

rear = (4 + 1) % 5 = 0;
arr[0] = 60;

• Ye hai circular behavior — rear ab wapas 0 index par gaya.
• 60 add hua circularly.

Output: 60 enqueued.

q.enqueue(70);

rear = (0 + 1) % 5 = 1;
arr[1] = 70;

• Rear ab 1 par gaya (yeh wo position hai jahan pehle 20 tha, jo dequeue ho chuka hai).

Output: 70 enqueued.

q.display();

Now the queue has these elements in circular order:

• Front = 2
• Rear = 1
• Elements print honge: 30 40 50 60 70

Output: Queue elements: 30 40 50 60 70

Queue Implementation using LInked List

• Linked List Queue: Har element ek node hota hai jisme data aur next pointer hota hai.
• Front → Jahan se elements remove (dequeue) hote hain.
• Rear → Jahan naye elements add (enqueue) hote hain.

#include <iostream>
using namespace std;
// Node class
class Node {
public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = NULL;
    }
};
// Queue class
class Queue {
private:
    Node* front;
    Node* rear;
public:
    Queue() {
        front = NULL;
        rear = NULL;
    }
    // Enqueue operation (Insert at rear)
    void enqueue(int val) {
        Node* newNode = new Node(val);
        if (rear == NULL) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        cout << val << " enqueued." << endl;
    }
    // Dequeue operation (Remove from front)
    void dequeue() {
        if (front == NULL) {
            cout << "Queue Underflow!" << endl;
            return;
        }
        Node* temp = front;
        cout << front->data << " dequeued." << endl;
        front = front->next;
        // If queue becomes empty
        if (front == NULL)
            rear = NULL;
        delete temp;
    }
    // Peek operation (front element)
    int peek() {
        if (front == NULL) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return front->data;
    }
    // Display elements
    void display() {
        if (front == NULL) {
            cout << "Queue is empty." << endl;
            return;
        }
        Node* temp = front;
        cout << "Queue elements: ";
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

// Main function
int main() {
    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();

    q.dequeue();
    q.display();

    q.enqueue(40);
    q.enqueue(50);
    q.display();

    cout << "Front element is: " << q.peek() << endl;

    return 0;
}

Output:

10 enqueued.

20 enqueued.

30 enqueued.

Queue elements: 10 20 30 

10 dequeued.

Queue elements: 20 30 

40 enqueued.

50 enqueued.

Queue elements: 20 30 40 50 

Front element is: 20

Explanation:

1. Node Structure

class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};

Explanation:

• Hum har element ko ek node ke form me store karenge.
• Har node me do cheezein hongi:
• data → jo value queue me store karni hai.
• next → next node ka address (ya NULL if last node).

Yeh ek basic building block hai linked list ka.

2. Queue Class with Pointers

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() {
        front = NULL;
        rear = NULL;
    }

Explanation:

• front → jahan se remove (dequeue) karna hota hai.
• rear → jahan naya node insert (enqueue) hota hai.

Agar queue khaali ho, to front aur rear dono NULL hote hain.

3. Enqueue Operation – Insert at Rear

void enqueue(int val) {
    Node* newNode = new Node(val);

    if (rear == NULL) { // Queue is empty
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }

    cout << val << " enqueued." << endl;
}

Explanation:

• Naya node create kiya: newNode.
• Case 1: Agar queue khaali hai (rear == NULL)
• Pehla element insert ho raha hai → front & rear dono ko newNode set kar do.
• Case 2: Queue me elements hain:
• rear->next = newNode → purane rear se newNode jod diya.
• rear = newNode → rear ko update kiya.

FIFO Follow Karta Hai: Jo pehle aaya, woh pehle niklega. Naya bas end me add ho raha hai.

4. Dequeue Operation – Remove from Front

void dequeue() {
    if (front == NULL) {
        cout << "Queue Underflow!" << endl;
        return;
    }

    Node* temp = front;
    cout << front->data << " dequeued." << endl;
    front = front->next;

    if (front == NULL) {
        rear = NULL; // Queue became empty
    }

    delete temp;
}

Explanation:

• Check: Agar front == NULL, toh queue khaali hai → Underflow.
• Warna:
• temp pointer banaya jo front ko point kare.
• Front ko aage badha diya → front = front->next.
• Agar front null ho gaya → queue khaali ho gayi → rear bhi null kar do.
• Temp node delete kar diya to free memory.

Important: delete temp; se memory leak avoid hoti hai.

5. Peek Operation

int peek() {
    if (front == NULL) {
        cout << "Queue is empty." << endl;
        return -1;
    }
    return front->data;
}

Explanation:

• Queue khaali hai? → print message.
• Warna front node ka data return karo bina remove kiye.

6. Display Operation

void display() {
    if (front == NULL) {
        cout << "Queue is empty." << endl;
        return;
    }

    Node* temp = front;
    cout << "Queue elements: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

Explanation:

• Temp pointer ko front se start karte hain.
• Jab tak temp != NULL, tab tak queue ke nodes print karte hain.
• FIFO order mein print hote hain.