কিউ (Queue)

কিউ (Queue) একটি লিনিয়ার ডাটা স্ট্রাকচার যা FIFO (First In First Out) প্রিন্সিপাল অনুসরণ করে। এর মানে হল, প্রথমে প্রবেশ করা উপাদানটি প্রথমে বাহির হবে। কিউতে উপাদানগুলো এক দিকে যুক্ত (enqueue) এবং অন্য দিকে মুছে ফেলা (dequeue) হয়। কিউ সাধারণত বিভিন্ন প্রোগ্রামিং কাজের মধ্যে ব্যবহৃত হয় যেমন প্রসেস সিডিউলিং, ব্যাফারিং, সার্ভার রিকোয়েস্ট প্রসেসিং ইত্যাদি।

কিউ সাধারণত দুইটি প্রধান অপারেশন সম্পাদন করে:

1. enqueue: কিউতে একটি নতুন উপাদান যুক্ত করা।
2. dequeue: কিউ থেকে একটি উপাদান মুছে ফেলা (এবং সেই উপাদানটি ফেরত দেওয়া)।
3. peek বা front: কিউতে সবচেয়ে প্রথম উপাদানটি দেখা (কিন্তু মুছে ফেলা হয় না)।
4. isEmpty: কিউ খালি কি না তা যাচাই করা।
5. size: কিউতে কতগুলো উপাদান আছে তা জানা।

কিউকে সাধারণত অ্যারে বা লিংকড লিস্টের মাধ্যমে ইমপ্লিমেন্ট করা হয়।

কিউ ইমপ্লিমেন্টেশন

এখানে কিউ ক্লাসটি তৈরি করা হয়েছে, যা অ্যারে ব্যবহার করে ইমপ্লিমেন্ট করা হয়েছে।

1. কিউ ক্লাস (Queue Class) - অ্যারে ব্যবহার করে

class Queue {
    int[] queue;
    int front;
    int rear;
    int capacity;
    
    // Constructor to initialize the queue
    public Queue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        front = -1;
        rear = -1;
    }

    // Check if the queue is empty
    public boolean isEmpty() {
        return front == -1;
    }

    // Check if the queue is full
    public boolean isFull() {
        return rear == capacity - 1;
    }

    // Add an element to the queue
    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full!");
        } else {
            if (front == -1) {
                front = 0; // First element to be added
            }
            rear++;
            queue[rear] = item;
            System.out.println(item + " enqueued to the queue");
        }
    }

    // Remove and return an element from the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return -1;
        } else {
            int item = queue[front];
            if (front == rear) {
                front = rear = -1; // Queue becomes empty
            } else {
                front++;
            }
            return item;
        }
    }

    // Get the front element of the queue
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return -1;
        } else {
            return queue[front];
        }
    }

    // Get the size of the queue
    public int size() {
        if (isEmpty()) {
            return 0;
        } else {
            return rear - front + 1;
        }
    }
    
    // Display all elements in the queue
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
        } else {
            System.out.print("Queue: ");
            for (int i = front; i <= rear; i++) {
                System.out.print(queue[i] + " ");
            }
            System.out.println();
        }
    }
}

ক্লাসের ব্যাখ্যা:

• enqueue(int item): কিউতে একটি নতুন উপাদান যুক্ত করে। যদি কিউ পূর্ণ থাকে, এটি একটি ত্রুটি বার্তা প্রদর্শন করে।
• dequeue(): কিউ থেকে প্রথম উপাদানটি মুছে ফেলে এবং তা ফেরত দেয়। যদি কিউ খালি থাকে, একটি ত্রুটি বার্তা দেখানো হয়।
• peek(): কিউর প্রথম উপাদানটি দেখায়, কিন্তু তা মুছে ফেলে না।
• isEmpty(): কিউ খালি কি না তা যাচাই করে।
• isFull(): কিউ পূর্ণ কি না তা যাচাই করে।
• size(): কিউতে কতগুলি উপাদান আছে তা জানায়।
• display(): কিউতে থাকা সব উপাদান প্রিন্ট করে।

কিউ ব্যবহার উদাহরণ

এখন কিউতে কিছু অপারেশন দেখানোর জন্য একটি main মেথড লিখি:

public class QueueDemo {
    public static void main(String[] args) {
        Queue queue = new Queue(5); // Queue with capacity of 5 elements
        
        // Enqueue some elements
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);
        
        // Display the current queue
        queue.display();  // Output: Queue: 10 20 30 40 50
        
        // Try to enqueue when the queue is full
        queue.enqueue(60); // Output: Queue is full!
        
        // Dequeue some elements
        System.out.println("Dequeued: " + queue.dequeue()); // Output: Dequeued: 10
        System.out.println("Dequeued: " + queue.dequeue()); // Output: Dequeued: 20
        
        // Display the current queue
        queue.display();  // Output: Queue: 30 40 50
        
