स्टॅक परमिटेशन्स (अ‍ॅरेचा स्टॅक क्रमांकाचा भाग आहे का ते तपासा)


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फोरकाइट्स
एकत्रित रांग स्टॅक

समस्या विधान

“स्टॅक परमिटेशन्स (अ‍ॅरेचा इतरांचा स्टॅक परिमिती आहे का ते तपासा)” ही समस्या सांगते की आपल्याला दोन अ‍ॅरे एक [] आणि बी [] आकाराचे एन दिले आहेत. अ‍ॅरेचे सर्व घटक अद्वितीय आहेत. दिलेली अ‍ॅरे बी [] दिलेली अ‍ॅरेची स्टॅक परिमिती आहे की नाही हे तपासण्यासाठी एक फंक्शन तयार करा [].

स्टॅक परमिटेशन्स (अ‍ॅरेचा स्टॅक क्रमांकाचा भाग आहे का ते तपासा)

उदाहरण

a[ ] = {1, 2, 3}

b[ ] = {2, 1, 3}
Yes

स्पष्टीकरणः प्रथम 1 आणि 2 स्टॅकमध्ये ढकल. नंतर त्यांना स्टॅकवरून पॉप करा. त्यानंतर, 3, नंतर पॉप 3 वर ढकलणे. परिणामी अनुक्रम 2, 1,3 असे दिसते जे आमचा दुसरा अ‍ॅरे आहे.

a[ ] = {1, 2, 3}

b[ ] = {3, 1, 2}
No

स्पष्टीकरणः पुश आणि पॉपचा कोणताही क्रम नाही ज्याचा परिणाम दुसर्‍या अ‍ॅरेमध्ये होईल. आणि म्हणून उत्तर नाही आहे.

अल्गोरिदम

  1. दोन आरंभ करा अ‍ॅरे अ [] आणि बी [] आकाराचे एन.
  2. स्टॅक परमिट तपासण्यासाठी फंक्शन तयार करा जे या दोघांना स्वीकारते पूर्णांक अ‍ॅरे आणि पॅरामीटर्स प्रमाणे अ‍ॅरेचा आकार.
  3. यानंतर, ए तयार करा शेपूट पूर्णांक प्रकारांची डेटा रचना.
  4. अ‍ॅरे अ []] वरून जा आणि अ‍ॅरेच्या सर्व घटकांना एका रांगेत खाली ढकलणे / घाला.
  5. त्यानंतर, पूर्णांक प्रकारची दुसरी रांग डेटा रचना तयार करा.
  6. अ‍ॅरे बी मधून जा [] आणि रांगेत अ‍ॅरे बीचे सर्व घटक ढकलणे / घाला.
  7. त्याचप्रमाणे ए तयार करा स्टॅक पूर्णांक प्रकारांची डेटा रचना.
  8. पहिल्या रांगेचा आकार 0 नसल्यास ट्रॅव्हर्स XNUMX पूर्णांक व्हेरिएबल तयार करा आणि त्यामध्ये पहिल्या रांगेच्या पुढील भागास घटक संचयित करा आणि पहिल्या रांगेतून पॉप / काढा.
  9. पूर्णांक व्हेरिएबलमधील मूल्य दुसर्‍या रांगेच्या समोर असलेल्या घटकाइतके नसते का ते तपासा, स्टॅकमध्ये पूर्णांक व्हेरिएबल दाबा / घाला.
  10. अन्य रांगेच्या पुढील बाजूस घटक पॉप / काढा.
  11. स्टॅकचा आकार ० नसताना पुन्हा आडवा करा. स्टॅकच्या शीर्षस्थानी घटक दुसर्‍या रांगेच्या पुढील भागाच्या समान भागाशी आहे का ते तपासा, आणि दुसर्‍या रांगेच्या पुढील भागास घटक पॉप / काढून टाका आणि स्टॅकचा वरचा भाग. बाकी ब्रेक.
  12. स्टॅक आणि पहिली रांग दोन्ही रिक्त आहेत का ते तपासा, “होय” अन्य मुद्रित करा “नाही”.

कोड

स्टॅक परमिटेशनसाठी सी ++ प्रोग्राम

#include<bits/stdc++.h> 
using namespace std; 
  
bool checkStackPermutation(int a[], int b[], int n){ 
    
    queue<int> input; 
    for(int i=0; i<n; i++){ 
        input.push(a[i]);
    }
  
    queue<int> output; 
    for(int i=0; i<n; i++){ 
        output.push(b[i]);
    }
  
    stack <int> tempStack; 
    while(!input.empty()){ 
        int ele = input.front(); 
        input.pop(); 
        
        if (ele == output.front()){ 
            output.pop(); 
            
            while(!tempStack.empty()){ 
                
                if(tempStack.top() == output.front()){ 
                    tempStack.pop(); 
                    output.pop(); 
                } 
                
                else{
                    break;
                }
            } 
        } 
        else{
            tempStack.push(ele); 
        }
    } 
  
    return (input.empty()&&tempStack.empty()); 
} 
  
int main(){ 
    int a[] = {1, 2, 3}; 
    int b[] = {2, 1, 3}; 
  
    int n = sizeof(a)/sizeof(a[0]); 
  
    if(checkStackPermutation(a, b, n)){ 
        cout << "Yes"; 
    }
    else{
        cout << "No"; 
    }
    return 0; 
}
Yes

स्टॅक परमिटेशनसाठी जावा प्रोग्राम

import java.util.LinkedList; 
import java.util.Queue; 
import java.util.Stack; 
  
class StackPermutation{ 
    static boolean checkStackPermutation(int a[], int b[], int n){ 
        Queue<Integer> input = new LinkedList<>(); 
  
        for(int i = 0; i < n; i++){ 
            input.add(a[i]); 
        } 
  
        Queue<Integer> output = new LinkedList<>(); 
        for(int i = 0; i < n; i++){ 
            output.add(b[i]); 
        } 
  
        Stack<Integer> tempStack = new Stack<>(); 
        while(!input.isEmpty()){ 
            int ele = input.poll(); 
  
            if(ele == output.peek()){ 
                output.poll(); 
                
                while(!tempStack.isEmpty()){ 
                    
                    if(tempStack.peek() == output.peek()){ 
                        tempStack.pop(); 
                        output.poll(); 
                    } 
                    
                    else{
                        break;
                    }
                } 
            }  
            else{ 
                tempStack.push(ele); 
            } 
        } 
  
        return (input.isEmpty() && tempStack.isEmpty()); 
    } 
  
    public static void main(String[] args){ 
        
        int a[] = { 1, 2, 3 }; 
        int b[] = { 2, 1, 3 }; 
        int n = a.length;
        
        if(checkStackPermutation(a, b, n)){ 
            System.out.println("Yes"); 
        }
        else{
            System.out.println("No"); 
        }
    } 
}
Yes

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे n दिलेल्या अ‍ॅरे a [] आणि b [] मधील घटकांची संख्या आहे. आम्ही नुकताच अ‍ॅरे घटकांमधून आणि अशा प्रकारे रेषीय वेळ गुंतागुंत केला आहे.

स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही n घटकांसाठी जागा वापरली. आम्ही दोन रांगा आणि स्टॅक तयार केले आहेत ज्यामुळे अल्गोरिदमला जागेत रेषात्मक गुंतागुंत निर्माण होते.