Computer Programming কিউ (Queue in C) গাইড ও নোট

Queue হল একটি ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতি অনুসরণ করে। অর্থাৎ, যে উপাদানটি প্রথমে যুক্ত হয় সেটিই প্রথমে অপসারণ হয়। কিউ সাধারণত বিভিন্ন ধরনের সমস্যা সমাধানে ব্যবহৃত হয়, যেমন প্রিন্টার কিউ, প্রক্রিয়া কিউ, এবং আরও অনেক ক্ষেত্রে।

Queue (কিউ) হল একটি ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতির উপর কাজ করে। এর মানে হল, যে উপাদানটি প্রথমে যুক্ত হয় সেটি প্রথমে অপসারণ হয়। কিউ সাধারণত বিভিন্ন ধরনের কাজের প্রক্রিয়াকরণের জন্য ব্যবহৃত হয়, যেখানে প্রক্রিয়াটি একটির পর একটি চলে।

১. Queue এর ধারণা

Queue হল একটি সুশৃঙ্খল ডেটা স্ট্রাকচার যা সাধারণত বিভিন্ন কাজের জন্য ব্যবহৃত হয়। কিউতে দুটি প্রধান অপারেশন রয়েছে:

• Enqueue: কিউয়ের শেষে একটি নতুন উপাদান যুক্ত করা।
• Dequeue: কিউয়ের শুরু থেকে একটি উপাদান অপসারণ করা।

২. Queue এর গঠন

কিউ সাধারণত দুটি সূচক ধারণ করে:

• Front: কিউয়ের প্রথম উপাদানের সূচক।
• Rear: কিউয়ের শেষ উপাদানের সূচক।

কিউ এর গঠন উদাহরণ:

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Queue এর সর্বাধিক সাইজ

struct Queue {
    int items[MAX]; // Queue উপাদানগুলির জন্য অ্যারে
    int front;      // Queue এর প্রথম উপাদানের ইনডেক্স
    int rear;       // Queue এর শেষ উপাদানের ইনডেক্স
};

৩. Queue এর প্রয়োগ

Queue এর বিভিন্ন ক্ষেত্রে ব্যবহারের উদাহরণ দেওয়া হলো:

প্রিন্টার কিউ:

• বিভিন্ন প্রিন্ট জব কিউয়ে রাখা হয়, এবং প্রথমে যে জবটি আসে সেটিই প্রথমে প্রিন্ট হয়।

প্রক্রিয়া কিউ:

• অপারেটিং সিস্টেমে বিভিন্ন প্রক্রিয়া বা থ্রেড কিউয়ে রাখা হয়। CPU প্রথমে যে প্রক্রিয়া চালাবে সেটি কিউয়ের শীর্ষে থাকে।

কাস্টমার সার্ভিস:

• ব্যাংক বা রেস্তোরাঁয় কাস্টমারদের সার্ভিস দেওয়ার সময় কাস্টমার কিউয়ে দাঁড়িয়ে থাকেন এবং প্রথমে যে কাস্টমার আসবে সেটিই প্রথমে সার্ভিস পাবে।

ডেটা ট্রান্সমিশন:

• নেটওয়ার্কের মধ্যে প্যাকেট ট্রান্সমিশন কিউয়ে রাখা হয় যাতে প্রথমে আসা প্যাকেটটি প্রথমে প্রেরণ করা হয়।

ব্যাকগ্রাউন্ড টাস্ক:

• ব্যাকগ্রাউন্ড টাস্ক বা কলব্যাক ফাংশন কিউয়ের মাধ্যমে পরিচালনা করা হয়।

 কিউয়ে উপাদান যোগ করা (Enqueue)

void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
    } else {
        if (q->front == -1) { // If queue is empty
            q->front = 0;      // Set front to 0
        }
        q->items[++(q->rear)] = value; // Increment rear and add value
        printf("%d enqueued to queue\n", value);
    }
}

কিউ থেকে উপাদান অপসারণ করা (Dequeue)

int dequeue(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        return q->items[(q->front)++]; // Return the front value and increment front
    }
}

 কিউয়ের প্রথম উপাদান দেখা (Peek)

int peek(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->items[q->front]; // Return the front value
    }
}

 পুরো প্রোগ্রাম উদাহরণ

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Queue এর সর্বাধিক সাইজ

