text: Check if an array is stack sortable | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( int A [ ] , int N ) { stack < int > S ; int B_end = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! S . empty ( ) ) { int top = S . top ( ) ; while ( top == B_end + 1 ) { B_end = B_end + 1 ; S . pop ( ) ; if ( S . empty ( ) ) { break ; } top = S . top ( ) ; } if ( S . empty ( ) ) { S . push ( A [ i ] ) ; } else { top = S . top ( ) ; if ( A [ i ] < top ) { S . push ( A [ i ] ) ; } else { return false ; } } } else { S . push ( A [ i ] ) ; } } return true ; } int main ( ) { int A [ ] = { 4 , 1 , 2 , 3 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; check ( A , N ) ? cout << " YES " : cout << " NO " ; return 0 ; }