25. Queue - Basics

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

---

1. Queue কি? (FIFO Principle)

কিউ-কে আপনি একটি টিকিট কাউন্টারের লাইনের সাথে তুলনা করতে পারেন। লাইনে যে সবার আগে এসে দাঁড়ায়, তাকেই সবার আগে সেবা দেওয়া হয়।

---

2. মূল অপারেশনসমূহ (Core Operations)

1. Enqueue: কিউ-এর পেছনে (Rear) নতুন এলিমেন্ট যোগ করা।
2. Dequeue: কিউ-এর সামনে (Front) থেকে এলিমেন্ট সরিয়ে ফেলা।
3. Front: কিউ-এর প্রথম এলিমেন্টটি দেখা।
4. Rear: কিউ-এর শেষ এলিমেন্টটি দেখা।
5. isEmpty / isFull: কিউ খালি বা পূর্ণ কি না তা চেক করা।

---

3. সার্কুলার অ্যারে দিয়ে ইমপ্লিমেন্টেশন (Circular Array Implementation)

সাধারণ অ্যারে দিয়ে কিউ বানালে অনেক মেমরি নষ্ট হয় (সামনে জায়গা খালি থাকলেও নতুন ডেটা ঢোকানো যায় না)। এর সমাধান হলো Circular Queue।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• Enqueue: প্রথমে চেক করুন কিউ ফুল কি না (কন্ডিশন: (rear + 1) % size == front)। যদি না হয়, তবে rear = (rear + 1) % size করে ডেটা রাখুন।
• Dequeue: চেক করুন কিউ খালি কি না। যদি না হয়, তবে front = (front + 1) % size করে ডেটা রিমুভ করুন।

Implementation

// Java Circular Queue
class Queue {
    int front = -1, rear = -1, size = 5;
    int arr[] = new int[size];
    void enqueue(int x) {
        if ((rear + 1) % size == front) return;
        if (front == -1) front = 0;
        rear = (rear + 1) % size;
        arr[rear] = x;
    }
    int dequeue() {
        if (front == -1) return -1;
        int res = arr[front];
        if (front == rear) front = rear = -1;
        else front = (front + 1) % size;
        return res;
    }
}

# Python Circular Queue
class CircularQueue:
    def __init__(self, n):
        self.size = n
        self.queue = [None] * n
        self.front = self.rear = -1
    def enqueue(self, data):
        if (self.rear + 1) % self.size == self.front: return
        if self.front == -1: self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = data
    def dequeue(self):
        if self.front == -1: return None
        res = self.queue[self.front]
        if self.front == self.rear: self.front = self.rear = -1
        else: self.front = (self.front + 1) % self.size
        return res

Broadway

4. লিঙ্কড লিস্ট দিয়ে ইমপ্লিমেন্টেশন (Linked List Implementation)

ডাইনামিক মেমরি ম্যানেজমেন্টের জন্য লিঙ্কড লিস্ট ব্যবহার করা হয়। এখানে দুটি হেড ব্যবহার করা সুবিধাজনক: front এবং rear।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• Enqueue: নতুন একটি নোড তৈরি করুন। একে rear.next-এ সেট করে rear কে নতুন নোডে সরিয়ে নিন।
• Dequeue: front কে তার পরের নোডে সরিয়ে দিন (front = front.next)।

Implementation

// Java Queue using Linked List
class QueueLL {
    Node front, rear;
    class Node {
        int data; Node next;
        Node(int d) { data = d; }
    }
    void enqueue(int x) {
        Node newNode = new Node(x);
        if (rear == null) { front = rear = newNode; return; }
        rear.next = newNode;
        rear = newNode;
    }
    int dequeue() {
        if (front == null) return -1;
        int res = front.data;
        front = front.next;
        if (front == null) rear = null;
        return res;
    }
}

# Python Queue using Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = self.rear = None
    def enqueue(self, data):
        new_node = Node(data)
        if not self.rear:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node
    def dequeue(self):
        if not self.front: return None
        res = self.front.data
        self.front = self.front.next
        if not self.front: self.rear = None
        return res

Broadway

5. কিউ ওভারফ্লো এবং আন্ডারফ্লো (Overflow & Underflow)

• Queue Overflow: যখন ফুল কিউ-তে নতুন ডেটা এঙ্কু (Enqueue) করার চেষ্টা করা হয়।
• Queue Underflow: যখন খালি কিউ থেকে ডেটা ডিঙ্কু (Dequeue) করার চেষ্টা করা হয়।

---

6. কিউ-এর ব্যবহার (Applications)

• CPU Scheduling: মাল্টিপল প্রসেসকে এক এক করে সময় দেওয়ার জন্য।
• Shared Resources: প্রিন্টার বা ডিস্কের কাজ সিরিয়াল অনুযায়ী করার জন্য।
• BFS (Breadth-First Search): গ্রাফ বা ট্রিতে লেভেল অনুযায়ী ট্রাভার্স করার জন্য।
• Request Handling: ওয়েবসাইট বা সার্ভারে ট্র্যাফিক ম্যানেজ করতে।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Peek (Front)	O(1)
Search	O(n)

---

IMPORTANT

স্ট্যাকের মতো কিউ-এর সব মূল অপারেশন (Enqueue/Dequeue) সবসময় O(1) সময়ে সম্পন্ন হয়।

---

TIP

রিয়েল-টাইম প্রজেক্টে মেমরি বাঁচাতে Circular Queue বা Linked List Implementation ব্যবহার করা সবচেয়ে কার্যকর।