struct Queue {
    int items[MAX]; // Queue উপাদানগুলির জন্য অ্যারে
    int front;      // Queue এর প্রথম উপাদানের ইনডেক্স
    int rear;       // Queue এর শেষ উপাদানের ইনডেক্স
};

// Queue তৈরি এবং ইনিশিয়ালাইজেশন
void initQueue(struct Queue* q) {
    q->front = -1; // Queue খালি
    q->rear = -1;  // Queue খালি
}

// Enqueue অপারেশন
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
    } else {
        if (q->front == -1) { // If queue is empty
            q->front = 0;      // Set front to 0
        }
        q->items[++(q->rear)] = value; // Increment rear and add value
        printf("%d enqueued to queue\n", value);
    }
}

// Dequeue অপারেশন
int dequeue(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        return q->items[(q->front)++]; // Return the front value and increment front
    }
}

// Peek অপারেশন
int peek(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->items[q->front]; // Return the front value
    }
}

// Main function
int main() {
    struct Queue queue; // Create a queue
    initQueue(&queue);  // Initialize the queue

    enqueue(&queue, 10); // Enqueue elements
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Front element is %d\n", peek(&queue)); // Peek at front element

    printf("%d dequeued from queue\n", dequeue(&queue)); // Dequeue element
    printf("Front element is now %d\n", peek(&queue)); // Peek at front element

    return 0;
}

Queue (কিউ) হল একটি ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতি অনুসরণ করে। কিউকে অ্যারে এবং লিঙ্কড লিস্ট ব্যবহার করে সহজেই বাস্তবায়ন করা যায়। নিচে উভয় পদ্ধতির বিস্তারিত আলোচনা এবং উদাহরণ দেওয়া হলো।

১. অ্যারে ব্যবহার করে Queue ইমপ্লিমেন্টেশন

১.১ কিউ এর গঠন

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Queue এর সর্বাধিক সাইজ

struct Queue {
    int items[MAX]; // Queue উপাদানগুলির জন্য অ্যারে
    int front;      // Queue এর প্রথম উপাদানের ইনডেক্স
    int rear;       // Queue এর শেষ উপাদানের ইনডেক্স
};

// Queue তৈরি এবং ইনিশিয়ালাইজেশন
void initQueue(struct Queue* q) {
    q->front = -1; // Queue খালি
    q->rear = -1;  // Queue খালি
}

১.২ কিউয়ে উপাদান যোগ করা (Enqueue)

void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
    } else {
        if (q->front == -1) { // If queue is empty
            q->front = 0;      // Set front to 0
        }
        q->items[++(q->rear)] = value; // Increment rear and add value
        printf("%d enqueued to queue\n", value);
    }
}

১.৩ কিউ থেকে উপাদান অপসারণ করা (Dequeue)

int dequeue(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        return q->items[(q->front)++]; // Return the front value and increment front
    }
}

১.৪ কিউয়ের প্রথম উপাদান দেখা (Peek)

int peek(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->items[q->front]; // Return the front value
    }
}

১.৫ পুরো প্রোগ্রাম উদাহরণ

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Queue এর সর্বাধিক সাইজ

struct Queue {
    int items[MAX]; // Queue উপাদানগুলির জন্য অ্যারে
    int front;      // Queue এর প্রথম উপাদানের ইনডেক্স
    int rear;       // Queue এর শেষ উপাদানের ইনডেক্স
};

// Queue তৈরি এবং ইনিশিয়ালাইজেশন
void initQueue(struct Queue* q) {
    q->front = -1; // Queue খালি
    q->rear = -1;  // Queue খালি
}

// Enqueue অপারেশন
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
    } else {
        if (q->front == -1) { // If queue is empty
            q->front = 0;      // Set front to 0
        }
        q->items[++(q->rear)] = value; // Increment rear and add value
        printf("%d enqueued to queue\n", value);
    }
}

// Dequeue অপারেশন
int dequeue(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        return q->items[(q->front)++]; // Return the front value and increment front
    }
}

// Peek অপারেশন
int peek(struct Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->items[q->front]; // Return the front value
    }
}