        // Check the front element
        System.out.println("Front element: " + queue.peek());  // Output: Front element: 30
        
        // Get the size of the queue
        System.out.println("Size of the queue: " + queue.size());  // Output: Size of the queue: 3
    }
}

আউটপুট:

10 enqueued to the queue
20 enqueued to the queue
30 enqueued to the queue
40 enqueued to the queue
50 enqueued to the queue
Queue: 10 20 30 40 50 
Queue is full!
Dequeued: 10
Dequeued: 20
Queue: 30 40 50
Front element: 30
Size of the queue: 3

সারাংশ

কিউ (Queue) একটি খুবই গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা FIFO (First In First Out) নিয়ম অনুসরণ করে। এটি ডাটা ইনসার্ট এবং রিমুভ করার জন্য খুবই কার্যকরী, বিশেষত যখন আমাদের প্রসেস সিডিউলিং বা কোনো টাস্ক প্রক্রিয়া করতে হয়। জাভাতে কিউ অ্যারে বা লিংকড লিস্টের মাধ্যমে ইমপ্লিমেন্ট করা যেতে পারে এবং এতে মৌলিক অপারেশন যেমন enqueue, dequeue, peek, size, এবং isEmpty ইত্যাদি কার্যকরভাবে সম্পাদিত হয়।

Queue একটি অর্ডারড ডাটা স্ট্রাকচার যা FIFO (First In First Out) প্রিন্সিপলে কাজ করে, অর্থাৎ যে ডেটা প্রথমে আসে সেটিই প্রথমে বের হয়। এটি একটি line এর মতো কাজ করে, যেখানে এলিমেন্টগুলি একদিকে ইনপুট করা হয় (enqueue) এবং অন্যদিকে আউটপুট করা হয় (dequeue)। ডাটা স্ট্রাকচার হিসেবে Queue অনেক গুরুত্বপূর্ণ, বিশেষত যখন কোনো ডাটা প্রক্রিয়া সিরিয়াল আকারে সম্পন্ন করতে হয়।

এখানে আমরা Queue এর ধারণা এবং এর প্রধান প্রকারভেদ—Simple Queue এবং Circular Queue নিয়ে আলোচনা করব।

1. Queue এর মৌলিক ধারণা

Queue এমন একটি ডাটা স্ট্রাকচার যেখানে ইনপুট এবং আউটপুট দুটি আলাদা অপারেশন থাকে:

• Enqueue: নতুন এলিমেন্ট যোগ করা।
• Dequeue: প্রথমে থাকা এলিমেন্ট সরিয়ে ফেলা।

Queue এর মৌলিক অপারেশন:

1. enqueue(x): x মানের একটি নতুন এলিমেন্ট যুক্ত করা।
2. dequeue(): প্রথমে থাকা এলিমেন্ট সরিয়ে ফেলা।
3. peek(): প্রথম এলিমেন্ট দেখার জন্য (কিন্তু সরানো হয় না)।
4. isEmpty(): Queue খালি কিনা চেক করা।
5. isFull(): Queue পূর্ণ কিনা চেক করা।

Queue এর প্রক্রিয়া খুবই সহজ, এবং এটি সিস্টেমের বিভিন্ন কাজের জন্য ব্যবহৃত হয়, যেমন ব্যাঙ্কের লাইন, অ্যাপ্লিকেশন প্রোগ্রামিং এবং পাইপলাইন ম্যানেজমেন্ট।

2. Simple Queue

Simple Queue হলো একটি সাধারণ Queue যেখানে ইনপুট এলিমেন্ট একদিকে দেওয়া হয় এবং আউটপুট এলিমেন্ট অন্যদিকে পাওয়া যায়। Simple Queue তে প্রথম এলিমেন্ট প্রথমে (FIFO) বের হয়। এটি সাধারণত একটি লিনিয়ার Queue হয়, যেখানে একমাত্র পয়েন্টার (pointer) থাকে।

Simple Queue এর স্ট্রাকচার:

Front -> [Data] -> [Data] -> [Data] -> Rear

এখানে Front হলো Queue এর প্রথম অংশ এবং Rear হলো Queue এর শেষ অংশ।

Simple Queue এর অপারেশন

উদাহরণ: Simple Queue

class Queue {
    int maxSize;
    int front;
    int rear;
    int[] queue;

    // Queue Constructor
    public Queue(int size) {
        maxSize = size;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
    }

    // Enqueue Operation
    public void enqueue(int value) {
        if (rear == maxSize - 1) {
            System.out.println("Queue is Full");
        } else {
            if (front == -1) front = 0;
            rear++;
            queue[rear] = value;
            System.out.println(value + " enqueued");
        }
    }

    // Dequeue Operation
    public void dequeue() {
        if (front == -1 || front > rear) {
            System.out.println("Queue is Empty");
        } else {
            System.out.println(queue[front] + " dequeued");
            front++;
        }
    }

