১৪-৭ঃImplement Stack using Queue (Leetcode)

এই পেজে আমরা Leetcode হতে একটি Interesting প্রবলেম সল্ভ করবো । আমরা Stack এর মডিউলে দেখেছি কীভাবে প্রাইমারী ডাটা স্ট্রাকচার যেমন array , doubly linked list এর সাহায্যে Stack ইমপ্লিমেন্ট করা শিখেছি । এই পেজে আমরা শিখবো , কীভাবে Queue ডাটা স্ট্রাকচার কে ব্যবহার করে Stack ইমপ্লিমেন্ট করা যায়। প্রবলেম লিঙ্কঃ https://leetcode.com/problems/implement-stack-using-queues/description/ প্রবলেম স্টেট্মেন্ট এ বলা আছে আপনাকে একটি MyStack ক্লাস দেয়া আছে , যেখানে stack এর মেইন মেইন ফাংশন যেমনঃ push , pop , top , empty এই সকল ফাংশন কমপ্লিট করতে হবে। এবং এই ফাংশন গুলা কমপ্লিট করার ক্ষেত্রে Stack এর কোনো concept ব্যবহার করা যাবে না। এই ক্ষেত্রে শুধু মাত্র দুটি queue এর সাহায্যে এই ফাংশন গুলোতে কাজ করতে হবে। আমরা ভাগ ভাগ করে প্রত্যেকটি function নিয়ে আলোচনা করবো ।

1. push( int x ) : এই ফাংশনে একটি ইন্টিজার x প্যারামিটার হিসেবে পাস করা হবে। এখন চিন্তা করা যাক , যদি একটি stack এ একটি ভ্যালু পুশ করতে বলা হয় তবে সেটি stack এর শেষে insert হয়ে যাবে । আমরা যদি queue তে একটি ভ্যালু পুশ করি , সেক্ষেত্রে ভ্যালুটি queue এর শেষে insert হয়ে যাবে । যেহেতু stack এবং queue এর ক্ষেত্রে এই কাজ টি একই , তাই এক্ষেত্রে queue এর মধ্যে normally ভ্যালু পুশ করে দিলেই হয়ে যাবে ।

2. pop() : এই ফাংশন স্ট্যাক এর শেষ element টি Remove করে দেয়। এবং সেই ভ্যালুটি প্রিন্ট করে। আমরা জানি , যেহেতু Stack , LIFO ফলো করে তাই , stack এর সর্বশেষে যে ভ্যালুটি insert হয়েছে তা সবার আগে রিমুভ হয়ে যাবে। কিন্তু Queue এর ক্ষেত্রে যে ভ্যালুটি সবার আগে Queue তে এসেছে তা আগে remove হবে । তাই এই pop এর কাজ টি queue তে normal way তে করা যাবে না। সলিউশনঃ এই ক্ষেত্রে আমাদের দুটি Queue এর সাহায্য নিতে হবে । চিন্তা করলে দেখা যায় , একটি Queue Q1 হতে যদি আরেকটি Queue Q2 তে ভ্যালু গুলা একেক করে push করা হয় তবে সেক্ষেত্রে Q1 এবং Q2 উভয় একদম সমান হবে। এই concept টি ব্যবহার করে আমরা একটি কাজ করতে পারি। যেহেতু Queue এর সর্বশেষ ভ্যালুটি stack এর শেষ ভ্যালু। তাই আমরা প্রথম Queue এর শেষ ভ্যালুর আগে পর্যন্ত সব ভ্যালুকে আরেকটি Queue তে Temporarily রাখবো । এবং Original Queue এর শেষ ভ্যালুটি পপ করে দিবো। এরপর Original Queue তে Temporary Queue টি এসাইন করে দিবো । শেষ ভ্যালু কোনটি বুঝার জন্য আমরা queue এর empty ফাংশনের সাহায্য নিবো।

