Check if an array is stack sortable | Java implementation of above approach . ; Function to check if A [ ] is Stack Sortable or Not . ; Stack S ; Pointer to the end value of array B . ; Traversing each element of A [ ] from starting Checking if there is a valid operation that can be performed . ; If the stack is not empty ; Top of the Stack . ; If the top of the stack is Equal to B_end + 1 , we will pop it And increment B_end by 1. ; if current top is equal to B_end + 1 , we will increment B_end to B_end + 1 ; Pop the top element . ; If the stack is empty We cannot further perfom this operation . Therefore break ; Current Top ; If stack is empty Push the Current element ; If the Current element of the array A [ ] if smaller than the top of the stack We can push it in the Stack . ; Else We cannot sort the array Using any valid operations . ; Not Stack Sortable ; If the stack is empty push the current element in the stack . ; Stack Sortable ; Driver 's Code
import java . util . Stack ; class GFG { static boolean check ( int A [ ] , int N ) { Stack < Integer > S = new Stack < Integer > ( ) ; int B_end = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! S . empty ( ) ) { int top = S . peek ( ) ; while ( top == B_end + 1 ) { B_end = B_end + 1 ; S . pop ( ) ; if ( S . empty ( ) ) { break ; } top = S . peek ( ) ; } if ( S . empty ( ) ) { S . push ( A [ i ] ) ; } else { top = S . peek ( ) ; if ( A [ i ] < top ) { S . push ( A [ i ] ) ; } else { return false ; } } } else { S . push ( A [ i ] ) ; } } return true ; } public static void main ( String [ ] args ) { int A [ ] = { 4 , 1 , 2 , 3 } ; int N = A . length ; if ( check ( A , N ) ) { System . out . println ( " YES " ) ; } else { System . out . println ( " NO " ) ; } } }