Sort stack using temporary Stacks in C++

In this tutorial of CodeSpeedy, we will learn how to sort a stack using temp Stacks in C++. We will learn to write the program in C++ in a very cool and easy way.

If you don’t know anything about this or how to write a program for the above topic, it’s OK, you are in the right place, let’s learn about it. Here, We will write a C++ program to sort a given unsorted stack into ascending order with the help of another temporary stack.

Firstly, we will create a temporary stack name it as tmpStack. And then, we will pop the first element from the given input stack named instack. After that, we will compare the element popped from the input stack with the element present on the top of the temporary stack. If the element is smaller, pop the top element from the temporary stack and then push the element into it. Otherwise, if the element is greater, push it directly into a temporary stack. Repeat the above steps until the input stack is not empty. Now the sorted element is in the temporary stack. Lastly, Print the temporary stack.

Examples:

Here are some examples of input and output stack:

Input  : [32, 1, 26, 65, 20, 12]
Output : [1, 12, 20, 26, 32, 65]

Input  : [9, 5, 3, 16, 29, 80]
Output : [3, 5, 9, 16, 29, 80]

 

Program:

Now, let’s begin to write code for Sorting stack using temporary Stacks using the above concept described –

// C++ program to sort a stack using an another stack. 


#include <bits/stdc++.h> 
using namespace std; 
  
 
s<int> sortStack(s<int> &instack) 
{ 
    s<int> tmpStack; 
    while (!instack.empty()) 
    {  
        int tmp = instack.top(); 
        instack.pop(); 
        // while temporary stack is not empty
        //top of stack is greater than temp
        while (!tmpStack.empty() && tmpStack.top() < tmp) 
        { 
            // pop from temporary stack
             instack.push(tmpStack.top()); 
            //push it into input stack 
             tmpStack.pop(); 
        } 
  
        // push temp in tempory of stack 
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
// main function 
int main() 
{ 
    s<int> input; 
    input.push(26); 
    input.push(4); 
    input.push(19); 
    input.push(66); 
    input.push(18); 
    input.push(9); 
  
    // Print the temporary stack 
    s<int> tmpStack = sortStack(instack); 
    cout << "Sorted numbers are:\t"; 
  
    while (!tmpStack.empty()) 
    { 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
} 

Output:

Output for the given input in the above-given program.

Given Input- [ 26 , 4 , 19 , 66 , 18 , 9 ]

Sorted numbers are:
[4, 9, 18, 19, 26, 66]

 

Thank you!

I hope this will help you.

Check out the solution for more –

2 responses to “Sort stack using temporary Stacks in C++”

  1. Aman Kumar says:

    Very nice explanation.
    Mam please explain how to sort a stack using recursion in C++.
    Thank you..

  2. Anurag says:

    A very good and to the point explanation…thanks a lot..it helped me a lot …

Leave a Reply

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