    // Peek Operation
    public void peek() {
        if (front == -1 || front > rear) {
            System.out.println("Queue is Empty");
        } else {
            System.out.println("Front Element: " + queue[front]);
        }
    }

    // Check if Queue is Empty
    public boolean isEmpty() {
        return (front == -1 || front > rear);
    }
}

public class SimpleQueueExample {
    public static void main(String[] args) {
        Queue q = new Queue(5);

        // Enqueue some elements
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);

        // Peek the front element
        q.peek();

        // Dequeue an element
        q.dequeue();

        // Check if Queue is empty
        System.out.println("Is Queue Empty: " + q.isEmpty());
    }
}

ব্যাখ্যা:

• Enqueue: enqueue() মেথডে নতুন এলিমেন্ট যোগ করা হয়।
• Dequeue: dequeue() মেথডে প্রথম এলিমেন্ট সরানো হয়।
• Peek: peek() মেথডে প্রথম এলিমেন্ট দেখা যায়, কিন্তু সরানো হয় না।
• isEmpty: isEmpty() মেথডে Queue খালি কিনা তা চেক করা হয়।

3. Circular Queue

Circular Queue হলো এমন একটি Queue যেখানে rear এবং front পয়েন্টার একই জায়গায় মিলিত হতে পারে। এতে Queue শেষ হওয়ার পরও ডেটা জায়গা নিয়ে পুনরায় ফিরে আসে। অর্থাৎ, যখন queue এর rear পয়েন্টার শেষে চলে যায়, তখন সেটি আবার প্রথম দিকে ফিরে যায় এবং নতুন এলিমেন্ট অ্যাড করতে পারে। এটি সাধারণভাবে একরকম সার্কুলার (চক্রাকার) স্ট্রাকচার হয়।

Circular Queue এর স্ট্রাকচার:

Front -> [Data] -> [Data] -> [Data] -> Rear
                   (Circular Connection)

এখানে Front হলো Queue এর প্রথম অংশ এবং Rear হলো Queue এর শেষ অংশ, এবং rear যখন শেষের দিকে চলে আসে তখন এটি আবার প্রথম দিকে ফিরে আসে।

Circular Queue এর অপারেশন

উদাহরণ: Circular Queue

class CircularQueue {
    int maxSize;
    int front;
    int rear;
    int[] queue;

    // Constructor
    public CircularQueue(int size) {
        maxSize = size;
        queue = new int[maxSize];
        front = -1;
        rear = -1;
    }

    // Enqueue Operation
    public void enqueue(int value) {
        if ((rear + 1) % maxSize == front) {
            System.out.println("Queue is Full");
        } else {
            if (front == -1) front = 0;
            rear = (rear + 1) % maxSize;
            queue[rear] = value;
            System.out.println(value + " enqueued");
        }
    }

    // Dequeue Operation
    public void dequeue() {
        if (front == -1) {
            System.out.println("Queue is Empty");
        } else {
            System.out.println(queue[front] + " dequeued");
            if (front == rear) {
                front = rear = -1;
            } else {
                front = (front + 1) % maxSize;
            }
        }
    }

    // Peek Operation
    public void peek() {
        if (front == -1) {
            System.out.println("Queue is Empty");
        } else {
            System.out.println("Front Element: " + queue[front]);
        }
    }

    // Check if Queue is Empty
    public boolean isEmpty() {
        return (front == -1);
    }
}

public class CircularQueueExample {
    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(5);

        // Enqueue some elements
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);

        // Peek the front element
        q.peek();

        // Dequeue an element
        q.dequeue();

        // Check if Queue is empty
        System.out.println("Is Queue Empty: " + q.isEmpty());
    }
}

ব্যাখ্যা:

• Circular Queue: enqueue() এবং dequeue() মেথডে Circular Queue-এর মূল ধারণা ব্যবহৃত হয়েছে, যেখানে rear এবং front পয়েন্টার চক্রাকারে চলতে থাকে।
• Rear Pointer: rear পয়েন্টারকে (rear + 1) % maxSize ব্যবহার করে চক্রাকারভাবে বাড়ানো হয়েছে, যাতে এটি শেষ হওয়ার পর আবার প্রথম দিকে ফিরে আসে।

4. Queue এর সুবিধা ও ব্যবহার

সুবিধা:

• FIFO (First In First Out): Queue এর মাধ্যমে আপনি সিস্টেমের কার্যক্রম FIFO ভিত্তিতে পরিচালনা করতে পারেন।
• ডাইনামিক মেমরি ব্যবস্থাপনা: Queue ডাইনামিকভাবে মেমরি ব্যবস্থাপনা করতে সহায়ক, বিশেষত যখন ডাটা প্রক্রিয়াকরণে প্রয়োজন হয়।

ব্যবহার:

