১৪-১,১৪-২ঃ Queue কী এবং Queue এর কিছু বাস্তব উদাহরণ

Queue এর বাংলা অর্থ হলো লাইন বা সারি । অর্থাৎ, আমাদের যদি কখনো প্রয়োজন হয় এমন একটি ডাটা স্ট্রাকচার এর যা লাইন বা সারির মতো করে কাজ করবে সেই ক্ষেত্রে আমরা Queue ডাটা স্ট্রাকচার ব্যবহার করতে পারি। আসুন জেনে নেয়া যাক , একটি সারি বা লাইন কীভাবে কাজ করে। ধরুন , আপনি Phitron এ বিকালের সাপোর্ট সেশন নিতে আসলেন । এসে একটি ফর্ম ফিলাপ করার পর দেখতে পেলেন আপনার সিরিয়াল নাম্বার হলো ১০। অর্থাৎ , আপনি ১০ জন মানুষের পর নিজের ফর্ম টি ফিলাপ করেছেন। এখন , সাপোর্ট সেশনে জয়েন করে দেখতে পেলেন , যে সবার আগে ফর্ম ফিলাপ করেছিলো তাকে ইন্সট্রাকটর সবার আগে কল করে তার সমস্যাটি সমাধান করে দিয়েছেন । সে সমাধান পেয়ে সাপোর্ট থেকে চলে যাওয়ার পর ২য় নাম্বারে যে ফর্ম ফিলাপ করেছে তাকে ইন্সট্রাকটর কল করে তার সমস্যাটি সমাধান করে দিয়েছে। এরপর তৃতীয় , চতুর্থ করে করে একের পর এক Student এর প্রবলেম সল্ভ করা হচ্ছিলো। এখানে ১৫ নাম্বার পজিশন থেকে কেও এসে ৪ নাম্বার এ যে আছে তার আগে সাপোর্ট নেয়ার কোনো সুযোগ ছিলো না।

এই ধরণের লাইন বা সারি মেইনটেন করে যে ডাটা স্ট্রাকচার , সেটি হলো Queue. Queue হলো এমন একটি ডাটা স্ট্রাকচার যা , FIFO ( First In Firt Out) মেথড টি ফলো করে থাকে। অর্থাৎ Queue এর মধ্যে যে ভ্যালুটি সবার আগে আসবে , এক্সেস করার ক্ষেত্রে বা প্রসেসিং এর ক্ষেত্রে সেই ভ্যালুটি সবার আগে থাকবে। প্রসেসিং এর পর এই ভ্যালুটি সবার আগে Queue থেকে বের হয়ে যাবে। ঠিক Phitron এর সাপোর্ট সেশন এর মতো। এবং নতুন কোনো ভ্যালু ঐ Queue তে যুক্ত হতে চাইলে সেটি Queue এর শেষে যুক্ত হবে। অর্থাৎ নতুন কেও সাপোর্ট এর জন্য আসলে তাকে সবার শেষে লাইনে দাঁড়াতে হবে। Queue কে বলা হয় Abstract Data Structure. অর্থাৎ Queue অন্যান্য basic ডাটা স্ট্রাকচার যেমন array , linked list এগুলার মাধ্যমে তৈরি হয়। মোটামুটি Queue তে একটি ভ্যালু তার শেষে এড করা যায় যাকে আমরা push বলি, এরপর Queue এর প্রথম থেকে কোনো ভ্যালু এক্সেস করি এবং Delete করতে পারি যাকে আমরা বলি pop. আর বাকি গুলো যেমন প্রথম ভ্যালু এক্সেস করা , সাইজ জানা এগুলা বেসিক অপারেশন যা সব DS এর জন্য প্রায় একই হয়। আসুন এইবার দেখে নেয়া যাক কোন কোন basic বা প্রাইমারি data structure দ্বারা Queue ইমপ্লিমেন্ট করা সবচেয়ে ভালো হবে । Array , Singly Linked List এবং Doubly Linked List এর কিছু তুলনা করা যাক।

DS	Insertion (push)	Delete from beginning (pop)
Array	O(1)	O(n)
Singly Linked List	O(1)	O(1)
Doubly Linked List	O(1)	o(1)

এখানে দেখা যাচ্ছে Queue এর প্রধান অপারেশন গুলো Array দ্বারা করা ইফিশিয়েন্ট হবে না। তাই আমরা Singly and Doubly দিয়ে Queue ইমপ্লিমেন্ট করা শিখবো