تباديل المكدس (تحقق مما إذا كانت المصفوفة هي تبديل مكدس لأخرى)


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون فوركايتس
اندماجي طابور كومة

المشكلة بيان

توضح مشكلة "Stack permutations (تحقق مما إذا كانت المصفوفة هي تبديل المكدس لأخرى)" أنه يتم منحك مصفوفتين a [] و b [] بالحجم n. جميع عناصر المصفوفة فريدة من نوعها. قم بإنشاء دالة للتحقق مما إذا كانت المصفوفة المعطاة 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. تهيئة اثنين المصفوفات أ [] و ب [] بحجم ن.
  2. قم بإنشاء دالة للتحقق من تبديل المكدس الذي يقبل الاثنين عدد صحيح المصفوفات وحجم المصفوفة كما هي معلمات.
  3. بعد ذلك ، قم بإنشاء ملف طابور هيكل البيانات من نوع صحيح.
  4. اجتياز المصفوفة [] وادفع / أدخل جميع عناصر المصفوفة [] في قائمة الانتظار.
  5. بعد ذلك ، قم بإنشاء بنية بيانات قائمة انتظار ثانية من نوع عدد صحيح.
  6. اجتياز المصفوفة b [] وادفع / أدخل جميع عناصر المصفوفة b [] في قائمة الانتظار.
  7. وبالمثل ، قم بإنشاء ملف كومة هيكل البيانات من نوع صحيح.
  8. قم بالانتقال بينما حجم قائمة الانتظار الأولى ليس 0. قم بإنشاء متغير عدد صحيح وقم بتخزين العنصر في مقدمة قائمة الانتظار الأولى فيه وقم بإزالته / إزالته من قائمة الانتظار الأولى.
  9. تحقق مما إذا كانت القيمة في متغير العدد الصحيح لا تساوي العنصر الموجود في مقدمة قائمة الانتظار الثانية ، وادفع / أدخل متغير العدد الصحيح في المكدس.
  10. عدا ذلك ، انبثق / أزل العنصر الموجود في مقدمة قائمة الانتظار الثانية.
  11. قم بالانتقال مرة أخرى بينما لا يكون حجم المكدس 0. تحقق مما إذا كان العنصر الموجود أعلى المكدس مساويًا للعنصر الموجود في مقدمة قائمة الانتظار الثانية ، وانطلق / أزل العنصر في مقدمة قائمة الانتظار الثانية ، ومن الجزء العلوي من المكدس. استراحة أخرى.
  12. تحقق مما إذا كانت كل من المكدس وقائمة الانتظار الأولى فارغة ، اطبع "نعم" وإلا اطبع "لا".

رمز

برنامج C ++ للتباديل المكدس

#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 هو عدد العناصر في مصفوفة معينة a [] و b []. لقد اجتزنا للتو عناصر المصفوفة ، وبالتالي فقد تجاوزنا تعقيدًا زمنيًا خطيًا.

تعقيد الفضاء

O (ن) لأننا استخدمنا مساحة لعدد n من العناصر. لقد أنشأنا قائمتين انتظار ومكدس مما يجعل الخوارزمية لديها تعقيد خطي في الفضاء.