C++ में स्टैक से सरणी के प्रत्येक तत्व को प्राप्त करने के लिए पॉप ऑपरेशनों की संख्या गिनें

समस्या विवरण

संख्याओं की एक सरणी और एक स्टैक दिया गया है। सरणी के सभी तत्व स्टैक के अंदर मौजूद हैं। लक्ष्य प्रत्येक सरणी तत्व को प्राप्त करने के लिए आवश्यक पॉप ऑपरेशनों की संख्या ज्ञात करना है।

स्टैक घटते क्रम में भरा जाता है, पहला तत्व सबसे बड़ा होता है और शीर्ष तत्व सबसे छोटा होता है।

उदाहरण

इनपुट

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

आउटपुट

पॉप ऑपरेशनों की संख्या: 3 1 0 0

व्याख्या

सरणी को 0th इंडेक्स से पार करते हुए, 2 प्राप्त करने के लिए हम स्टैक को तीन बार पॉप करेंगे। इसलिए arr[0] = 3। पहले दो पॉप 7 और 6 भी देंगे। 1 प्राप्त करने के लिए हम अब स्टैक को एक बार पॉप करेंगे। इसलिए arr[1] = 1। 6 और 7 के लिए चूंकि ये पहले ही पॉप हो चुके हैं, इसलिए arr[2]=arr[3]=0।

इनपुट

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

आउटपुट

पॉप ऑपरेशनों की संख्या: 3 0 1 0

व्याख्या

सरणी को 0th इंडेक्स से पार करते हुए, 1 प्राप्त करने के लिए हम स्टैक को तीन बार पॉप करेंगे। इसलिए arr[0] = 3। पहले दो पॉप 3 और 2 भी देंगे।

दृष्टिकोण

इस दृष्टिकोण में हम एक unordered_map<int, bool> um का उपयोग करेंगे ताकि यह जांचा जा सके कि तत्व पहले ही पॉप हो चुका है या नहीं। तत्व को पॉप करें और इसे um में जोड़ें। यदि यह फिर से आता है तो पॉपिंग गिनती को 0 सेट करें। यदि नहीं तो तब तक गिनती बढ़ाएं जब तक हम इसे प्राप्त न कर लें।

एल्गोरिदम चरण

एक पूर्णांक सरणी arr[] लें।
तत्वों को संग्रहीत करने के लिए stack<int> stck लें।
घटते क्रम में इसमें तत्व डालें।
फंक्शन pop_operations(stack<int>& stck, int arr[], int elements) स्टैक पर पॉप ऑपरेशनों की संख्या लौटाता है।
प्रारंभिक गिनती 0 लें।
पॉप ऑपरेशन करते समय मिले अद्वितीय संख्याओं को संग्रहीत करने के लिए unordered_map<int, bool> um लें।
for लूप का उपयोग करके सरणी को पार करें।
temp = arr[i] लें।
यदि temp um में नहीं है। इसे प्राप्त करने के लिए 0 पॉप ऑपरेशन प्रिंट करें।
अन्यथा जब तक temp न मिल जाए, स्टैक पर पॉप करें और पॉप किए गए प्रत्येक तत्व को um में true सेट करें और गिनती बढ़ाएं।
लूप के अंत में गिनती प्रिंट करें।
इस तरह हम सरणी के प्रत्येक तत्व के लिए पॉप ऑपरेशनों की गिनती प्रिंट करेंगे।

C++ कोड उदाहरण

#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