১৪-৮ঃ Implement Queue using Stacks (Leetcode)

এই পেজে আমরা শিখবো , কীভাবে Stack ডাটা স্ট্রাকচার কে ব্যবহার করে Queue ইমপ্লিমেন্ট করা যায়। প্রবলেম লিঙ্কঃ https://leetcode.com/problems/implement-queue-using-stacks/description/ প্রবলেম স্টেট্মেন্ট এ বলা আছে আপনাকে একটি MyQueue ক্লাস দেয়া আছে , যেখানে queue এর মেইন মেইন ফাংশন যেমনঃ push , pop , peek ( front) , empty এই সকল ফাংশন কমপ্লিট করতে হবে। এবং এই ফাংশন গুলা কমপ্লিট করার ক্ষেত্রে Queue এর কোনো concept ব্যবহার করা যাবে না। এই ক্ষেত্রে শুধু মাত্র দুটি stack এর সাহায্যে এই ফাংশন গুলোতে কাজ করতে হবে। আগের প্রবলেমের মতো আমরা প্রত্যেকটি ফাংশন আলাদা ভাবে আলোচনা করি।

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

2. pop(): এই ফাংশনটি queue এর শুরু থেকে অর্থাৎ front থেকে একটি ভ্যালু ডিলিট করে দিতে পারে। এখন আমাদের যেহেতু stack এর সাহায্যে কাজটি করতে হবে তাই দেখা যায় , stack এ pop এর ক্ষেত্রে যে ভ্যালুটি সবার পরে এসেছে অর্থাৎ শেষের ভ্যালুটি আগে pop হয়ে যাবে তাই এই কাজটি একটি stack এর সাহায্যে করা যাবে না। Solution: এই ক্ষেত্রে যেহেতু stack এর মধ্যে যে ভ্যালুটি সবার আগে enter করেছে তা বের করতে হবে , তাই এইক্ষেত্রে stack এর শেষ ভ্যালুটি ( pop এর ভিত্তিতে শেষের ভ্যালু) আমাদের বের করে আনতে হবে। এই ক্ষেত্রে আমরা আরেকটি temporary stack নিতে পারি । Original stack থেকে pop করে একটি একটি করে ভ্যালু temporary stack এ push করতে থাকবো ,এবং একটি সময় original stack এর শেষ ভ্যালুতে চলে আসবো তখন সেই ভ্যালুটি হবে Queue এর front এর ভ্যালু যেটি আমাদের pop করা লাগবে। এই ভ্যালুটি যেহেতু pop করে দিবো তাই তা আমাদের temporary stack এ রাখতে হবে না। সব ভ্যালু Temporary stack এর মধ্যে রাখার পর আমরা দেখতে পাবো , Original stack এর একটি reverse stack হলো Temporary stack. তাই এক্ষেত্রে আমরা সব কাজ শেষে সরাসরি Originl stack এ temporary stack রেখে দিতে পারবো না। এই ক্ষেত্রে আমাদের temporary stack থেকে ম্যানুয়ালি একটি একটি করে ভ্যালু Original stack এ পুশ করলে আমরা আবার original stack টি ব্যাক পাবো

1. peek(): উক্ত ফানশন টি queue এর সবার শুরুর ভ্যালুটি রিটার্ন করবে। এই ক্ষেত্রে আমরা pop এর ফাংশনের মতো stack এর শেষের ভ্যালুটি বের করে তা রিটার্ন করে দিবো। খেয়াল রাখতে হবে , pop ফাংশনে শেষ ভ্যালুটি temporary stack এ রাখা হয়নি , কিন্তু এই ক্ষেত্রে যেহেতু আমরা peek এর ভ্যালুটি রিমুভ করবো না , তাই এই ভ্যালুটিও temporary stack এ রাখতে হবে।

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

আসুন এইবার কোড দেখে নেয়া যাক

class MyQueue
{
public:
    stack<int> st; // একটি stack নেয়া হচ্ছে 
    MyQueue()
    {
    }

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

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

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

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