কিউ (Queue)
কিউ হচ্ছে একটি রৈখিক লিস্ট, যেটিকে আমরা যে কোন টিকেট কাউন্টারের ব্যবস্থাপনার সাথে তুলনা করতে পারি।
যে আগে আসবে আগে সার্ভিস পাবে বা টিকেট পাবে, ঠিক এরকমই কিউ এর অপারেশন গুলো।
একেই আমরা বলে থাকি ফিফো (First in first out)
এনকিউ (enqueue) বা পুশ হল কিউতে নতুন উপাদান যোগ করা এবং ডিকিউ বা পপ হল সব থেকে আগে থাকা বা আগে আসা উপাদান যেটি কিউতে বর্তমান আছে সেটিকে সরিয়ে ফেলা লিস্ট থেকে।
কিউতে পুশ করা কাজটি করা হয় rear বা back সাইড দিয়ে। এটিকে টেইল (tail) ও বলা হয়।
ডিলেট করার কাজটি ফ্রন্ট (front) সাইড দিয়ে করা হয়। এটাকে হেড (head) ও বলা হয়।
আর এভাবেই কিউতে FIFO অপারেশন পরিচালিত হয়।
কোথায় কোথায় কিউ ব্যবহৃত হয়?
- Single Shared Resource, যেমন সিপিউ টাস্ক সিডিউলিং
- কল সেন্টারে কল হোল্ড করে রাখার প্রসেস
- রিয়েল টাইম সিস্টেমে বিভিন্ন ইন্টারাপ্ট হ্যান্ডেলিং এর জন্যে
কিউ কিভাবে কাজ করে?
এরে, লিংকড লিস্ট, স্ট্যাক ব্যবহার করে কিউ ইমপ্লিমেন্ট করা যায়।
এরে ব্যবহার করে খুব সহজেই কিউ ইমপ্লিমেন্ট করা যায়। যেহেতু প্রথমে কিউতে কোন উপাদান থাকে না তাই হেড এবং টেইল দুটিই এরে এর প্রথম ইন্ডেক্স কে ইন্ডিকেট করবে। যখনি আমরা কিউতে উপাদান যোগ করতে থাকব, টেইল সামনে আগাতে থাকবে। টেইল নতুন উপাদান যোগ করার স্থান টি নির্দেশ করে। কিন্তু হেড সব সময় কিউতে থাকা প্রথম উপাদানের ইন্ডেক্সকেই ইন্ডিকেট করে থাকে।
উপরের ডায়াগ্রাম দেখে আমরা সহজেই বুঝতে পারি একটি কিউতে এনকিউ এবং ডিকিউ এর মত কাজ গুলো কিভাবে ঘটে এবং কিভাবে তাদের মধ্যকার হেড এবং টেইলের পজিশনের পরিবর্তন ঘটে।
১) শুরুতে কিউতে কোন ডাটা নেই। তাই হেড এবং টেইলের পজিশন কিউ লিস্টের বাহিরে।
২) ২য় চিত্রে আমরা একটি ইলিমেন্ট প্রবেশ করিয়েছি।
৩) তারপর আমরা ধাপে ধাপে আরো ৩ টি এলিমেন্ট কে পুশ বা এনকিউ করেছি। এখন আমরা ডায়াগ্রাম ভাল করে লক্ষ্য করলে একটি জিনিস দেখব, এখানে হেড এবং টেইলের পজিশন এক নয়। কেননা হেড কিউ লিস্টে থাকা প্রথম এলিমেন্টের পজিশন নির্দেশ করে।
এবং টেইল নির্দেশ করে কিউ লিস্টের সবচেয়ে নতুন এলিমেন্টের পজিশন।
৪-৫) আমরা এখন প্রথম এলিমেন্ট টি ডিকিউ করব। এতে করে কিউ তে প্রথম এলিমেন্ট হবে ২য় স্থান করা এলিমেন্ট টি। তাই হেডের পজিশন ও পরিবর্তন হয়েছি। কিন্তু টেইলের পজিশন আগের মতই আছে।
৬) যখন আমরা ৩ টি এলিমেন্ট ডিকিউ করি তখন লক্ষ্য করলে দেখতে পারি যে হেডের অবস্থান এখন টেইলের আগে।
অর্থাৎ এখন আমরা নতুন কোন এলিমেন্ট এনকিউ করলে তার অবস্থান হবে হেডের সেই অবস্থান।
তাছাড়া হেড > টেইল বলতে বুঝায় কিউ লিস্টে কোন উপাদান নেই।
আমরা এখন এনকিউ অপারেশন ঘটালে টেইলের পজিশন এক বেড়ে হেড এবং টেইল একই পজিশন নির্দেশ করবে।
এই ডায়াগ্রাম টি এরে লিস্ট ব্যবহার করা একটি কিউ এর উদাহরণ।
এই ডায়াগ্রাম দেখে আমরা বুঝতে পারছি, এরে তে খালি স্থান জায়গা গুলো আর ব্যবহার করতে পারব না (সেখানে আর এনকিউ অপারেশন ঘটাতে পারব না)।
তাই এতে করে বিশাল কিউ এর জন্যে এরে ব্যবহার না করাই শ্রেয়।
এতে প্রচুর মেমোরি লস হয়। কেননা। সেখানে কোন উপাদান না রাখলেও, এরে লিস্টের জন্যে সেগুলো মেমোরি থেকে জায়গা দখল করে রেখেছে।
তাই লিংকড লিস্ট ব্যবহার করে কিউ ইমপ্লিমেন্ট করাই শ্রেয়।