• Process Scheduling: অপারেটিং সিস্টেমে টাস্ক বা প্রক্রিয়া সাজানোর জন্য Queue ব্যবহার করা হয়।
• Message Queues: মেসেজ প্রক্রিয়া এবং পাঠানোর জন্য Queue ব্যবহৃত হয়।
• Printer Queue: প্রিন্টার কাজের জন্য Queue ব্যবহার করা হয়।
• Data Buffering: ডাটা স্টোরেজ এবং ট্রান্সফার কাজে Queue ব্যবহৃত হয়।

Queue একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা FIFO (First In First Out) প্রিন্সিপল অনুসরণ করে। Simple Queue এবং Circular Queue হল এর দুই প্রাথমিক ধরনের। Queue দিয়ে আপনি বিভিন্ন কাজ যেমন প্রক্রিয়া সিডিউলিং, মেসেজ ট্রান্সফার, ডাটা স্টোরেজ ইত্যাদি কার্যকরীভাবে করতে পারেন। Java দিয়ে Queue তৈরি এবং ব্যবহারের মাধ্যমে আপনি ডাটা স্ট্রাকচার এবং অ্যালগরিদমের ভিত্তি শক্তিশালী করতে পারবেন।

Queue কি?

Queue হল একটি অ্যাবস্ট্র্যাক্ট ডেটা টাইপ (ADT) যা FIFO (First In, First Out) নীতি অনুসরণ করে। এর মানে হল যে প্রথমে যে উপাদানটি ইনসার্ট হবে, সেটিই প্রথমে আউটপুট হবে। এটি বাস্তব জীবনে ব্যবহারিক সমস্যাগুলির জন্য উপযোগী, যেমন প্রিন্টার জব, কল সেন্টার সিস্টেম, এবং প্রক্রিয়াকরণ সিস্টেমের জন্য।

Queue মূলত দুটি প্রধান অপারেশন সাপোর্ট করে:

1. enqueue (ইনসার্ট): একটি উপাদান কোয়েতে যোগ করা।
2. dequeue (ডিলিট): কোয়েত থেকে একটি উপাদান সরানো।

এছাড়া, peek অপারেশনও থাকে যা কোয়েরির প্রথম উপাদান দেখাতে সাহায্য করে এবং isEmpty অপারেশন কোয়েটি খালি কিনা তা চেক করে।

1. Queue ইমপ্লিমেন্টেশন using Array

এখানে Array ব্যবহার করে একটি Queue ইমপ্লিমেন্ট করার উদাহরণ দেখানো হচ্ছে। আমরা একটি নির্দিষ্ট সাইজের অ্যারে ব্যবহার করব যা সীমাবদ্ধ থাকবে।

উদাহরণ: Queue ইমপ্লিমেন্টেশন using Array

public class QueueUsingArray {
    private int[] queue;
    private int front, rear, size;

    // Constructor to initialize queue
    public QueueUsingArray(int capacity) {
        queue = new int[capacity];
        size = 0;
        front = 0;
        rear = -1;
    }

    // Enqueue operation
    public void enqueue(int value) {
        if (size == queue.length) {
            System.out.println("Queue is full");
            return;
        }
        rear = (rear + 1) % queue.length; // Circular increment
        queue[rear] = value;
        size++;
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = queue[front];
        front = (front + 1) % queue.length; // Circular increment
        size--;
        return value;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return queue[front];
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Display the queue elements
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        int i = front;
        while (i != rear) {
            System.out.print(queue[i] + " ");
            i = (i + 1) % queue.length;
        }
        System.out.println(queue[rear]);
    }
}

public class Main {
    public static void main(String[] args) {
        QueueUsingArray queue = new QueueUsingArray(5);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);
        
        System.out.println("Queue elements:");
        queue.display();  // Output: 10 20 30 40 50

        System.out.println("Dequeue element: " + queue.dequeue());  // Output: 10
        queue.display();  // Output: 20 30 40 50
        
        System.out.println("Peek element: " + queue.peek());  // Output: 20
    }
}

ব্যাখ্যা:

• Enqueue: কোয়েতে একটি উপাদান যোগ করা হয়, তবে যদি কোয়ে পূর্ণ থাকে, এটি একটি ত্রুটি বার্তা প্রদর্শন করবে।
• Dequeue: কোয়েতে প্রথম উপাদান সরিয়ে ফেলা হয় এবং এটি সার্বিক সাইজ কমিয়ে দেয়।
• Peek: প্রথম উপাদানটি কেবল দেখা হয়, তবে এটি কোয়েত থেকে সরানো হয় না।
• Circular Queue: এখানে সাইক্লিক আর্গুমেন্ট ব্যবহার করা হয়েছে, যাতে কোয়েতে স্থান পূর্ণ হওয়ার পরও পুরনো স্থানে নতুন উপাদান যোগ করা যায়।

