Circular Queue

Circular Queue

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

Circular Queue भी FIFO (First In, First Out) principle पर काम करती है। इसमें insertion Rear से और deletion Front से किया जाता है।

Need for Circular Queue

Simple linear queue में यदि कुछ elements dequeue कर दिए जाएँ, तो front की ओर खाली हुई positions उपलब्ध होने के बावजूद rear आगे बढ़ता रहता है। इससे array की कुछ memory unused रह सकती है।

उदाहरण के लिए, मान लीजिए queue की size 5 है:

यदि 10 और 20 को dequeue कर दिया जाए, तो स्थिति होगी:

अब शुरुआत की दो positions खाली हैं, लेकिन simple linear queue में rear आगे नहीं जा सकता। Circular Queue इस समस्या को solve करती है और खाली positions को फिर से उपयोग करने देती है।

Structure of Circular Queue

Circular Queue में अंतिम index के बाद अगला index फिर से 0 हो जाता है। इसके लिए modulus (%) operator का उपयोग किया जाता है।

उदाहरण के लिए, यदि SIZE = 5 है:

इस प्रकार position 4 के बाद queue वापस position 0 पर आ जाती है।

Important Terms

Enqueue Operation in Circular Queue

Circular Queue में नया element insert करने से पहले यह check किया जाता है कि queue full है या नहीं। Full condition सामान्यतः इस प्रकार होती है:

यदि यह condition true है, तो circular queue full है और नया element insert नहीं किया जा सकता।

Dequeue Operation in Circular Queue

Dequeue operation में element को front position से remove किया जाता है। इसके बाद front को circular तरीके से आगे बढ़ाया जाता है:

Empty Circular Queue

Circular Queue को empty दिखाने के लिए सामान्य implementation में front = -1 रखा जाता है।

Example of Circular Queue

मान लीजिए circular queue की size 5 है और उसमें निम्न elements insert किए गए:

अब यदि 10 और 20 को dequeue किया जाए, तो positions 0 और 1 खाली हो जाएँगी। अब यदि 60 और 70 insert किए जाएँ, तो वे खाली हुई शुरुआती positions पर insert हो सकते हैं:

यही circular queue की सबसे महत्वपूर्ण विशेषता है।

Step-by-Step Working

Circular Queue Using Array in C++

नीचे एक C++ program दिया गया है जो array की सहायता से circular queue implement करता है। इसमें enqueue, dequeue और display operations शामिल हैं।

#include <iostream>
using namespace std;

const int SIZE = 5;

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

void enqueue(int value)
{
    if ((rear + 1) % SIZE == front)
    {
        cout << "Queue Overflow" << endl;
        return;
    }

    if (front == -1)
    {
        front = 0;
        rear = 0;
    }
    else
    {
        rear = (rear + 1) % SIZE;
    }

    queue[rear] = value;

    cout << value << " inserted" << endl;
}

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

    cout << queue[front] << " deleted" << endl;

    if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else
    {
        front = (front + 1) % SIZE;
    }
}

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

    cout << "Queue: ";

    int i = front;

    while (true)
    {
        cout << queue[i] << " ";

        if (i == rear)
            break;

        i = (i + 1) % SIZE;
    }

    cout << endl;
}

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

    display();

    dequeue();
    dequeue();

    display();

    enqueue(60);
    enqueue(70);

    display();

    return 0;
}

How Modulus Operator Makes Queue Circular

Circular Queue में modulus operator का विशेष महत्व है। यदि queue की size 5 है और rear की current position 4 है, तो अगली position होगी:

rear = (rear + 1) % 5;

इसका result होगा:

इसलिए rear position 4 से वापस position 0 पर आ जाता है।

Full Condition

Circular Queue में queue full होने की condition है:

इस condition का अर्थ है कि rear के आगे वाली position front के बराबर है। यानी queue में कोई खाली position उपलब्ध नहीं है।

Empty Condition

हमारी implementation में circular queue empty होने की condition है:

जब आखिरी element भी dequeue हो जाता है, तब front और rear दोनों को -1 कर दिया जाता है।

Circular Queue vs Linear Queue

Advantages of Circular Queue

• Memory का बेहतर उपयोग होता है।
• Dequeue के बाद खाली हुई positions को reuse किया जा सकता है।
• Linear queue की false overflow problem को कम करता है।
• Fixed-size buffer के लिए उपयोगी है।
• CPU scheduling और buffering जैसे applications में उपयोगी है।
• Queue operations efficient तरीके से किए जा सकते हैं।

Applications of Circular Queue

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

• CPU Scheduling: Round Robin scheduling में।
• Memory Buffer: Data buffering के लिए।
• Keyboard Buffer: Keyboard input को temporarily store करने में।
• Network Buffer: Data packets को manage करने में।
• Traffic Management: कुछ scheduling systems में।
• Streaming Data: Continuous data processing में।

False Overflow

Linear queue में एक स्थिति ऐसी आ सकती है जिसमें queue का rear array के अंतिम स्थान पर पहुँच जाता है, जबकि शुरुआत में कुछ positions खाली होती हैं। इसे False Overflow कहा जाता है।

Circular Queue इन खाली positions को reuse करके इस समस्या को solve करती है।

Time Complexity

Important Points

• Circular Queue एक linear data structure का circular implementation है।
• यह FIFO principle पर काम करती है।
• Insertion Rear से होता है।
• Deletion Front से होता है।
• Last position के बाद first position को फिर से use किया जा सकता है।
• Modulo (%) operator circular movement के लिए महत्वपूर्ण है।
• Full condition: (rear + 1) % SIZE == front
• Empty condition: front == -1
• Circular Queue memory utilization को improve करती है।
• यह linear queue की false overflow problem को solve करती है।
• Round Robin scheduling में Circular Queue का उपयोग किया जा सकता है।

