Queue Data Structure: ধারণা ও কাজকর্ম
Queue (কিউ) হলো একটি অ্যাবস্ট্রাক্ট ডেটা স্ট্রাকচার যা স্ট্যাকের মতোই কিন্তু এর দুটি এন্ড খোলা থাকে। এক প্রান্তে ডেটা ইনসার্ট হয় (Enqueue) এবং অন্য প্রান্ত থেকে ডেটা রিমুভ হয় (Dequeue)।
FIFO Principle (First-In-First-Out)
কিউ First-In-First-Out (FIFO) পদ্ধতি ফলো করে — যেটি প্রথমে ইনসার্ট হয়েছে, সেটিই প্রথমে বের হবে। এটি একটি সিংগেল-লেন ワン-ওয়ে রোডের মতো: যে গাড়িটি আগে ঢুকেছে, সেটিই আগে বের হবে।
কিউর মূল অপারেশনসমূহ
| অপারেশন | বর্ণনা | টাইম কমপ্লেক্সিটি (Array-based) |
|---|---|---|
| Enqueue | রিয়ার/টেইলে এলিমেন্ট যোগ করা | O(1) — push() |
| Dequeue | ফ্রন্ট/হেড থেকে এলিমেন্ট সরানো | O(n) — shift() (রিইন্ডেক্সিং) |
| Peek/Front | হেড এলিমেন্ট দেখা (রিমুভ ছাড়া) | O(1) — container[0] |
| isEmpty | কিউ খালি কিনা চেক | O(1) |
| isFull | কিউ ফুল কিনা চেক (ক্যাপাসিটি লিমিট থাকলে) | O(1) |
| size | বর্তমান এলিমেন্ট সংখ্যা | O(1) |
রিয়েল-ওয়ার্ল্ড উদাহরণ
- প্রিন্ট কিউ: ডকুমেন্ট প্রিন্টারের জন্য অপেক্ষা করে।
- কাস্টমার সার্ভিস লাইন: ফোন কল বা কাউন্টার লাইন।
- CPU টাস্ক শিডিউলিং: প্রসেসর কিউ।
- BFS (Breadth-First Search): গ্রাফ/ট্রি ট্রাভার্সাল।
- বাফার/ক্যাশ: ডেটা স্ট্রিম হ্যান্ডলিং।
- মেসেজ কিউ সিস্টেম: RabbitMQ, Kafka, Redis Queues।
ভিজ্যুয়াল রিপ্রেজেন্টেশন
FRONT (Head) REAR (Tail) ↓ ↓ [ 10 ] → [ 20 ] → [ 30 ] → [ 40 ] → [ 50 ] ↑ ↑ Dequeue() Enqueue() (Remove) (Add)
নোট: উপরের ডায়াগ্রামে ১০ সবচেয়ে আগে ইনসার্ট হয়েছিল, তাই এটি ফ্রন্টে আছে এবং প্রথমে ডিকিউ হবে।
কিউ vs স্ট্যাক
| বৈশিষ্ট্য | Queue (FIFO) | Stack (LIFO) |
|---|---|---|
| ইনসারশন এন্ড | রিয়ার (টেইল) | টপ |
| রিমUভাল এন্ড | ফ্রন্ট (হেড) | টপ |
| অর্ডার | প্রথম ইন, প্রথম আউট | লাস্ট ইন, ফার্স্ট আউট |
| উদাহরণ | লাইন, প্রিন্ট কিউ | অনডো স্ট্যাক, ফাংশন কল |
জাভাস্ক্রিপ্টে নেটিভ অ্যারে হিসেবে কিউ
// নেটিভ অ্যারে মেথড দিয়ে কিউ ব্যবহার
const queue = [];
// Enqueue
queue.push(1);
queue.push(2);
queue.push(3);
// Peek
console.log(queue[0]); // 1
// Dequeue
console.log(queue.shift()); // 1
console.log(queue); // [2, 3]
// Size
console.log(queue.length); // 2
// isEmpty
console.log(queue.length === 0); // false
সুবিধা: কোনো ক্লাস লাগে না, বিল্ট-ইন মেথড।
অসুবিধা: ক্যাপাসিটি লিমিট নেই, Underflow/Overflow অটো হ্যান্ডল নেই, সেমান্টিক ক্লারিটি কম।
