মডিউল ১৫-৬ঃ Reverse Stack Using Recursion (CodingNinjas)

প্রবলেম লিংকঃ Reverse Stack Using Recursion

প্রবলেম স্টেটমেন্টঃ ইনপুটে একটি স্ট্যাক থাকবে। রিকারশন দিয়ে এই স্ট্যাক রিভার্স করতে হবে। সল্যুশনঃ আমরা প্রতিবার স্ট্যাক এর টপের ভেলু রেখে দিয়ে স্ট্যাককে পপ করে দিয়ে তারপর রিকারশন কল করে দিতে পারি। রিকারশনে আমরা নতুন একটি স্ট্যাক নিয়ে তাতে পূর্বের সব ভেলু পুশ করে তারপর রিকারশন কল করার আগে যেই টপ এর ভেলু আমরা সেইভ করে রেখেছিলাম তা পুশ করে দিতে পারি। এরপর সেই স্ট্যাক থেকে আবার পূর্বের স্ট্যাকে নিয়ে আসলে রিভার্স হয়ে যাবে। এভাবে রিকারশন শেষে সম্পূর্ণ স্ট্যাক রিভার্স হয়ে যাবে।

void reverseStack(stack<int> &s)
{
    if (s.empty())        // স্ট্যাক এম্পটি না হওয়া পর্যন্ত রিকারশন চলবে।
        return;
    int x = s.top();      // স্ট্যাকের টপের ভেলু সেইভ করে রাখা হচ্ছে। 
    s.pop();              // স্ট্যাক পপ করে দেওয়া হচ্ছে। 
    reverseStack(s);      // টপের ভেলু পপ করার পর রিকারশন কল করে স্ট্যাককে দিয়ে দেওয়া হচ্ছে।
    stack<int> cp;        // নতুন স্ট্যাক নেওয়া হচ্ছে। 
    while (!s.empty())    // পূর্বের স্ট্যাক থেকে নতুন স্ট্যাকে ভেলু পুশ করা হচ্ছে। 
    {
        cp.push(s.top()); 
        s.pop();
    }
    cp.push(x);           // টপের ভেলু যেটি সেইভ করে রাখা হয়েছিল তা পুশ করা হচ্ছে নতুন স্ট্যাকে। 
    while (!cp.empty())   // নতুন স্ট্যাক থেকে পূর্বের স্ট্যাকে ভেলু পুশ করা হচ্ছে। 
    {
        s.push(cp.top());
        cp.pop();
    }
}