C++-এ স্ট্যাক থেকে পপ অপারেশন করে অ্যারেতে থাকা প্রতিটি এলিমেন্ট পাওয়ার সংখ্যা গণনা

একটি সংখ্যার অ্যারে এবং একটি স্ট্যাক দেওয়া আছে। অ্যারেতে থাকা সকল এলিমেন্ট স্ট্যাকে আছে। লক্ষ্য হলো প্রতিটি অ্যারে এলিমেন্ট পেতে কতবার পপ অপারেশন করতে হয় সেটির গণনা করা।

স্ট্যাকটি ডিক্রিজিং অর্ডারে ভরা থাকে, প্রথম এলিমেন্টটি সর্বোচ্চ এবং টপ এলিমেন্টটি ন্যূনতম।

উদাহরণ ১

ইনপুট

Stack [ 7,6,2,1 ] array : 2,1,6,7

আউটপুট

স্ট্যাক থেকে পপ অপারেশন করে অ্যারেতে থাকা প্রতিটি এলিমেন্ট পাওয়ার সংখ্যা: 3 1 0 0

ব্যাখ্যা

অ্যারেটি ০তম ইনডেক্স থেকে ট্রুভার্স: ২ পেতে স্ট্যাক ৩ বার পপ করতে হয়। তাই arr[0] = ৩। প্রথম দুটি পপ দিয়ে ৭ এবং ৬ও বের হয়েছে। ১ পেতে এখন একবার পপ করতে হয়। তাই arr[1] = ১। ৬ এবং ৭ ইতিমধ্যে পপ হয়ে গেছে, তাই arr[2]=arr[3]=0।

উদাহরণ ২

ইনপুট

Stack [ 3,2,1,1 ] array : 1,2,1,3

আউটপুট

স্ট্যাক থেকে পপ অপারেশন করে অ্যারেতে থাকা প্রতিটি এলিমেন্ট পাওয়ার সংখ্যা: 3 0 1 0

ব্যাখ্যা

অ্যারেটি ০তম ইনডেক্স থেকে ট্রুভার্স: ১ পেতে স্ট্যাক ৩ বার পপ করতে হয়। তাই arr[0] = ৩। প্রথম দুটি পপ দিয়ে ৩ এবং ২ও বের হয়েছে।

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে unordered_map um ব্যবহার করা হয় যাতে চেক করা যায় এলিমেন্টটি ইতিমধ্যে পপ হয়েছে কিনা। এলিমেন্ট পপ করে um-এ যোগ করা হয়। যদি সেটি আবার আসে তবে পপ কাউন্ট ০ সেট করা হয়। না হলে তখন পর্যন্ত পপ করা হয় যতক্ষণ না পাওয়া যায়, এবং কাউন্ট বাড়ানো হয়।

ইন্টিজার অ্যারে arr[] নিন।
এলিমেন্টগুলো সংরক্ষণের জন্য stack stck নিন।
ডিক্রিজিং অর্ডারে এলিমেন্টগুলো পুশ করুন।
pop_operations(stack& stck, int arr[], int elements) ফাংশনটি পপ অপারেশনের সংখ্যা রিটার্ন করে।
আরম্ভিক কাউন্ট ০ রাখুন।
পপ অপারেশনের время которых একক সংখ্যাগুলো সংরক্ষণের জন্য unordered_map um নিন।
for লুপ দিয়ে অ্যারে ট্রুভার্স করুন।
temp = arr[i] নিন।
যদি temp um-এ না থাকে, তবে ০ পপ অপারেশন প্রিন্ট করুন।
অন্যথায় যতক্ষণ temp পাওয়া যায় না ততক্ষণ স্টাকে পপ করুন, প্রতিটি পপ করা এলিমেন্টকে um-এ true সেট করুন এবং কাউন্ট বাড়ান।
while লুপ শেষে কাউন্ট প্রিন্ট করুন।
এভাবে অ্যারেতে থাকা প্রতিটি এলিমেন্টের জন্য পপ অপারেশনের কাউন্ট প্রিন্ট হবে।

উদাহরণ কোড

#include <bits/stdc++.h> 
using namespace std; 

void pop_operations(stack<int>& stck, int arr[], int elements) {
    int count = 0; 
    unordered_map<int, bool> um; 
    cout << "স্ট্যাক থেকে পপ অপারেশন করে অ্যারেতে থাকা প্রতিটি এলিমেন্ট পাওয়ার সংখ্যা: "; 
    
    for (int i = 0; i < elements; ++i) {
        int temp = arr[i]; 
        if (um.find(temp) != um.end()) {
            cout << "0 "; 
        } else {
            count = 0; 
            while (stck.top() != temp) {
                um[stck.top()] = true; 
                stck.pop(); 
                count++; 
            } 
            stck.pop(); 
            count++; 
            cout << count << " "; 
        } 
    } 
} 

int main() { 
    int elements = 4; 
    int arr[] = { 2, 1, 6, 7}; 
    stack<int> stck; 
    stck.push(1); 
    stck.push(2); 
    stck.push(6); 
    stck.push(7); 
    pop_operations(stck, arr, elements); 
    return 0; 
}

আউটপুট

উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:

স্ট্যাক থেকে পপ অপারেশন করে অ্যারেতে থাকা প্রতিটি এলিমেন্ট পাওয়ার সংখ্যা: 3 1 0 0