Board Focus

Board Important Questions

Very Short Answer Questions

Q1. Circular Queue क्या है?

Answer: Circular Queue एक ऐसी queue है जिसमें अंतिम position के बाद queue फिर से पहली position पर आ जाती है।

Q2. Circular Queue किस principle पर काम करती है?

Answer: FIFO (First In, First Out) principle पर।

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

Answer: Rear से।

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

Answer: Front से।

Q5. Circular Queue में circular movement के लिए किस operator का उपयोग किया जाता है?

Answer: Modulus (%) operator।

Q6. Circular Queue की full condition क्या है?

Answer: (rear + 1) % SIZE == front

Q7. Circular Queue की empty condition क्या है?

Answer: front == -1

Q8. Circular Queue का मुख्य लाभ क्या है?

Answer: यह dequeue के बाद खाली हुई positions को दोबारा उपयोग करने देती है।

Short Answer Questions

Q9. Linear Queue की तुलना में Circular Queue की आवश्यकता क्यों पड़ती है?

Answer: Linear Queue में front से elements delete होने के बाद शुरुआती positions खाली हो सकती हैं, लेकिन उनका प्रभावी रूप से reuse नहीं हो पाता। Circular Queue इन positions को दोबारा उपयोग करके memory utilization को बेहतर बनाती है।

Q10. Circular Queue में modulus operator का क्या महत्व है?

Answer: Modulus operator last position के बाद index को फिर से first position पर लाने के लिए उपयोग किया जाता है। जैसे SIZE 5 होने पर (4 + 1) % 5 = 0।

Q11. False Overflow क्या है?

Answer: Linear queue में rear के अंतिम position पर पहुँच जाने के बावजूद शुरुआती positions खाली होने की स्थिति को false overflow कहा जाता है।

Q12. Circular Queue में Enqueue operation समझाइए।

Answer: Enqueue से पहले full condition check की जाती है। यदि queue full नहीं है, तो rear को circular तरीके से आगे बढ़ाकर नए element को उस position पर insert किया जाता है।

Q13. Circular Queue में Dequeue operation समझाइए।

Answer: Dequeue से पहले empty condition check की जाती है। यदि queue empty नहीं है, तो front element को remove करके front को (front + 1) % SIZE द्वारा आगे बढ़ाया जाता है।

Long Answer Questions

Q14. Circular Queue को array की सहायता से समझाइए।

Answer: Circular Queue में array की last position के बाद first position को फिर से उपयोग किया जाता है। Front deletion position और rear insertion position को दर्शाता है। Circular movement के लिए modulus operator का उपयोग किया जाता है। Full condition सामान्यतः (rear + 1) % SIZE == front होती है, जबकि empty queue में front को -1 रखा जाता है।

Q15. Circular Queue को C++ में implement करने का program लिखिए।

#include <iostream>
using namespace std;

const int SIZE = 5;

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

void enqueue(int value)
{
    if ((rear + 1) % SIZE == front)
    {
        cout << "Queue Overflow" << endl;
        return;
    }

    if (front == -1)
    {
        front = 0;
        rear = 0;
    }
    else
    {
        rear = (rear + 1) % SIZE;
    }

    queue[rear] = value;
}

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

    cout << "Deleted: " << queue[front] << endl;

    if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else
    {
        front = (front + 1) % SIZE;
    }
}

void display()
{
    if (front == -1)
    {
        cout << "Queue is empty";
        return;
    }

    int i = front;

    cout << "Queue: ";

    while (true)
    {
        cout << queue[i] << " ";

        if (i == rear)
            break;

        i = (i + 1) % SIZE;
    }
}

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

    dequeue();

    enqueue(40);
    enqueue(50);

    display();

    return 0;
}

Q16. Circular Queue और Linear Queue में अंतर लिखिए।

Answer: Linear Queue में elements linear order में रहते हैं और rear के अंतिम position पर पहुँचने के बाद आगे नहीं बढ़ सकता। Circular Queue में अंतिम position के बाद first position को फिर से उपयोग किया जा सकता है। इसलिए Circular Queue memory का अधिक efficient उपयोग करती है और false overflow की समस्या को कम करती है।

Practice Questions

1. Circular Queue क्या है?
2. Circular Queue FIFO principle पर कैसे काम करती है?
3. Circular Queue में Front और Rear की भूमिका समझाइए।
4. Circular Queue में Enqueue और Dequeue operations समझाइए।
5. Circular Queue की full condition लिखिए।
6. Circular Queue की empty condition लिखिए।
7. Circular Queue में modulus operator का क्या उपयोग है?
8. False Overflow क्या है?
9. Linear Queue और Circular Queue में अंतर लिखिए।
10. Circular Queue के चार applications लिखिए।
11. Array की सहायता से Circular Queue implement करने का C++ program लिखिए।
12. Enqueue operation का C++ function लिखिए।
13. Dequeue operation का C++ function लिखिए।
14. Circular Queue में empty और full conditions को समझाइए।
15. Circular Queue के advantages और limitations लिखिए।
16. Round Robin CPU scheduling में Circular Queue का उपयोग कैसे किया जाता है?

Quick Revision

• Circular Queue: Circular form में काम करने वाली Queue
• Principle: FIFO
• Insertion: Rear
• Deletion: Front
• Next Rear: (rear + 1) % SIZE
• Next Front: (front + 1) % SIZE
• Full: (rear + 1) % SIZE == front
• Empty: front == -1
• Main Advantage: Empty positions को reuse करना
• Important Operator: Modulus (%)
• Main Application: Round Robin Scheduling और buffering