Introduction to Queue

A data structure where the first item added is the first one removed.

Introduction to Queue

Queue एक linear data structure है जिसमें elements को एक विशेष क्रम में store और access किया जाता है। Queue में insertion एक end से और deletion दूसरे end से किया जाता है। जिस end से element insert किया जाता है उसे Rear और जिस end से element remove किया जाता है उसे Front कहा जाता है।

Queue FIFO (First In, First Out) principle पर काम करता है। इसका अर्थ है कि जो element सबसे पहले queue में insert किया जाता है, वही सबसे पहले बाहर निकलता है।

FIFO: First In, First Out — जो element सबसे पहले आएगा, वह सबसे पहले बाहर जाएगा।

Real-Life Example of Queue

Queue को ticket counter पर लगी लोगों की line से समझा जा सकता है। जो व्यक्ति सबसे पहले line में आता है, उसे सबसे पहले service मिलती है। इसी प्रकार queue में सबसे पहले insert किया गया element सबसे पहले remove होता है।

Basic Terminology of Queue

Term	Meaning
Queue	FIFO principle पर आधारित linear data structure
Front	Queue का वह end जहाँ से element remove किया जाता है
Rear	Queue का वह end जहाँ नया element insert किया जाता है
Enqueue	Queue में नया element insert करना
Dequeue	Queue से element remove करना
Peek	Front element को बिना remove किए देखना
Overflow	Full queue में नया element insert करने का प्रयास
Underflow	Empty queue से element remove करने का प्रयास

Representation of a Queue

एक queue को सामान्यतः इस प्रकार represent किया जा सकता है:

Front → 10 | 20 | 30 | 40 ← Rear

इस queue में 10 front element है और 40 rear element है। Dequeue operation करने पर 10 सबसे पहले remove होगा।

Basic Queue Operations

Queue पर मुख्य रूप से निम्न operations किए जाते हैं:

Enqueue: Queue के rear में नया element insert करना।
Dequeue: Queue के front से element remove करना।
Peek: Front element को बिना remove किए देखना।
isEmpty: यह check करना कि queue खाली है या नहीं।
isFull: यह check करना कि queue पूरी तरह भर चुकी है या नहीं।

1. Enqueue Operation

Enqueue operation का उपयोग queue में नया element insert करने के लिए किया जाता है। नया element हमेशा Rear पर add होता है।

Initial Queue:
Front → 10 | 20 ← Rear

Enqueue(30) के बाद:
Front → 10 | 20 | 30 ← Rear

2. Dequeue Operation

Dequeue operation queue के front element को remove करता है। Queue में deletion केवल front से किया जाता है।

Before Dequeue:
Front → 10 | 20 | 30 ← Rear

After Dequeue:
Front → 20 | 30 ← Rear

3. Peek Operation

Peek operation queue के front element की value बताता है, लेकिन element को queue से remove नहीं करता।

#include <iostream>
using namespace std;

int main()
{
    int queue[5] = {10, 20, 30};
    int front = 0;
    int rear = 2;

    cout << "Front element = " << queue[front];

    return 0;
}

Output:
Front element = 10

Queue Using an Array

C++ में queue को array की सहायता से implement किया जा सकता है। इसमें सामान्यतः दो variables front और rear का उपयोग किया जाता है।

front: Queue के पहले element का index रखता है।
rear: Queue के अंतिम element का index रखता है।

एक simple linear queue में शुरुआत में:

front = -1;
rear = -1;

इसका अर्थ है कि queue खाली है।

Simple Queue Implementation

#include <iostream>
using namespace std;

int main()
{
    int queue[5];
    int front = 0;
    int rear = -1;

    // Enqueue elements
    queue[++rear] = 10;
    queue[++rear] = 20;
    queue[++rear] = 30;

    cout << "Queue elements:" << endl;

    for (int i = front; i <= rear; i++)
    {
        cout << queue[i] << endl;
    }

    return 0;
}

Output:
Queue elements:
10
20
30

Enqueue Operation in C++

Enqueue operation के दौरान यह check करना आवश्यक है कि queue full तो नहीं है। Simple array-based queue में यदि rear == SIZE - 1 है, तो queue full मानी जाती है।

#include <iostream>
using namespace std;

int main()
{
    const int SIZE = 5;

    int queue[SIZE];
    int front = 0;
    int rear = -1;

    int value = 10;

    if (rear == SIZE - 1)
    {
        cout << "Queue Overflow";
    }
    else
    {
        queue[++rear] = value;
        cout << value << " inserted into queue";
    }

    return 0;
}

Output:
10 inserted into queue

Dequeue Operation in C++

Dequeue operation से पहले यह check किया जाता है कि queue empty तो नहीं है। यदि queue में कोई element नहीं है, तो dequeue operation नहीं किया जा सकता।

#include <iostream>
using namespace std;

int main()
{
    int queue[5] = {10, 20, 30};
    int front = 0;
    int rear = 2;

    if (front > rear)
    {
        cout << "Queue Underflow";
    }
    else
    {
        cout << "Deleted element = " << queue[front];
        front++;
    }

    return 0;
}

