اسٹیک پرمٹٹیشن (چیک کریں اگر کوئی صف دوسرے کے اسٹیک پرمٹ ہے)


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون فورکائٹس
مشترکہ قطار اسٹیک

مسئلہ یہ بیان

مسئلہ "اسٹیک پرمٹٹیشن (چیک کریں اگر کوئی صف دوسرے کے اسٹیک پرمٹ ہے)" میں بتایا گیا ہے کہ آپ کو دو ارے a [] اور b [] سائز این دیئے گئے ہیں۔ صف کے سارے عناصر منفرد ہیں۔ یہ معلوم کرنے کے لئے ایک فنکشن بنائیں کہ آیا دیئے جانے والے ارے بی [] دیئے گئے صفوں کو اسٹیک اجازت ہے []] یا نہیں۔

اسٹیک پرمٹٹیشن (چیک کریں اگر کوئی صف دوسرے کے اسٹیک پرمٹ ہے)

مثال کے طور پر

a[ ] = {1, 2, 3}

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

وضاحت: سب سے پہلے اسٹیک میں 1 اور 2 دبائیں۔ پھر انہیں اسٹیک سے پاپ کریں۔ اس کے بعد ، 3 دبائیں ، پھر پاپ 3۔ لہذا نتیجہ ترتیب 2 ، 1,3،XNUMX کی طرح لگتا ہے جو ہماری دوسری صف ہے۔

a[ ] = {1, 2, 3}

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

وضاحت: پش اور پاپ کا کوئی ترتیب نہیں ہے جس کا نتیجہ دوسری صف میں نکلے گا۔ اور اس طرح جواب نہیں ہے۔

الگورتھم

  1. دو شروع کریں صفیں a [] اور b [] سائز n.
  2. اسٹیک پرمٹ چیک کرنے کے لئے ایک فنکشن بنائیں جو ان دونوں کو قبول کرتا ہے عددی ارے اور پیرے کی حیثیت سے صف کا سائز۔
  3. اس کے بعد ، ایک بنائیں قطار عددی قسم کا ڈیٹا ڈھانچہ۔
  4. صف کو ایک []] سے عبور کریں اور صف میں شامل ہونے والے سرنی کے تمام عناصر کو [] داخل کریں۔
  5. اس کے بعد ، انٹیجر قسم کی دوسری قطار ڈیٹا ڈھانچہ تشکیل دیں۔
  6. صف کے بی سے گزریں []] اور صف میں داخل ہونے والے صف کے تمام عناصر کو [] داخل کریں۔
  7. اسی طرح ، تخلیق a ڈھیر لگانا عددی قسم کا ڈیٹا ڈھانچہ۔
  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 دیئے گئے صف میں موجود عناصر کی تعداد ایک [] اور بی [] ہے۔ ہم ابھی سرنی عناصر اور اس طرح ایک لمبی وقت کی پیچیدگی سے گذر چکے ہیں۔

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

اے (ن) کیونکہ ہم نے n عناصر کے لئے جگہ استعمال کی۔ ہم نے دو قطاریں اور اسٹیک بنائے ہیں جس کی وجہ سے الگورتھم خلا میں خطوطی پیچیدگی پیدا کرتا ہے۔