স্ট্যাক দিয়ে কিউ তৈরি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৩

সমস্যাঃ স্ট্যাক (Stack) ব্যবহার করে কিউ (Queue) তৈরি করতে হবে, অর্থাৎ কিউ এর এনকিউ (enqueue) ও ডিকিউ (dequeue) ফাংশন তৈরি করতে হবে।

সমাধানঃ প্রথমে একটু চিন্তা করলেই আমরা বুঝতে পারবো যে একটি স্ট্যাক দিয়ে আসলে একটি কিউ তৈরি করা সম্ভব নয়। যদি সম্ভব হতো, তাহলে এই দুটি আলাদা ডেটা স্ট্রাকচার হতো না। কিন্তু যেহেতু সমস্যা দেওয়া হয়েছে, সমাধান নিশ্চয়ই আছে। সমাধান হচ্ছে, দুটি স্ট্যাক ব্যবহার করা।

নোটঃ স্ট্যাক ও কিউ নিয়ে আমি বিস্তারিত আলোচনা করেছি, কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে। এছাড়া ইউটিউবেও এ বিষয়ে আলোচনা  করেছি ডেটা স্ট্রাকচার ও অ্যালগরিদম প্লেলিস্টে

ধরা যাক, কিউতে প্রথমে আমি পাঁচটি সংখ্যা রাখতে চাই, অর্থাৎ enqueue অপারেশন হবে পাঁচবার এবং সংখ্যাগুলো হচ্ছে – 1, 2, 3, 4, 5. আমি এগুলো প্রথম স্ট্যাকে পুশ (push) করব।

এখন আমি চাই, কিউ থেকে প্রথম তিনটি সংখ্যা সরিয়ে ফেলতে, অর্থাৎ তিনবার dequeue অপারেশন হবে। তাহলে কিউ থেকে যথাক্রমে 1, 2, 3 – এই তিনটি সংখ্যা চলে যাবে। কিন্তু স্ট্যাক থেকে তো কেবল ওপরের সংখ্যাটি সরানো যায়। তাহলে, আমি প্রথম স্ট্যাকের সবগুলো সংখ্যা দ্বিতীয় স্ট্যাকে নিয়ে আসব। তখন স্ট্যাকগুলোর অবস্থা হবে নিচের ছবির মতো –

এখন আমি দ্বিতীয় স্ট্যাকে তিনবার পপ (pop) অপারেশন চালালে 1, 2, 3 স্ট্যাক থেকে চলে যাবে। তখন স্ট্যাকদুটির অবস্থা হবে নিচের ছবির মতো –

এখন আমি কিউতে 6 ও 7 ক্রমানুসারে রাখতে চাই। আমি সেগুলো প্রথম স্ট্যাকে পুশ করবো।

এখন কিউ-এর অবস্থা হচ্ছে এমন: 4, 5, 6, 7. আমি যদি কিউ থেকে তিনটি সংখ্যা সরিয়ে নিই (অর্থাৎ তিনবার ডিকিউ করি), সেগুলো হবে, যথাক্রমে 4, 5, 6। ডিকিউ করার জন্য আমি প্রথমে দেখবো যে দ্বিতীয় স্ট্যাকে কিছু আছে কী না। যদি থাকে, সেই স্ট্যাক থেকে পপ করবো। আর যদি stack2 খালি থাকে, তাহলে Stack1-এর সব কিছু Stack2-তে নিয়ে আসবো (তখন দ্বিতীয় স্ট্যাকে সেগুলো প্রথম স্ট্যাকের বিপরীত ক্রমে থাকবে)। তারপরে দ্বিতীয় স্ট্যাক থেকে পপ করবো।

আশা করি, সমাধানটি নিজের পছন্দমতো প্রোগ্রামিং ভাষায় ইমপ্লিমেন্ট করতে সমস্যা হবে না। সমাধান সঠিক হলো কী না, তা যাচাই করার জন্য নিচের যেকোনো একটি লিঙ্কে গিয়ে সমাধান জমা দিলেই হবে –

Facebook Comments

Leave a Reply