How to check if an array is stack sortable in C++

In this tutorial, we will learn about how to check, using the C++ programming language, whether a given array is stack sortable or not.

An array P is said to be stack sortable only when:

• Its elements can be moved to a temporary stack variable(let’s say ‘Stk’) one by one starting from the first element.
• From that stack, those elements moved to another array Q one by one(addition of stack top element, that we remove from the stack, and adding it to the end of array Q).
• And after these operations, we find that all the elements in array Q are present in ascending order(sorted manner).

Provided input array P contains integer values only.

For example:
We have an Array P with elements { 9, 7, 4, 2, 1 }, a temporary stack variable Stk which is empty initially and another array Q of the same size as that of array P. In this case, the output will be true i.e. array P is stack sortable.

Explanation:

Input: int P[]= { 9, 7, 4, 2, 1 }
First operation: 
Removing elements from the front of array P one by one and adding them 
to stack Stk such that we have:
P[]= {}
Stk= { 9, 7, 4, 2, 1 }
Second operation:
Remove the top element of the stack Stk and add the to the end of array 
Q so that we end up with:
Q[]= { 1, 2, 4, 7, 9 }
Stk= {}

Now we can see that array Q has elements that are sorted in ascending order. Therefore, array P is stack sortable array. From these operations, we can conclude that if all elements of array P can be pushed into the stack, following the condition such that element to be pushed is smaller than the top element of the stack then array P will be stack sortable.

For better understanding let us consider the following example:

#include<iostream>//std::cout
#include<stack>//std::stack
#include<array>//std::array
using namespace std;
/*boolean function which results true if all the elements get pushed or 
false if all of them don't get pushed into stack*/ 
bool checkstacksortable(array <int,4>p)
{
  stack <int> Stk; //creating stack variable
  Stk.push(p[0]); //pushing first element of array into the stack
  for(int i=1;i<p.size();i++)
 {
     if(Stk.top()>p[i])  //main condition for pushing an element into the stack
      Stk.push(p[i]);
     else
      return 0; //condition fails and thus all the elements won't be pushed into the stack
 }
 return 1; //returns true as all element get pushed into the stack

}
int main()
{
  array <int,4> P={8,6,3,1};
  if(checkstacksortable(P))
  cout<<"Array P is stack sortable";
  else
  cout<<"Array P is not stack sortable";
}

The output of the following program is:

Array P is stack sortable

Explanation: ‘checkstacksortable’ function checks the main criteria that whether all the elements get pushed into the stack following the condition such that element to be pushed is smaller than the top element of the stack. When any of the elements don’t follow this criterion, the function returns false or 0 implying that the array is not stack sortable else it would return true or 1 implying that the array is stack sortable.

Also read:

• Reversal Algorithm for the Right Rotation of an Array in C++
• std::bitset::bitset in C++