2. Queue ইমপ্লিমেন্টেশন using Linked List

এখন আমরা Linked List ব্যবহার করে একটি Queue ইমপ্লিমেন্ট করব। Linked List-based Queue একটি dynamic queue হতে পারে, যেটি কোনো নির্দিষ্ট সাইজের সীমা ছাড়াই কাজ করতে পারে।

উদাহরণ: Queue ইমপ্লিমেন্টেশন using Linked List

public class QueueUsingLinkedList {
    private Node front, rear;
    private int size;

    // Node class
    private class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Constructor
    public QueueUsingLinkedList() {
        front = rear = null;
        size = 0;
    }

    // Enqueue operation
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return value;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return front.data;
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return front == null;
    }

    // Display the queue elements
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        QueueUsingLinkedList queue = new QueueUsingLinkedList();

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        
        System.out.println("Queue elements:");
        queue.display();  // Output: 10 20 30 40

        System.out.println("Dequeue element: " + queue.dequeue());  // Output: 10
        queue.display();  // Output: 20 30 40
        
        System.out.println("Peek element: " + queue.peek());  // Output: 20
    }
}

ব্যাখ্যা:

• Node class: Node ক্লাসে প্রতিটি নোডের জন্য ডেটা এবং পরবর্তী নোডের রেফারেন্স থাকে।
• Enqueue: যখন নতুন উপাদান ইনসার্ট করা হয়, তখন একটি নতুন নোড তৈরি করা হয় এবং রিয়ার পয়েন্টার সেট করা হয়।
• Dequeue: ফ্রন্ট নোড থেকে উপাদান সরিয়ে ফেলা হয় এবং ফ্রন্ট পয়েন্টার আপডেট করা হয়।
• Peek: ফ্রন্ট নোডের ডেটা দেখানো হয়, কিন্তু এটি কোয়েত থেকে সরানো হয় না।
• Display: লিঙ্কড লিস্ট ট্রাভার্স করে কোয়েরির উপাদানগুলো প্রদর্শন করা হয়।

3. Singly Linked List Queue vs Array-based Queue

সারাংশ

Queue হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা FIFO (First In, First Out) নীতি অনুসরণ করে। আমরা Array এবং Linked List ব্যবহার করে Queue ইমপ্লিমেন্ট করতে পারি। Array-based Queue সীমাবদ্ধ আকারে কাজ করে, তবে Linked List-based Queue ডাইন

ামিক এবং সুবিধাজনক হতে পারে। ডেটা স্ট্রাকচার এবং অ্যালগরিদম এর মধ্যে কোড অপটিমাইজেশন এবং অ্যাক্সেসের ক্ষেত্রে দুটি পদ্ধতিরই নিজস্ব সুবিধা ও সীমাবদ্ধতা রয়েছে।

Priority Queue এবং Deque (Double-Ended Queue) হল এমন দুটি ডাটা স্ট্রাকচার, যা কিছু বিশেষ ধরনের ডেটা অপারেশন পরিচালনার জন্য ব্যবহৃত হয়। Priority Queue সাধারণত Queue ডাটা স্ট্রাকচারের একটি বিশেষ রূপ যেখানে উপাদানগুলো তাদের প্রাধান্য অনুসারে সাজানো থাকে, এবং Deque হল এমন একটি Queue যা দুই প্রান্ত থেকে উপাদান যোগ বা মুছতে সক্ষম।

এখানে আমরা Priority Queue এবং Deque এর ধারণা, তাদের ব্যবহার, এবং তাদের Java তে কিভাবে ব্যবহার করা যায় তা আলোচনা করব।

1. Priority Queue

Priority Queue হল একটি বিশেষ ধরনের কিউ ডাটা স্ট্রাকচার, যেখানে প্রতিটি উপাদান একটি নির্দিষ্ট প্রাধান্য বা প্রাধান্য মানের ভিত্তিতে রাখা হয়। কিউতে উপাদান যোগ করার সময়, তাদের প্রাধান্য অনুযায়ী তাদের অবস্থান ঠিক করা হয়, এবং সাধারণত min-heap বা max-heap ব্যবহার করে এই প্রাধান্য সিস্টেমটি কার্যকর করা হয়।

1.1. Priority Queue এর বৈশিষ্ট্য

• Priority-based ordering: উপাদানগুলির একটি নির্দিষ্ট প্রাধান্য থাকে এবং কিউতে সর্বোচ্চ বা সর্বনিম্ন প্রাধান্যযুক্ত উপাদান আগে বের করা হয়।
• Min-heap বা Max-heap এর মাধ্যমে এর কার্যকারিতা নিশ্চিত করা হয়। Min-heap ব্যবহার করলে সর্বনিম্ন প্রাধান্য উপাদান বের হবে, আর Max-heap ব্যবহার করলে সর্বোচ্চ প্রাধান্য উপাদান বের হবে।

