Пермутације стека (Проверите да ли је низ пермутацијама стека других)


Ниво тешкоће Средњи
Често питани у амазонка Фоуркитес
Комбинаторни Ред Стацк

Изјава о проблему

Проблем „Пермутације стека (Проверите да ли је низ пермутацијама стека других)“ наводи да су вам дата два низа а [] и б [] величине н. Сви елементи низа су јединствени. Направите функцију за проверу да ли је задати низ б [] пермутација стека датог низа а [] или не.

Пермутације стека (Проверите да ли је низ пермутацијама стека других)

Пример

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. Створите целобројну променљиву и сачувајте елемент на челу првог реда у њему и ставите га / уклоните из првог реда.
  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

Анализа сложености

Сложеност времена

Он) где је н број елемената у датом низу а [] и б []. Управо смо прешли кроз низ елемената и тиме линеарну временску сложеност.

Сложеност простора

Он) јер смо користили простор за н елемената. Направили смо два реда и стек што чини алгоритам линеарном сложеношћу у простору.