Sorting a Stack Using a Temporary Stack

Algorithm for sorting a stack

This approach of sorting a stack using a temporary stack is simple to implement. We will make a function sortStack() which returns a sorted stack.

In the function sortStack(), we will make a temporary stack tempStack and will push the elements of the input stack into tempStack. While pushing the elements into tempStack, we will ensure that the top of the tempStack is greater than the element we are pushing in it. If the top is smaller than the element we are pushing, we will pop the elements from tempStack until its top is greater than the element we are inserting, or it is empty.

For every element that we are popping from tempStack, we will push it into the input stack. We will perform this operation until the input stack becomes empty.

Click on the following links to read further: Features of C Language and Short int in C Programming

Pseudocode

sortStack()
1.Make temporary stack tempStack.
2.While the input stack is not empty, we will perform this
Pop an element from the input stack and call it temp.
While tempStack is not empty and the top of tempStack is smaller than temp, pop elements from tempStack and push them into the input stack.
Push temp into the tempStack.
3.The sorted numbers are in tempStack return tempStack.

Below is the dry run of this pseudocode.

input:[6,8,2,4]
tempStack:[]

Popped element:4
input:[6,8,2]
tempStack:[4]

Popped element:2
input:[6,8]
tempStack:[4,2]

Popped element:8
input:[6,2,4]
tempStack:[8]

Popped element:4
input:[6,2]
tempStack:[8,4]

Popped element:2
input:[6]
tempStack:[8,4,2]

Popped element:6
input:[2,4]
tempStack:[8,6]

Popped element:4
input:[2]
tempStack:[8,6,4]

Popped element:2
input:[]
tempStack:[8,6,4,2]

Final sorted stack:[8,6,4,2]

Implementation In C++

Below is the implementation of the algorithm for sorting a stack in c++. For simplicity, we will use the stack from C++ STL.

// c++ code for sorting a stack

#include<iostream>
#include<stack>

using namespace std;

// function for sorting a stack
stack<int> sortStack(stack<int> & input)
{
    stack<int> tempStack;

    while(!input.empty())
    {
        int temp=input.top();
        input.pop();
       
        /*while tempStack is not empty and
        top of temp stack is smaller than temp */
       
        while(!tempStack.empty()&&tempStack.top()<temp)
        {
            input.push(tempStack.top());
            tempStack.pop();
        }
        tempStack.push(temp);
    }
    return tempStack;
}

int main()
{
    stack<int>input;
    input.push(6);
    input.push(8);
    input.push(2);
    input.push(4);
   
    stack<int>s=sortStack(input);
   
    cout<<"Sorted stack is: ";
   
    //Printing the sorted Stack
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }

}

You can also try this code with Online C++ Compiler

Run Code

Output

Sorted stack is: 2 4 6 8

Time Complexity

O(n²) as in the worst case, we will pop each element from the tempStack repeatedly to insert a new element.

Space complexity

 O(n) as we are using a tempStack to store the sorted elements

Also Read - Selection Sort in C

Must Read Stack Operations

Frequently Asked Questions

What is a Stack data structure?

A Stack is a data structure that follows the Last In First Out (LIFO) principle. It means the element which is inserted last is the first one to be removed.

What are the main operations performed on a stack?

The main operations performed on a stack are Push, Pop, and Peek (or Top).

What is the Push operation in a Stack?

The Push operation is used to insert an element into the stack. The new element is added to the top of the stack.

What is the Pop operation in a Stack?

The Pop operation is used to remove the topmost element from the stack. It returns the removed element.

Conclusion

This article discussed sorting a stack using a temporary stack with all crucial aspects necessary to implement it. We discussed the algorithm in detail and implemented the program for sorting a stack in c++. We also took a look at the time and space complexity of the program. You can also refer

• Introduction to C++
• Data Structure

You can also consider our Mern Stack Course to give your career an edge over others.

Happy Learning!