جایگزینی های پشته (بررسی کنید آیا آرایه جایگزینی پشته های دیگر است)


سطح دشواری متوسط
اغلب در آمازون فورکایت
ترکیبی صف پشته

بیان مسأله

مسئله "جایگزینی های پشته (بررسی کنید که آیا آرایه ای جایگزین پشته دیگری است)" بیان می کند که به شما دو آرایه a [] و b [] از اندازه n داده می شود. تمام عناصر آرایه منحصر به فرد هستند. برای بررسی اینکه آیا آرایه داده شده b [] جایگزینی پشته آرایه a [] است یا خیر ، یک تابع ایجاد کنید.

جایگزینی های پشته (بررسی کنید آیا آرایه جایگزینی پشته های دیگر است)

مثال

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. از طریق آرایه a [] عبور کرده و تمام عناصر آرایه a [] را در صف فشار دهید / وارد کنید.
  5. پس از آن ، یک ساختار داده صف دوم از نوع عدد صحیح ایجاد کنید.
  6. از آرایه b [] عبور کرده و تمام عناصر آرایه b [] را در صف فشار دهید / وارد کنید.
  7. به همین ترتیب ، ایجاد کنید پشته ساختار داده از نوع عدد صحیح.
  8. عبور کنید در حالی که اندازه صف اول 0 نیست. یک متغیر عدد صحیح ایجاد کنید و عنصر موجود در جلوی صف اول را در آن ذخیره کنید و آن را از صف اول پاپ / حذف کنید.
  9. بررسی کنید که آیا مقدار متغیر عدد صحیح برابر با عنصر جلوی صف دوم نیست ، متغیر عدد صحیح را در پشته فشار دهید / وارد کنید.
  10. Else pop / عنصر جلوی صف دوم را بردارید.
  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) که n تعداد عناصر موجود در یک آرایه داده شده a [] و b [] است. ما فقط عناصر آرایه را مرور کرده ایم و بنابراین یک پیچیدگی زمانی خطی را پیدا کرده ایم.

پیچیدگی فضا

O (N) زیرا ما از n برای عناصر استفاده کردیم. ما دو صف و پشته ایجاد کردیم که باعث می شود الگوریتم دارای پیچیدگی خطی در فضا باشد.