1  /*
 2   * Stack permutation is done using the following steps
 3   * Take 2 arrays as input
 4   * Then taking one element from the first array and push it to input stack 
 5   * If the top (most recent pushed element) of the stack already exists in the 2nd array 
 6   * we will pop tha element. 
 7   * If the arrays are permutations , then the output stack will be empty 
 8   */ 
 9  
10  import java.util.Stack;
11  import java.util.Scanner;
12  
13  public class stack_permutation {
14    public static boolean checkStackPerm(int ip[], int op[], int length) {
15      Stack<Integer> s = new Stack<Integer>();
16  
17      int j = 0;
18  
19      for(int i = 0; i < length; i++) {
20        s.push(ip[i]);
21  
22        while(!s.isEmpty() && s.peek() == op[j]) {
23          s.pop();
24          j++;
25        }
26      }
27  
28      if(s.isEmpty()) {
29        return true;
30      }
31      return false;
32    }
33  
34    public static void main(String[] args) {
35      Scanner sc = new Scanner(System.in);
36  
37      System.out.println("Enter length of array: ");
38      int length = sc.nextInt();
39  
40      int[] array1= new int[length];
41  
42      System.out.println("Enter array1: ");
43      for(int i = 0; i < length; i++) {
44        array1[i] = sc.nextInt();
45      }
46  
47      int[] array2 = new int[length];
48  
49      System.out.println("Enter array2: ");
50      for(int j = 0; j < length; j++) {
51        array2[j] = sc.nextInt();
52      }
53  
54      boolean perm_or_not = checkStackPerm(array1, array2, length);
55  
56      if(perm_or_not) {
57        System.out.println("The 2 arrays are permutations of each other");
58      }
59      else {
60        System.out.println("The 2 arrrays are not permutations of each other");
61      }
62    }
63  }