// Main function
int main() {
    struct Queue queue; // Create a queue
    initQueue(&queue);  // Initialize the queue

    enqueue(&queue, 10); // Enqueue elements
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Front element is %d\n", peek(&queue)); // Peek at front element

    printf("%d dequeued from queue\n", dequeue(&queue)); // Dequeue element
    printf("Front element is now %d\n", peek(&queue)); // Peek at front element

    return 0;
}

২. লিঙ্কড লিস্ট ব্যবহার করে Queue ইমপ্লিমেন্টেশন

২.১ কিউ এর গঠন

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;              // Data part
    struct Node* next;     // Pointer to the next node
};

// Queue structure
struct Queue {
    struct Node* front;     // Pointer to the front node
    struct Node* rear;      // Pointer to the rear node
};

২.২ কিউ তৈরি এবং ইনিশিয়ালাইজেশন

void initQueue(struct Queue* q) {
    q->front = NULL; // Queue খালি
    q->rear = NULL;  // Queue খালি
}

২.৩ স্ট্যাকের উপাদান যোগ করা (Enqueue)

void enqueue(struct Queue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Create new node
    newNode->data = value;   // Assign data
    newNode->next = NULL;    // Initialize next to NULL

    if (q->rear == NULL) { // If queue is empty
        q->front = newNode; // Both front and rear point to new node
        q->rear = newNode;
    } else {
        q->rear->next = newNode; // Link the new node at the end
        q->rear = newNode;        // Move rear to new node
    }
    printf("%d enqueued to queue\n", value);
}

২.৪ কিউ থেকে উপাদান অপসারণ করা (Dequeue)

int dequeue(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        struct Node* temp = q->front; // Store current front
        int dequeuedValue = temp->data; // Get data from front
        q->front = q->front->next; // Move front to next node
        if (q->front == NULL) { // If front becomes NULL
            q->rear = NULL; // If queue becomes empty, update rear
        }
        free(temp); // Free the old front
        return dequeuedValue; // Return the dequeued value
    }
}

২.৫ কিউয়ের প্রথম উপাদান দেখা (Peek)

int peek(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->front->data; // Return the front value
    }
}

২.৬ পুরো প্রোগ্রাম উদাহরণ

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;              // Data part
    struct Node* next;     // Pointer to the next node
};

// Queue structure
struct Queue {
    struct Node* front;     // Pointer to the front node
    struct Node* rear;      // Pointer to the rear node
};

// Function to initialize the queue
void initQueue(struct Queue* q) {
    q->front = NULL; // Queue খালি
    q->rear = NULL;  // Queue খালি
}

// Function to enqueue an element to the queue
void enqueue(struct Queue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Create new node
    newNode->data = value;   // Assign data
    newNode->next = NULL;    // Initialize next to NULL

    if (q->rear == NULL) { // If queue is empty
        q->front = newNode; // Both front and rear point to new node
        q->rear = newNode;
    } else {
        q->rear->next = newNode; // Link the new node at the end
        q->rear = newNode;        // Move rear to new node
    }
    printf("%d enqueued to queue\n", value);
}

// Function to dequeue an element from the queue
int dequeue(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow! Cannot dequeue\n");
        return -1; // Return -1 to indicate underflow
    } else {
        struct Node* temp = q->front; // Store current front
        int dequeuedValue = temp->data; // Get data from front
        q->front = q->front->next; // Move front to next node
        if (q->front == NULL) { // If front becomes NULL
            q->rear = NULL; // If queue becomes empty, update rear
        }
        free(temp); // Free the old front
        return dequeuedValue; // Return the dequeued value
    }
}

// Function to peek at the front element of the queue
int peek(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue is empty! No front element\n");
        return -1; // Return -1 to indicate empty queue
    } else {
        return q->front->data; // Return the front value
    }
}

// Main function to demonstrate queue operations
int main() {
    struct Queue queue; // Create a queue
    initQueue(&queue);  // Initialize the queue

    enqueue(&queue, 10); // Enqueue elements
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Front element is %d\n", peek(&queue)); // Peek at front element

    printf("%d dequeued from queue\n", dequeue(&queue)); // Dequeue element
    printf("Front element is now %d\n", peek(&queue)); // Peek at front element

    return 0;
}

Circular Queue এবং Priority Queue হল দুটি বিশেষ ধরনের Queue, যা বিভিন্ন পরিস্থিতিতে ব্যবহার করা হয়। নিচে উভয় কিউ-এর ধারণা এবং প্রয়োগের বিষয়ে আলোচনা করা হলো।