1.2. Priority Queue এর ব্যবহার

• Task Scheduling: যখন বিভিন্ন টাস্কের জন্য বিভিন্ন প্রাধান্য সেট করা হয়, যেমন অপারেটিং সিস্টেমের স্কেজুলিং বা ব্যাচ প্রসেসিং।
• Dijkstra’s Algorithm: গ্রাফ অ্যালগরিদমে সর্বনিম্ন দূরত্ব খুঁজে বের করার জন্য।
• Huffman Encoding: কম্প্রেশন অ্যালগরিদমে।

1.3. Priority Queue Example in Java

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Adding elements to the priority queue
        pq.add(10);
        pq.add(5);
        pq.add(20);
        pq.add(15);

        // Printing the priority queue elements (min-heap)
        System.out.println("Priority Queue (Min-Heap): ");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

ব্যাখ্যা:

• এখানে, PriorityQueue একটি min-heap হিসাবে কাজ করছে, যেখানে সবচেয়ে কম মানের উপাদান আগে বের হবে।
• poll() মেথড ব্যবহার করা হয়েছে PriorityQueue থেকে উপাদান বের করার জন্য, যা স্বয়ংক্রিয়ভাবে সর্বনিম্ন মানের উপাদান বের করে।

আউটপুট:

Priority Queue (Min-Heap): 
5
10
15
20

2. Deque (Double-Ended Queue)

Deque (Double-Ended Queue) একটি ডাটা স্ট্রাকচার যা Queue এর একটি উন্নত সংস্করণ। এতে আপনি Queue এর মতো সাধারণভাবে উপাদান যোগ বা মুছতে পারেন, তবে এই ডাটা স্ট্রাকচারে আপনি দুই প্রান্ত থেকেই (অর্থাৎ front এবং rear) উপাদান যোগ বা মুছতে পারেন। এটি খুবই উপকারী যখন আপনি এমন পরিস্থিতি বা অ্যালগরিদমে কাজ করেন যেখানে দুটি প্রান্তের কাছ থেকে উপাদান হ্যান্ডলিং করতে হয়।

2.1. Deque এর বৈশিষ্ট্য

• Two-ended operation: আপনি Deque এর শুরু এবং শেষে ডাটা যোগ বা মুছতে পারেন।
• FIFO (First-In-First-Out) and LIFO (Last-In-First-Out): এটি Queue এবং Stack উভয়ের বৈশিষ্ট্য ধারণ করে, কারণ আপনি Deque তে উপাদান যোগ এবং মুছতে পারেন যেকোনো প্রান্ত থেকে।

2.2. Deque এর ব্যবহার

• Deque as a Stack: Deque এর মাধ্যমে আপনি Stack তৈরি করতে পারেন, যেখানে উপাদান LIFO পদ্ধতিতে প্রবাহিত হবে।
• Deque as a Queue: আপনি এটি Queue হিসেবেও ব্যবহার করতে পারেন, যেখানে উপাদানগুলি FIFO পদ্ধতিতে প্রবাহিত হবে।
• Sliding Window: এটি এমন পরিস্থিতিতে ব্যবহৃত হয় যেখানে আপনি ডেটার একটি সাবসেটের উপর অপারেশন করছেন এবং সেটি স্লাইডিং উইন্ডোর মতো পরিবর্তিত হচ্ছে।

2.3. Deque Example in Java

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        // Create a Deque
        Deque<Integer> deque = new ArrayDeque<>();

        // Adding elements at the front and rear
        deque.addFirst(10);  // Add 10 at the front
        deque.addLast(20);   // Add 20 at the rear
        deque.addFirst(5);   // Add 5 at the front
        deque.addLast(25);   // Add 25 at the rear

        // Printing the deque elements
        System.out.println("Deque elements: " + deque);

        // Removing elements from the front and rear
        deque.removeFirst(); // Remove from front
        deque.removeLast();  // Remove from rear

        System.out.println("Deque after removal: " + deque);
    }
}

ব্যাখ্যা:

• এখানে, ArrayDeque ব্যবহার করা হয়েছে যা Deque এর একটি ইমপ্লেমেন্টেশন।
• addFirst() এবং addLast() মেথডের মাধ্যমে উপাদান যোগ করা হয়েছে, প্রথমে এবং পরে।
• removeFirst() এবং removeLast() মেথডের মাধ্যমে উপাদান সরানো হয়েছে, প্রথম এবং পরে।

আউটপুট:

Deque elements: [5, 10, 20, 25]
Deque after removal: [10, 20]

3. Priority Queue vs Deque

সারাংশ

