Stack: Check if a stack is a permutation of another stack

Problem Statement:

You are given 2 array, check one array is permutation of another array.

Example

Input : First array: 1, 2, 3
Second array: 2, 1, 3
Output : Yes

Solution

In this solution we will convert the input queue to the output queue using stack and check.

Take 2 queue, and insert both of the stack into 2 queues. One is input queue and another is output queue.

Then create a stack data structure.

Then check if the value of the top element of the input queue is equal to the front of the second queue, if it is equal then remove the element from the second queue.

If it is not equal, then push the element into the stack

Then traverse again till the size of the stack is not 0. Check if the the top of the stack is equal to the element in the front of the second queue. Then pop the element at the front of the second queue and top of the stacl.

else break.

Then if both the stack and the first queue are empty then print yes.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

bool check_stack_permutation(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(check_stack_permutation(a, b, n)){ 
        cout << "Yes"; 
    }
    else{
        cout << "No"; 
    }
    return 0; 
}

Output:

Yes