Output:
Deleted element = 10

Complete Queue Program Using Array

नीचे एक simple C++ program दिया गया है जिसमें enqueue, dequeue और display operations को functions की सहायता से implement किया गया है।

#include <iostream>
using namespace std;

const int SIZE = 5;

int queue[SIZE];
int front = -1;
int rear = -1;

void enqueue(int value)
{
    if (rear == SIZE - 1)
    {
        cout << "Queue Overflow" << endl;
    }
    else
    {
        if (front == -1)
            front = 0;

        queue[++rear] = value;
        cout << value << " inserted" << endl;
    }
}

void dequeue()
{
    if (front == -1 || front > rear)
    {
        cout << "Queue Underflow" << endl;
    }
    else
    {
        cout << queue[front] << " deleted" << endl;
        front++;
    }
}

void display()
{
    if (front == -1 || front > rear)
    {
        cout << "Queue is empty" << endl;
    }
    else
    {
        cout << "Queue:" << endl;

        for (int i = front; i <= rear; i++)
        {
            cout << queue[i] << endl;
        }
    }
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);

    display();

    dequeue();

    display();

    return 0;
}

Output:
10 inserted
20 inserted
30 inserted
Queue:
10
20
30
10 deleted
Queue:
20
30

Queue Overflow

जब queue पूरी तरह भर चुकी हो और उसमें नया element insert करने का प्रयास किया जाए, तो इस स्थिति को Queue Overflow कहा जाता है।

Queue Overflow: Full queue में Enqueue operation करने का प्रयास।

Queue Underflow

जब queue खाली हो और उसमें से element remove करने का प्रयास किया जाए, तो इस स्थिति को Queue Underflow कहा जाता है।

Queue Underflow: Empty queue में Dequeue operation करने का प्रयास।

Applications of Queue

Queue का उपयोग computer science और real-world systems में कई जगह किया जाता है:

Printer job scheduling में।
CPU scheduling में।
Keyboard और I/O buffering में।
Network data packet management में।
Customer service systems में।
Breadth First Search (BFS) algorithm में।
Task scheduling में।
Operating systems में process management के विभिन्न कार्यों में।

Queue and FIFO Principle

Queue का सबसे महत्वपूर्ण characteristic FIFO है। मान लीजिए elements को इस क्रम में enqueue किया गया:

Enqueue: 10 → 20 → 30 → 40

तो dequeue करने पर elements इस क्रम में बाहर आएँगे:

Dequeue: 10 → 20 → 30 → 40

Stack vs Queue

Feature	Stack	Queue
Principle	LIFO	FIFO
Insertion	Top से	Rear से
Deletion	Top से	Front से
Ends Used	एक end	दो ends
Example	Plates का stack	Ticket की queue

Advantages of Queue

Queue का structure सरल और समझने में आसान होता है।
FIFO principle के कारण fair processing संभव होती है।
Scheduling और buffering के लिए उपयोगी है।
Data को orderly तरीके से process किया जा सकता है।
BFS जैसे algorithms में उपयोगी है।

Limitations of Linear Queue

Simple array-based queue में memory का efficient उपयोग नहीं हो सकता।
Front से elements delete होने के बाद शुरुआती खाली स्थान हमेशा reuse नहीं हो पाता।
Fixed-size array में queue की capacity सीमित होती है।
Full queue में enqueue करने पर overflow हो सकता है।

Why Circular Queue is Needed?

Simple linear queue में dequeue के बाद front की ओर खाली हुए positions को सीधे reuse नहीं किया जा सकता। इस समस्या को दूर करने के लिए Circular Queue का उपयोग किया जाता है। Circular queue में अंतिम position के बाद फिर से पहली position पर आया जा सकता है।

Linear Queue: Front → 10 | 20 | 30 | 40 ← Rear

Circular Queue: Last position के बाद first position को फिर से use किया जा सकता है।

Important Points

Queue एक linear data structure है।
Queue FIFO (First In, First Out) principle पर काम करता है।
Insertion Rear से होता है।
Deletion Front से होता है।
Enqueue operation element insert करता है।
Dequeue operation element remove करता है।
Peek front element को बिना remove किए दिखाता है।
Empty queue में dequeue करने पर Underflow होता है।
Full queue में enqueue करने पर Overflow होता है।
Array-based queue में front और rear variables का उपयोग किया जाता है।
Queue का उपयोग scheduling, buffering और BFS में किया जाता है।

Board Focus

Exam के लिए याद रखें:
Queue → Linear Data Structure
Principle → FIFO
Insertion → Enqueue
Deletion → Dequeue
Insertion End → Rear
Deletion End → Front
Front Element → Peek
Full Queue में Enqueue → Overflow
Empty Queue में Dequeue → Underflow

Board Important Questions

Very Short Answer Questions

Q1. Queue क्या है?

Answer: Queue एक linear data structure है जो FIFO principle पर काम करता है।

Q2. FIFO का full form क्या है?

Answer: First In, First Out.