1. top() : এই ফাংশন টি stack এর সবার উপরের ভ্যালু অর্থাৎ শেষে যে ভ্যালুটি এসেছে তা রিটার্ন করে । যেহেতু Queue এর front ফাংশন ঐ queue তে যে ভ্যালুটি সবার শেষে ঢুকেছে তা রিটার্ন করে , তাই এইক্ষেত্রে সরাসরি Queue এর ফাংশন গুলো দিয়ে এই কাজ টি করা যাবে না Solution: এই ক্ষেত্রে আমরা Queue এর সাহায্যে stack এর pop ইমপ্লিমেন্ট করার যে মেথড টি দেখেছি তার মতো করে একটি temporary queue ক্রিয়েট করে original queue থেকে সব ভ্যালু temporary queue তে পুশ করতে থাকবো। পুশ করতে করতে যখন দেখবো queue এর শেষ element এ এসে গেছি তখন বুঝতে পারবো এই ভ্যালুটি stack এর top ভ্যালু , কারণ এই ভ্যালুটি queue এ সবার শেষে এসেছে। আর সবার শেষের ভ্যালুটি stack এর top ভ্যালু। এই ক্ষেত্রে top value টি কেও আবার temporary queue তে রাখবো, এবং সবশেষে Original Quete তে temporary queue এসাইন করে দিবো।

2. empty()ঃ এই ফাংশন টি stack টি খালি কিনা তা চেক করবে। stack এবং queue উভয় এর ক্ষেত্রে তারা খালি থাকলে True রিটার্ন করবে। তাই আমরা normally Queue এর সাহায্যে এই কাজটি করে ফেলতে পারবো।

এখন কোড দেখে নেয়া যাক।

Code:

class MyStack
{
public:
    queue<int> q;  // একটি queue নিচ্ছি যা globally সব ফাংশনে ব্যবহার করা যাবে 
    MyStack()
    {
    }

    void push(int x)
    {
        q.push(x); // Stack এবং Queue এর পুশ করা একই। দুটি container এর শেষে ভ্যালু এড হয়
    }

    int pop()
    {
        queue<int> newQ; // আরেকটি Temporary queue নিলাম। যেখানে কিছুক্ষনের জন্য original queue টি স্টোর করে রাখবো 
        int last; // queue এর last ভ্যালু অর্থাৎ stack এর top ভ্যালু রাখার জন্য ভ্যারিয়েবল নিয়ে নিলাম  
        while (!q.empty()) 
        {
            int k = q.front(); // queue এর ভ্যালু গুলা এক এক করে নিয়ে k তে রাখছি
            q.pop(); //  এবং queue থেকে remove করে দিচ্ছি 
            if (q.empty())  // যদি দেখি কারেন্ট ভ্যালুটি queue থেকে বের করে দেয়ার পর queue টি খালি হয়ে গেছে
            {
                // last element
                last = k; // তার মানে সেই ভ্যালুটি হলো queue এর last element 
                break; // এই ক্ষেত্রে আমরা ভ্যালুটি কে temporary queue তে স্টোর করে রাখবো না। অর্থাৎ এটি সরাসরি remove করে দেয়া হয়েছে
            }
            newQ.push(k); // যদি এটি শেষ ভ্যালু না হয়ে থাকে তবে এটি  permanently ডিলিট হবে না তাই  ঐ ভ্যালুটি আমরা temporary queue তে রাখবো 
        }
        q = newQ; // সবশেষে original queue তে temporary queue এর ভ্যালু গুলো আবার রেখে দিবো 
        return last; // সবশেষে সেই ভ্যালুটি রিটার্ন করে দিবো 
    }

    int top()
    {
        queue<int> newQ;
        int last;
        while (!q.empty())
        {
            int k = q.front();
            q.pop();
            if (q.empty())
            {
                // last element
                last = k;
            } // pop ফাংশনের মতো সবকিছু একই এই ফাংশনে শুধু মাত্র এখানে ভিন্নতা আছে।
            // যেহেতু top() ফাংশন শুধুমাত্র স্ট্যাকের উপরের ভ্যালুটি এক্সেস করে তা ডিলিট করে দেয় না, এই ক্ষেত্রে আমরা শেষ ভ্যালুটি কে delete করবো না। তাই এইক্ষেত্রে সেই ভ্যালুটিও temporay queue তে রেখেছি।   
            newQ.push(k);
        }
        q = newQ;
        return last;
    }

    bool empty()
    {
        return q.empty(); // queue খালি কিনা চেক করছি। 
    }
};