• Priority Queue হল একটি বিশেষ ধরনের কিউ যেখানে উপাদানগুলি তাদের প্রাধান্য অনুসারে সাজানো থাকে এবং সবচেয়ে বেশি প্রাধান্যযুক্ত উপাদান দ্রুত বের হয়ে আসে। এটি সাধারণত task scheduling, graph algorithms, এবং compression algorithms তে ব্যবহৃত হয়।
• Deque হল এমন একটি কিউ যা দুটি প্রান্ত থেকে উপাদান যোগ বা মুছতে পারে, অর্থাৎ আপনি FIFO বা LIFO উভয় পদ্ধতি অনুসরণ করতে পারেন। এটি সাধারণত sliding window, queue, এবং stack হিসেবেও ব্যবহৃত হতে পারে।

দুটি ডাটা স্ট্রাকচারই Java তে খুবই কার্যকরী এবং বিভিন্ন পরিস্থিতিতে ব্যবহার করা যেতে পারে। Priority Queue এবং Deque উভয়েই Java Collections Framework এর অংশ, যা ডাটা স্ট্রাকচার এবং অ্যালগরিদম সম্পর্কিত বিভিন্ন সমস্যা সমাধান করতে সহায়ক।

Queue একটি FIFO (First In, First Out) ডাটা স্ট্রাকচার, যেখানে প্রথমে আসা উপাদানটি প্রথমে বের হয়ে যায়। এটি এমন কিছু সমস্যার সমাধান করতে সাহায্য করে যেখানে এলিমেন্টগুলো একে একে প্রসেস করা প্রয়োজন, যেমন Breadth-First Search (BFS) এবং Print Jobs।

এই গাইডে আমরা Queue এর ব্যবহার কিভাবে Breadth-First Search (BFS) এবং Print Jobs মডেল করতে সাহায্য করে তা দেখবো।

1. Queue এর মৌলিক ধারণা

Queue একটি ডাটা স্ট্রাকচার, যা দুটি মৌলিক অপারেশন সমর্থন করে:

• enqueue: একটি উপাদান কোডের শেষে যোগ করা।
• dequeue: কোডের শুরুর থেকে উপাদানটি বের করা।

Queue সাধারণত দুইটি জায়গায় কাজ করে:

1. front: প্রথম উপাদান যেখানে থাকে।
2. rear: শেষ উপাদান যেখানে যোগ করা হয়।

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // Enqueue
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // Dequeue
        System.out.println("Dequeued: " + queue.poll()); // Output: 1

        // Peek at the front element
        System.out.println("Front element: " + queue.peek()); // Output: 2
    }
}

এখানে, LinkedList ব্যবহার করা হয়েছে Queue ইন্টারফেসের জন্য। add() মেথড দিয়ে ইনকিউ করতে এবং poll() মেথড দিয়ে ডিকিউ করতে হয়। peek() মেথড দ্বারা প্রথম উপাদান দেখতে পারি।

2. Breadth-First Search (BFS) with Queue

Breadth-First Search (BFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা Queue ব্যবহার করে। এটি প্রথমে বর্তমান নোডের পাশের নোডগুলো একে একে পরিদর্শন করে। Queue এর সাহায্যে, BFS একটি স্তরের সব নোড পরিদর্শন করে এবং পরবর্তী স্তরের নোডগুলোকে প্রসেস করে।

2.1. BFS Implementation using Queue

import java.util.*;

public class BFS {
    // Graph representation using adjacency list
    private Map<Integer, List<Integer>> adjList;

    public BFS() {
        adjList = new HashMap<>();
    }

    // Add edges to the graph
    public void addEdge(int u, int v) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(v);
        adjList.get(v).add(u); // For undirected graph
    }

    // BFS traversal
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        visited.add(start);
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            
            // Traverse the adjacent nodes
            for (int neighbor : adjList.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS graph = new BFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);
        
        System.out.print("BFS traversal starting from node 1: ");
        graph.bfs(1); // Output: 1 2 3 4 5 6
    }
}

2.2. Explanation of BFS using Queue:

• প্রথমে স্টার্ট নোডকে visited সেটে যোগ করা হয় এবং queue এ যুক্ত করা হয়।
• তারপর, queue এর মধ্যে থেকে একে একে নোড বের করা হয় এবং তার প্রতিবেশী নোডগুলোকে visited চেক করে queue তে যোগ করা হয়।
• এভাবে, BFS পুরো গ্রাফকে স্তরানুসারে পরিদর্শন করে।

Queue ব্যবহার করার কারণে BFS অ্যালগরিদম FIFO নীতিতে কাজ করে, অর্থাৎ প্রথমে যোগ হওয়া নোডটি আগে পরিদর্শন করা হয়।

3. Print Jobs with Queue

Print Jobs মডেল করার জন্যও Queue ব্যবহার করা যেতে পারে। ধরুন, একটি প্রিন্টার সার্ভার আছে যেখানে অনেক প্রিন্ট জব পেন্ডিং রয়েছে। Queue-এর সাহায্যে আমরা এগুলিকে প্রসেস করতে পারি, প্রথমে যে প্রিন্ট জব এসেছে সেটি আগে প্রিন্ট হবে।

