**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();
}
}
```

**Output**

Sorted stack is: 2 4 6 8

**Time Complexity**

**O(n**^{2}) 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

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

**Happy Learning!**