১. Circular Queue

১.১ Circular Queue এর ধারণা

Circular Queue হল একটি Queue যেখানে শেষের উপাদানের পরবর্তী পয়েন্টার প্রথম উপাদানের দিকে নির্দেশ করে। এর ফলে এটি একটি সার্কুলার ফর্ম তৈরি করে, যা কিউয়ের স্থান ব্যবহারকে সর্বাধিক করে।

১.২ Circular Queue এর গঠন

Circular Queue তে প্রধান দুটি সূচক থাকে:

• Front: প্রথম উপাদানের সূচক।
• Rear: শেষ উপাদানের সূচক।

১.৩ Circular Queue এর ব্যবহার

Resources Management:

• সিস্টেমে বিভিন্ন রিসোর্স (যেমন CPU, Memory) নিয়ন্ত্রণের জন্য Circular Queue ব্যবহার করা হয়। এটি সিস্টেমের উভয় প্রান্তের রিসোর্সগুলির প্রতি সমান সুযোগ দেয়।

Round Robin Scheduling:

• অপারেটিং সিস্টেমে প্রক্রিয়ার জন্য Round Robin Scheduling পদ্ধতিতে Circular Queue ব্যবহৃত হয়। প্রতিটি প্রক্রিয়াকে সমান সময় বরাদ্দ করা হয় এবং পরে পরবর্তী প্রক্রিয়াতে চলে যায়।

Buffer Management:

• সার্ভার এবং ক্লায়েন্টের মধ্যে ডেটা স্থানান্তরের সময় Circular Queue ব্যবহার করা হয়। এটি ডেটার একটি ধারাবাহিক প্রবাহ নিশ্চিত করে।

Data Streaming:

• সাউন্ড, ভিডিও বা নেটওয়ার্ক ডেটা প্রবাহিত করার সময় Circular Queue ব্যবহার করা হয়, যেখানে সাম্প্রতিক ডেটা পুরনো ডেটাকে প্রতিস্থাপন করে।

২. Priority Queue

২.১ Priority Queue এর ধারণা

Priority Queue হল একটি বিশেষ ধরনের Queue যেখানে প্রতিটি উপাদানের একটি নির্দিষ্ট অগ্রাধিকার থাকে। সাধারণ Queue এর মতো FIFO পদ্ধতি অনুসরণ না করে, Priority Queue অগ্রাধিকারের ভিত্তিতে উপাদানগুলিকে সারিবদ্ধ করে।

২.২ Priority Queue এর গঠন

Priority Queue সাধারণত একটি Heap বা একটি অর্ডারড লিস্ট দ্বারা বাস্তবায়িত হয়, যেখানে উচ্চ অগ্রাধিকারযুক্ত উপাদানগুলি সর্বদা আগে dequeued হয়।

২.৩ Priority Queue এর ব্যবহার

Job Scheduling:

• বিভিন্ন কাজের অগ্রাধিকার ভিত্তিতে ব্যবস্থাপনার জন্য Priority Queue ব্যবহার করা হয়। যেকোন কাজের উচ্চ অগ্রাধিকার থাকলে সেটি প্রথমে সম্পন্ন হয়।

Pathfinding Algorithms:

• Dijkstra’s Algorithm এবং A* Algorithm এ Priority Queue ব্যবহৃত হয়, যেখানে প্রতিটি নোডের জন্য একটি খরচ নির্ধারণ করা হয় এবং ন্যূনতম খরচের ভিত্তিতে অনুসন্ধান করা হয়।

Data Compression:

• Huffman Coding এর মতো ডেটা কম্প্রেশন অ্যালগরিদমে Priority Queue ব্যবহৃত হয়। এটি প্রতিটি অক্ষরের জন্য তার ফ্রিকোয়েন্সি ভিত্তিতে একটি ট্রি তৈরি করে।

Event Simulation:

• বিভিন্ন ঘটনা বা কার্যকলাপের সময়সীমা অনুযায়ী অগ্রাধিকার সেট করতে Priority Queue ব্যবহার করা হয়, যা সময়ের ভিত্তিতে সঠিক কার্যকলাপ পরিচালনা করে।