3.1. Print Jobs Simulation Using Queue

import java.util.LinkedList;
import java.util.Queue;

public class PrintJobQueue {
    static class PrintJob {
        String document;
        int pages;

        PrintJob(String document, int pages) {
            this.document = document;
            this.pages = pages;
        }
    }

    public static void main(String[] args) {
        // Creating a Queue for print jobs
        Queue<PrintJob> printQueue = new LinkedList<>();
        
        // Adding print jobs to the queue
        printQueue.add(new PrintJob("Document1.pdf", 10));
        printQueue.add(new PrintJob("Document2.pdf", 15));
        printQueue.add(new PrintJob("Document3.pdf", 5));

        // Process each print job in the queue
        while (!printQueue.isEmpty()) {
            PrintJob job = printQueue.poll();  // Get the next print job
            System.out.println("Printing: " + job.document + " (" + job.pages + " pages)");
            // Simulate printing process
        }
    }
}

3.2. Explanation:

• PrintJob ক্লাসে একটি ডকুমেন্ট এবং তার পেজ সংখ্যা থাকে।
• Queue ব্যবহার করে, আমরা প্রিন্ট জবগুলো যুক্ত করি।
• poll() মেথড ব্যবহার করে প্রথম প্রিন্ট জবটি বের করা হয় এবং প্রিন্ট করা হয়।

এখানে Queue FIFO পদ্ধতিতে কাজ করে, যেখানে প্রথমে আসা প্রিন্ট জবটি আগে প্রিন্ট হবে।

4. Complex Example: Combining BFS and Print Jobs

ধরা যাক, আমরা একটি পরিস্থিতি তৈরি করতে চাই যেখানে গ্রাফের নোডগুলি প্রিন্ট জব হিসেবে ব্যবহৃত হবে এবং BFS অ্যালগরিদমের মাধ্যমে তাদের প্রক্রিয়া করা হবে।

4.1. BFS with Print Jobs

import java.util.*;

public class BFSWithPrintJobs {
    static class PrintJob {
        String document;
        int pages;

        PrintJob(String document, int pages) {
            this.document = document;
            this.pages = pages;
        }

        @Override
        public String toString() {
            return document + " (" + pages + " pages)";
        }
    }

    static class Graph {
        private Map<Integer, List<Integer>> adjList = new HashMap<>();

        // Add an edge to the graph
        public void addEdge(int u, int v) {
            adjList.putIfAbsent(u, new ArrayList<>());
            adjList.putIfAbsent(v, new ArrayList<>());
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        // BFS with Print Job Simulation
        public void bfsWithPrintJobs(int start) {
            Queue<Integer> queue = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            Queue<PrintJob> printQueue = new LinkedList<>();

            visited.add(start);
            queue.add(start);

            // Simulate adding print jobs for each node
            printQueue.add(new PrintJob("Print Job for Node " + start, 10));

            while (!queue.isEmpty()) {
                int node = queue.poll();
                PrintJob currentJob = printQueue.poll();
                System.out.println("Processing print job: " + currentJob);

                // Traverse adjacent nodes and add print jobs
                for (int neighbor : adjList.get(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.add(neighbor);
                        printQueue.add(new PrintJob("Print Job for Node " + neighbor, 5)); // Assigning 5 pages for simplicity
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);

        System.out.println("BFS with Print Jobs Simulation:");
        graph.bfsWithPrintJobs(1);
    }
}

4.2. Explanation:

• এখানে, আমরা BFS ট্রাভার্সাল ব্যবহার করেছি এবং প্রতিটি নোডের জন্য PrintJob তৈরি করেছি।
• PrintJob একে একে প্রিন্ট হচ্ছে, এবং নোডের পাশের নোডগুলোর জন্য নতুন প্রিন্ট জব তৈরি হচ্ছে।

সারাংশ

Queue একটি অত্যন্ত শক্তিশালী ডাটা স্ট্রাকচার যা BFS (Breadth-First Search) এবং Print Jobs মডেলিং এর মতো বিভিন্ন কাজে ব্যবহৃত হয়। BFS গ্রাফ ট্রাভার্সাল এবং Print Jobs-এ কুয়েরি পরিচালনা করতে FIFO প্রক্রিয়ায় কাজ করে। এই প্রোগ্রামগুলি কিভাবে Queue ব্যবহার করে ডাটা প্রসেস এবং প্রিন্ট জবসমূহ পরিচালনা করা যায় তা দেখায়।

Key Takeaways:

• Queue হল FIFO ডাটা স্ট্রাকচার।
• BFS গ্রাফ ট্রাভার্সাল করতে Queue ব্যবহার করা হয়।
• Print Jobs মডেল করতে Queue ব্যবহৃত হয় যেখানে প্রথমে আসা জবটি প্রথমে প্রিন্ট করা হয়।