Q3. Queue में insertion किस operation द्वारा किया जाता है?

Answer: Enqueue operation द्वारा।

Q4. Queue में deletion किस operation द्वारा किया जाता है?

Answer: Dequeue operation द्वारा।

Q5. Queue में insertion किस end से होता है?

Answer: Rear से।

Q6. Queue में deletion किस end से होता है?

Answer: Front से।

Q7. Queue Overflow क्या है?

Answer: Full queue में नया element insert करने का प्रयास Queue Overflow कहलाता है।

Q8. Queue Underflow क्या है?

Answer: Empty queue से element remove करने का प्रयास Queue Underflow कहलाता है।

Short Answer Questions

Q9. Enqueue और Dequeue में अंतर बताइए।

Answer: Enqueue operation queue के rear में नया element insert करता है, जबकि Dequeue operation queue के front से element remove करता है।

Q10. Queue में Front और Rear की भूमिका समझाइए।

Answer: Front queue के उस end को दर्शाता है जहाँ से elements delete किए जाते हैं, जबकि Rear उस end को दर्शाता है जहाँ नए elements insert किए जाते हैं।

Q11. Queue के कोई चार applications लिखिए।

Answer: Queue का उपयोग CPU scheduling, printer scheduling, network buffering और Breadth First Search में किया जाता है।

Q12. Queue और Stack में मुख्य अंतर क्या है?

Answer: Stack LIFO principle पर काम करता है और insertion तथा deletion एक ही end से होते हैं। Queue FIFO principle पर काम करता है और insertion Rear से तथा deletion Front से होता है।

Long Answer Questions

Q13. Queue को array की सहायता से implement करने का C++ program लिखिए।

#include <iostream>
using namespace std;

int main()
{
    int queue[5];
    int front = 0;
    int rear = -1;

    queue[++rear] = 10;
    queue[++rear] = 20;
    queue[++rear] = 30;

    cout << "Queue elements:" << endl;

    for (int i = front; i <= rear; i++)
    {
        cout << queue[i] << endl;
    }

    return 0;
}

Output:
Queue elements:
10
20
30

Q14. Queue में Enqueue और Dequeue operations को C++ में implement कीजिए।

#include <iostream>
using namespace std;

int main()
{
    int queue[5];
    int front = 0;
    int rear = -1;

    // Enqueue
    queue[++rear] = 10;
    queue[++rear] = 20;
    queue[++rear] = 30;

    // Dequeue
    cout << "Deleted: " << queue[front] << endl;
    front++;

    cout << "Front element: " << queue[front];

    return 0;
}

Output:
Deleted: 10
Front element: 20

Q15. Queue Overflow को check करने का C++ program लिखिए।

#include <iostream>
using namespace std;

int main()
{
    const int SIZE = 3;

    int queue[SIZE] = {10, 20, 30};
    int rear = 2;

    if (rear == SIZE - 1)
        cout << "Queue Overflow";
    else
        cout << "Enqueue operation possible";

    return 0;
}

Output:
Queue Overflow

Q16. Queue Underflow को check करने का C++ program लिखिए।

#include <iostream>
using namespace std;

int main()
{
    int queue[5];
    int front = -1;
    int rear = -1;

    if (front == -1 || front > rear)
        cout << "Queue Underflow";
    else
        cout << "Dequeue operation possible";

    return 0;
}

Output:
Queue Underflow

Practice Questions

Queue क्या है? इसके मुख्य characteristics लिखिए।
FIFO principle को उदाहरण सहित समझाइए।
Queue में Enqueue और Dequeue operations क्या हैं?
Queue में Front और Rear की भूमिका समझाइए।
Queue Overflow और Queue Underflow को समझाइए।
Array की सहायता से queue implement करने का C++ program लिखिए।
Queue में तीन elements enqueue करने का program लिखिए।
Queue से front element dequeue करने का program लिखिए।
Queue के front element को display करने का program लिखिए।
Queue में Overflow condition check करने का program लिखिए।
Queue में Underflow condition check करने का program लिखिए।
Stack और Queue में अंतर लिखिए।
Queue के पाँच applications लिखिए।
Linear Queue की limitation क्या है?
Circular Queue की आवश्यकता क्यों पड़ती है?
यदि 10, 20, 30 और 40 को इसी क्रम में enqueue किया जाए, तो dequeue करने पर किस क्रम में elements प्राप्त होंगे?

Quick Revision

Queue: Linear data structure
Principle: FIFO
Insertion: Enqueue
Deletion: Dequeue
Insertion End: Rear
Deletion End: Front
Front Element: Peek द्वारा देखा जा सकता है
Overflow: Full queue में Enqueue
Underflow: Empty queue में Dequeue
Main Applications: Scheduling, buffering और BFS

One-Line Revision: Queue एक FIFO-based linear data structure है जिसमें insertion Rear से और deletion Front से किया जाता है।

Lesson 20 of 37

Previous Lesson Infix to Postfix and Postfix Evaluation Next Lesson Circular Queue

Computer Science - Class XII

Introduction to Queue