Sorting a stack using stl in C++

In this tutorial, we will learn how to sort a stack using stl in C++. Hence first we will learn about stl.

Tutorial to sort a stack using standard template library in C++

STL stands for standard template library which is a set of classes that provides various pre-defined data structures and functions to aid programs such as arrays, linked lists, trees and stacks, etc. There are four components of STL: Algorithms, Functions, Containers, and iterators.
Algorithms contain sorting, searching, array algorithms, partition operations, etc. Containers contain data structures like lists, arrays, queue, stack, priority queues, sets, maps, etc. Iterators are used to loop over a sequence of items as the name suggests. In this tutorial, we are going to use a stack as an stl component to sort another stack.

To read and understand stacks more clearly, visit: Stack in C++ Standard Template Library (STL)

The approach to sort a stack using another temporary stack is very simple. We will loop over the main stack until the underflow condition occurs. Here we will use .isEmpty() function of stack container class which tells whether the stack is empty or not. Then, we will pop out the element out of the stack and compares it will element in the temporary stack. If the top element of the temporary stack is greater than the popped element of the main stack, we will pop it out of the temporary stack and push into the main stack, meanwhile, we will push the popped element of the main stack into the temporary stack.

At the end of the loop, the main stack gets empty and elements are stored in the temporary stack in a decreasing sorted order. If we want the order to be increasing, we have to push all the elements back to the main stack.

The program for the same:

#include <bits/stdc++.h> 
using namespace std; 

stack<int> sortFunction(stack<int> &mainStack) 
{ 
  stack<int> AuxStack; 

  while (!mainStack.empty()) 
  { 
    // pop out the first element 
    int temp = mainStack.top(); 
    mainStack.pop(); 

    while (!AuxStack.empty() && AuxStack.top() > temp) 
    { 
      // pop from Auxstack and push it to the mainstack 
      mainStack.push(AuxStack.top()); 
      AuxStack.pop(); 
    } 

    // push temp in end 
    AuxStack.push(temp); 
  } 

  return AuxStack; 
} 

// main function 
int main() 
{ 
  stack<int> mainStack; 
  mainStack.push(78); 
  mainStack.push(103); 
  mainStack.push(31); 
  mainStack.push(19); 
  mainStack.push(67); 
  mainStack.push(83); 
  mainStack.push(47);

  // Declaring AuxStack
  stack<int> AuxStack = sortFunction(mainStack); 
  cout << "Sorted numbers in decreasing order are:"<<endl; 
  while (!AuxStack.empty()) 
  { 
    cout << AuxStack.top()<< " "; 
    mainStack.push(AuxStack.top());
    AuxStack.pop(); 
  } 
  cout<<endl;
  cout<<"Sorted numbers in increasing order are:"<<endl;
  while(!mainStack.empty()){
      cout<<mainStack.top()<<" ";
      mainStack.pop();
  }
} 

Output:

Sorted numbers in decreasing order are: 103 83 78 67 47 31 19 
Sorted numbers in increasing order are: 19 31 47 67 78 83 103

I hope this tutorial was helpful for all.

To understand STL better, visit: How to change a particular element of a C++ STL Vector

One response to “Sorting a stack using stl in C++”

  1. Mohit Kumar says:

    Was working on stl and had the same doubt this really helped me a lot !!
    Good Job

Leave a Reply

Your email address will not be published. Required fields are marked *