ডাটা স্ট্রাকচার: কিউ এবং সার্কুলার কিউ

কিউ একটা বেসিক ডাটা স্ট্রাকচার। এটাকে তুমি চিন্তা করতে পারো বাসের লাইনের মত, যে সবার সামনে দাড়িয়ে আছে সে সবার আগে উঠবে, নতুন কোনো যাত্রী আসলে সে লাইনের পিছনে দাড়াবে।

কিউতে দুইরকম অপারেশন থাকে। এনকিউ(Enqueue) মানে হলো কিউতে নতুন এলিমেন্ট যোগ করা এবং ডিকিউ(Dequeue) বা পপ মানে হলো সবথেকে পুরোনো এলিমেন্টটা কিউ থেকে সরিয়ে ফেলা।

অ্যারে ব্যবহার করে আমরা ফিক্সড সাইজের কিউ ইমপ্লিমেন্ট করতে পারি। আমাদেরকে সবসময় দুইটা পয়েন্টার রাখতে হবে, হেড (Head) পয়েন্টার নির্দেশ করবে কিউয়ের সামনের এলিমেন্টের পজিশন এবং টেইল (Tail) পয়েন্টার নির্দেশ করবে পিছনের এলিমেন্টের পজিশন। একদম শুরুতে Head = -1, Tail = -1 রাখতে পারো। প্রতিটি এলিমেন্ট এনকিউ করার সময় টেইলকে এক পজিশন সামনে এগিয়ে নিয়ে সেই পজিশনে নতুন এলিমেন্টকে রাখতে হবে। ডিকিউ করার সময় শুধুমাত্র হেড একধাপ এগিয়ে নিতে হবে। একটা সিমুলেশন দেখলেই ব্যাপারটা পরিষ্কার হবে:

queue

লক্ষ কর, শেষের এলিমেন্টটা ডিকিউ করার পর হেড টেইলের এর সামনে চলে গেছে। এতে কোনো সমস্যা নাই, Head > Tail বা Head = -1 মানে হলো কিউটা পুরোপুরি খালি।

উপরের কিউতে সর্বোচ্চ ৫টা এলিমেন্ট রাখা যাবে। কিন্তু আরো বড় একটা সমস্যা আছে। Head বা Tail সবসময় সামনে আগাচ্ছে এবং ডিকিউ করার সময় অ্যারের যে জায়গাটা ফাকা হয়ে যাচ্ছে সেটা দ্বিতীয়বার ব্যবহার করার কোনো উপায় নেই! সর্বশেষ ধাপে Tail = 2 হয়ে গিয়েছে, যদিও কিউটা খালি। তারমানে প্রথম ৩টা পজিশন আর ব্যবহার করতে পারবে না। এই কারণে বাস্তবে কখনোই এভাবে কিউ ইমপ্লিমেন্ট করা হয় না, করলে মেমরির সর্বোচ্চ ব্যবহার করতে পারবে না।

একটা সমাধান হলো লিংকড লিস্ট ব্যবহার করা। লিংকড লিস্ট ব্যবহার করলে প্রথম সুবিধা হলো কিউ এর সাইজ ফিক্সড করে দেয়া দরকার নেই। আরেকটা সুবিধা হলো তুমি যখন ডিকিউ করবে তখন টেইল পয়েন্টার যে এলিমেন্টকে পয়েন্ট করে আছে তাকে মেমরি থেকে মুছে দিতে পারবে। লিংকড লিস্ট ব্যবহার করে একটা সিমুলেশন দেখি।

 

queue22

আমরা দেখতে পাচ্ছি এখানে কোন মেমরি অপচয় হবার সুযোগ নেই।

ফিক্সড সাইজের অ্যারে দিয়েও এমনভাবে কিউ ইমপ্লিমেন্ট করা যাতে মেমরি অপচয় না হয়। একে বলা হয় সার্কুলার কিউ যা দেখতে অনেকটা এরকম:

queue31

সার্কুলার কিউতে তুমি শুরুতে যেকোনো পজিশনে এনকিউ করতে পারো, উদাহরণ হিসাবে ছবিতে 2 নম্বর ইনডেক্সকে স্টার্টিং পয়েন্ট ধরেছি। আগের মতোই কিউ 10, 20 এবং 30 এনকিউ করার পর দেখতে হবে এরকম:

 

queue33ডিকিউ ও একই ভাবে করবো:

queue35এখন মনে করো কিউটা সম্পূর্ণ ভরে গেছে:

queue37

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

এখন প্রশ্ন হলো কিভাবে বুঝবে যে সার্কুলার কিউ ফুল হয়ে গেছে নাকি? কিউ ফুল হলে অবশ্যই টেইলের পজিশন হেডের এক ধাপ পিছনে হবে। সার্কুলার কিউ এর একটা পাইথন কোড দেখ:

আরেক ধরণের কিউ আছে যার নাম ডাবল এন্ডেড কিউ। ডাবল এন্ডেড কিউ এর দুই পাশেই এলিমেন্ট প্রবেশ করানো যায়, আবার দুইদিক থেকেই পপ করা যায়। ডাবল এন্ডেড কিউ দিয়ে সমাধান করা যায় এমন একটা মজার সমস্যা আলোচনা করেছি স্লাইডিং রেঞ্জ মিনিমাম কুয়েরি নিযে লেখায়

প্রায়োরিটি কিউ নামের আরও এক ধরণের কিউ আছে। সেখানে প্রতিটা এলিমেন্টের একটা প্রায়োরিটি থাকে, পপ করার সময় যার প্রায়োরিটি বেশি সে আগে পপ হয়। প্রায়োরিটি কিউ ইমপ্লিমেন্ট করতে হলে হিপ ডাটা স্ট্রাকচার সম্পর্কে জানতে হবে, সেটা নিয়ে আরেকদিন আলোচনা করবো।

প্রোগ্রামিং কনটেস্টে কিউ এর সবথেকে কমন ব্যবহার হলো ব্রেথড ফার্স্ট সার্চ । প্রায়োরিটি কিউ ব্যবহার করে ডায়াক্সট্রা অ্যালগোরিদম ইমপ্লিমেন্ট করা হয়। আবার অপারেটিং সিস্টেম বিভিন্ন রকমের কিউ ব্যবহার করে টাস্ক শিডিউলিং এর জন্য।

প্রতিটি বড় প্রোগ্রামিং ল্যাংগুয়েজেই কিউ লাইব্রেরি আছে যা দিয়ে খুব সহজে কিউ ব্যবহার করা যায়। কিন্তু শেখার সময় নিজেকে অবশ্যই ইম্প্লিমেন্ট করতে হবে, নাহলে কিউ কিভাবে কাজ করে বুঝতে পারবে না।

আজ এই পর্যন্তই, হ্যাপি কোডিং!

Print Friendly

ফেসবুকে মন্তব্য

comments

Powered by Facebook Comments

8,434 বার পড়া হয়েছে

Leave a Reply

Your email address will not be published. Required fields are marked *


Time limit is exhausted. Please reload CAPTCHA.