How to Sort array using Stacks in C++

By Pratik Tayade

In this tutorial, we are going to discuss how to sort an array using a stack in C++. First of all, we need to understand what is a stack? In the following paragraph, we will get to know what is meant by the stack.

Stacks can be stated as the type of container adapter in C++ which works on the principle of the LIFO.LIFO stands for Last In First Out. In the stack, the new element can be added from the one side only. The side from which the insertion and the deletion of the element happen is referred to as TOP of the stack.

We have one task here that is, we will be given with an array and we have to sort the array using array only.

The C++ program below illustrates the sorting of the array using stack

Now its time to write our code:

#include<bits/stdc++.h>
using namespace std;
stack<int> stack_sol(stack<int> x) // This will return the sorted stack.
{
  stack<int> pro;
  while (!x.empty())
  {
    // remove the first element (pop).
    int yb = x.top();
    x.pop();
    // Iterate till  the stack is not empty
    // and top of stack is smaller than yb
    while (!pro.empty() && pro.top() < yb)
    {
      // Remove(pop)from the stack
      // and insert(push) it to the pro stack
      x.push(pro.top());
      pro.pop();
    }
    pro.push(yb);// push yb in  stack
  }
  return pro;//return pro
}
void sort_Stacks(int var[], int n)
{
  
  stack<int> x;// Push The elements of the array into stack
  for (int i=0; i<n; i++)
  x.push(var[i]);
  // Sort the stack
  stack<int> pro = stack_sol(x);
  for (int i=0; i<n; i++)
  {
    var[i] = pro.top();
    pro.pop();
  }
}
int main()
{
  int var[] = {15,25,8,2,9};
  int n = sizeof(var)/sizeof(var[0]);
  sort_Stacks(var, n);
  for (int i=0; i<n; i++)
  cout<< var[i] << " ";
  return 0;
}

output:2 8 9 15 25

You can also refer to:

Leave a Reply Cancel reply