কিউ কি?

ধরো তুমি বাসের টিকেট কিনে লাইনে দাঁড়িয়ে আছো। এখন বাসে ওঠাটা হচ্ছে আমার কাজ(প্রসেসিং)। কাকে আগে বাসে উঠতে দিবে? যে সবার আগে এসেছে, তাকে। এটাকে বলে কিউ - যে সবার আগে এসেছে তাকে আগে প্রসেস করা। queue< int > q; q.push( 100 ); // inserting 100 q.push( 101 ); // inserting 101 q.push( 102 ); // inserting 102 while( !q.empty() ) { cout << q.front() << endl; // printing the front q.pop(); // removing that one }

কিউ হল কতগুলো আইটেমের এমন এক ধারাবাহিক সংগ্রহশালা (কালেকশন - collection) যেখানে নতুন আইটেমের সংযোজন (এনকিউ – enqueue) সংগ্রহশালার এক প্রান্তে আর পুরনো আইটেমের অপসারণ (ডিকিউ - dequeue) ঠিক তার বিপরীত প্রান্তে হয়। বোঝার সুবিধার্থে, যে প্রান্তে নতুন আইটেমের সংযোজন হয় সে প্রান্তকে আমরা পিছনের অংশ বা রিয়ার (rear) অথবা টেইল (tail - লেজ) বলতে পারি। আর যে প্রান্তে পুরনো আইটেমের অপসারণ হয় সে প্রান্তকে আমরা সামনের অংশ বা ফ্রন্ট (front) অথবা হেড (head - মাথা) বলতে পারি। বেশ গোলমেলে ব্যাপার-স্যাপার, তাই না? দুশ্চিন্তা করার কোন কারণ নেই। একটা গল্প বললেই বিষয়টা পরিষ্কার হয়ে যাবে।

বিদ্যুৎ বিল দেবার শেষ তারিখ চলে এসেছে, অথচ তখনো আমাদের বিদ্যুৎ বিল দেয়া হয়নি। অন্যদিকে কায়িক পরিশ্রম না করার কারণে আমার শরীরও ফুলে ঢোল হয়ে গিয়েছে। আম্মাজান দুয়ে দুয়ে চার মিলিয়ে ফেললেন। হাতে বিদ্যুৎ বিল ধরিয়ে দিয়ে আমাকে ব্যাংকে পাঠিয়ে দিলেন। যাতায়াত খরচ না দেয়ার কারণে হেঁটে হেঁটেই ব্যাংকে আসতে হল। গিয়ে দেখলাম, বিদ্যুৎ বিলের বুথের সামনে চারজনের একটা লাইন। তড়িঘড়ি করে লাইনে দাঁড়িয়ে পাঁচ নাম্বারে আমার অবস্থান নিশ্চিত করলাম। বুথের ভদ্রলোক একজন-একজন করে বিল নিচ্ছেন। সময় কাটানোর জন্য কি করা যেতে পারে ভাবতে লাগলাম। শেষমেষ গুনগুন করে গান গাওয়া শুরু করলাম,”কবে আইবে আমার পালা রে…।" আশ্চর্য ফলাফল পেলাম। পুরো গান শেষ হতে না হতেই আমার পালা চলে এলো। ততক্ষণে অবশ্য আমার পিছনে আরো দুইজন এসে গিয়েছে। কিন্তু আমার আগে বিল দেয়ার সুযোগ নেই তাদের। ব্যাংকের নিয়ম অত্যন্ত কড়া। আমার পরেই তারা সুযোগ পাবে। অবশেষে বিল দিয়ে নাচতে নাচতে বাসায় চলে আসলাম। বিল দিতে গিয়ে কিউ ডাটা স্ট্রাকচারের বাস্তবিক উদাহরণ পেয়েছি - এটাই নাচা-নাচির কারণ।

উপরের চিত্রে আমরা একটি পূর্ণদৈর্ঘ্য কিউ কাহিনী দেখতে পাচ্ছি। প্রাথমিকভাবে, প্রথম জন হচ্ছে আমাদের কিউয়ের হেড আর চতুর্থ জনের ডান পাশের ঘরটা হচ্ছে টেইল। পঞ্চম জন (আইটেম)-কে আমরা যদি আমাদের কিউয়ে এনকিউ (সংযোজন) করতে চাই তবে তা টেইলে করতে হবে। আর পঞ্চম জন (আইটেম) এনকিউ হয়ে যাবার পরে টেইল কিন্তু এক ঘর ডানে সরে আসবে। অর্থাৎ পঞ্চম জনের ডান পাশের ঘরটা হবে নতুন টেইল। আবার ডিকিউ (অপসারণ) করার সময় হেডকে সবার আগে ডিকিউ করতে হবে। ঘটনাচক্রে, হেডে রয়েছে প্রথম জন, তাই প্রথম জনকেই সবার আগে ডিকিউ করতে হবে। প্রথম জনকে ডিকিউ করা হয়ে গেলে উক্ত ঘর ফাঁকা হয়ে যাবে, তাই হেড এক ঘর ডানে সরে আসবে। তখন নতুন হেডে থাকবে দ্বিতীয় জন। আচ্ছা, এই জন কি অভিনেতা জন? নাকি এই জন দিয়ে মানুষজন বুঝানো হয়েছে? এটা কুইজ। যে সবার আগে উত্তর দিতে পারবে সে একটা হাওয়াই চকলেট পাবে।

উপরের চিত্রটা দেখে একটা বিষয় তো আমরা সবাই কম-বেশি বুঝে ফেলেছি যে, কিউ একটি ফার্স্ট-ইন-ফার্স্ট-আউট (FIFO) ডাটা স্ট্রাকচার। কারণ, সবার আগে যে ঢুকছে সেই সবার আগে বের হচ্ছে। অনেকটা 'আগে আসলে আগে পাবেন' (ফার্স্ট-কাম-ফার্স্ট-সার্ভড) টাইপের অবস্থা।