اسٽيڪ اجازت نامو (چيڪ ڪريو ته صف ٻي اسٽوري جو اجازت نامو آهي)


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon چار چار
گڏجاڻي پنگتي حيثيت رکي ٿو چتي

مسئلي جو بيان

مسئلو "اسٽيڪ اجازت نامو (چڪاس ڪريو ته ڇا صف بندي اسٽيڪ جي ٻين اجازت نامو آهي)" ٻڌائي ٿي ته توهان کي ٻه عدد هڪ آهي اي [] ۽ b [] سائيز n. صف جا سڀ عنصر منفرد آهن. اهو چيڪ ڪرڻ لاءِ فڪشن ٺاهيو ته جيڪڏهن ڏنل صف ب [] ڏنل صف جو هڪ اسٽيڪ اجازت آهي [] يا نه.

اسٽيڪ اجازت نامو (چيڪ ڪريو ته صف ٻي اسٽوري جو اجازت نامو آهي)

مثال

a[ ] = {1, 2, 3}

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

وضاحت: پهرين ڌڪ 1 ۽ 2 کي اسٽيڪ ۾. پوءِ انهن کي اسٽيڪ مان پاپ ڪريو. بعد ۾ ، pushيرايو 3 ، پوءِ پاپ 3. انهي جو نتيجو تسلسل 2 ، 1,3،XNUMX وانگر لڳندو آهي جيڪو اسان جي ٻي صف آهي

a[ ] = {1, 2, 3}

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

وضاحت: ڌپ ۽ پاپ جو تسلسل ناهي جنهن جو نتيجو ٻئي صف ۾ اچي ويندو. ۽ اهڙي طرح جواب ناهي.

الورورٿم

  1. شروعاتي ٻه قطارون a [] ۽ b [] سائيز n.
  2. اسٽيڪ اجازت نامي کي جانچڻ لاءِ هڪ فنڪشن ٺاهيو جيڪو ٻن کي قبول ڪري ٿو انٽرويو ان جون قطارون ۽ سائز جي ماپ
  3. ان کان پوءِ اي پنگتي حيثيت رکي ٿو انڌيري قسم جي ڊيٽا جو خاڪو.
  4. صف آر. [] کي ڇڪيو ۽ قطار جي سڀني عناصر کي [/] دٻايو / قطار ۾ [].
  5. ان کان پوءِ ، انٽيگر قسم جو ٻيو قطار ڊيٽا جوڙيو.
  6. قطار ذريعي گذري وڃڻ [b] ۽ قطار ۾ [b] صف جي سڀني عنصرن کي ڌڪ / داخل ڪيو.
  7. ساڳي طرح ، اي ٺاهيو اسٽيڪ انڌيري قسم جي ڊيٽا جو خاڪو.
  8. سفر ڪريو جڏهن ته پهرين قطار جي ماپ 0. نه آهي ڪو انوگر متغير ٺاهيو ۽ عنصر کي ان ۾ رکي ڇڏيو پهرين قطار کي انهي ۾ رکو ۽ پاپ / خارج ڪريو ان کي پهرين قطار مان.
  9. چڪاس ڪريو ته انٽيگر متغير ۾ قدر ٻئي قطار جي اڳيان عنصر سان برابر نه آهي ، اسٽڪ ۾ انٽيگر متغير کي دٻايو / داخل ڪريو.
  10. ايل پاپ / قطار کي قطار ڪريو ٻي قطار جي سامھون.
  11. ٻيهر لڪايو جڏهن ته اسٽيڪ جو قد 0. ناهي اسٽيڪ جي چوٽي. ايلس بريڪ.
  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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي n ھڪڙي ڏنل قطار ۾ عناصر جو تعداد آھي a [] ۽ b []. اسان صرف ترتيب واري عنصرن مان لنگهيو آهي ۽ اهڙيءَ طرح هڪ لڪير وقت جي پيچيدگي آهي.

خلائي پيچيدگي

اي (ن) ڇاڪاڻ ته اسان اين عنصرن لاءِ جاءِ استعمال ڪئي. اسان ٻه قطار ۽ اسٽيڪ ٺاهيا جيڪي الگورٿم کي خلا ۾ لڪير جي پيچيدگي ٺاهيندا آهن.