# Sort a Stack Using Temporary Stack

Sort a Stack Using Temporary Stack” is again one of the favorite technical interview problems based on stack data structure. Here, in this problem, we are given a stack and our task is to sort the elements of given stack using help of another temporary stack. The top of the stack will contain the largest element and bottom of the stack will contain smallest element.

Example:

```Given Stack: [ 12, 15, 5, 13, 4, 7 ]
/*’12’ is bottom element and ‘7’ is top element */
Sorted Stack: [4, 5, 7, 12, 13, 15]

Given Stack: [50, 40, 30, 20, 10]
Sorted Stack: [10, 20, 30, 40, 50]```

The solution of above problem is quite tricky and requires some logical thinking. The steps required to Sort a Stack Using Temporary Stack are as follows:

1. Create an empty temporary stack ‘tmp’.
2. While original stack ‘st’ is not empty, perform the following operation:

Pop out the top element of the original stack ‘st’ and store it to temporary variable ‘temp’.

If the temporary stack ‘tmp’ is empty, then push the ‘temp’ element into the stack.

Else if, check if the top element of the temporary stack is smaller than or equal to the ‘temp’ or not. If yes, push the ‘temp’ into the stack.

Else, pop the elements from the temporary stack ‘tmp’ and push them back into the original stack ‘st’ until top element of the stack is smaller than or equal to the ‘temp’ element or stack is empty. Then, push ‘temp’ into the stack.

3. Finally, in the temporary stack the elements are present in the sorted order where top element will be the greatest element and bottom element will be the smallest element.

Derivation of Algorithm of Sort a Stack Using Temporary Stack using an Example:

```Suppose the elements of the original stack are:
[12, 45, 11, 7, 89, 33], where ‘33’ is at the top of the stack and ‘12’ is at the bottom of the stack.

Initially,
Original Stack: [12, 45, 11, 7, 89, 33]             /* ‘33’ is at top */
Temporary Stack: []

#Step1: Pop ‘33’ from Original Stack and store it into temporary variable ‘temp’ and check whether stack is empty or top element of stack is smaller than or equal to ‘temp’ element or not. If yes, push ‘temp’ into the Temporary Stack. So,
Original Stack: [12, 45, 11, 7, 89]                   /* ‘89’ is at top */
Temporary Stack: [33]

#Step2: Pop ‘89’ from Original Stack and store it into temporary variable ‘temp’ and check whether stack is empty or top element of stack is smaller than or equal to ‘temp’ element or not. If yes, push ‘temp’ into the Temporary Stack. So,
Original Stack: [12, 45, 11, 7]             /* ‘7’ is at top */
Temporary Stack: [33,89]

#Step3: Pop ‘7’ from Original Stack and store it into temporary variable ‘temp’ and check whether stack is empty or top element of stack is smaller than or equal to ‘temp’ element or not. If no, then pop the elements of the stack until stack is empty or top element of the stack is smaller than or equal to ‘temp’ element. So,
Original Stack: [12, 45, 11, 7]            /* ‘7’ is at top */
Temporary Stack: [33,89]

Temp = 7

Original Stack: [12, 45, 11]
Temporary Stack:[33,89]

Original Stack: [12, 45, 11,89]
Temporary Stack:[33]

Original Stack: [12, 45, 11,89,33]
Temporary Stack:[]

Then, push the temp into the stack.

Original Stack: [12, 45, 11,89,33]
Temporary Stack:[7]

#Step4:

Original Stack: [12, 45, 11,89]
Temporary Stack:[7,33]

#Step5:

Original Stack: [12, 45, 11]
Temporary Stack:[7,33,89]

#Step6:

Original Stack: [12, 45]
Temporary Stack:[7,33,89]

Temp = 11

Original Stack: [12, 45,89]
Temporary Stack:[7,33]

Original Stack: [12, 45,89,33]
Temporary Stack:[7]

Original Stack: [12, 45,89,33]
Temporary Stack:[7,11]

#Step7:

Original Stack: [12, 45,89]
Temporary Stack:[7,11,33]

#Step8:

Original Stack: [12, 45]
Temporary Stack:[7,11,33,89]

#Step9:

Original Stack: [12]
Temporary Stack:[7,11,33,89]

Temp = 45

Original Stack: [12,89]
Temporary Stack:[7,11,33]

Original Stack: [12,89]
Temporary Stack:[7,11,33,45]

#Step10:

Original Stack: [12]
Temporary Stack:[7,11,33,45,89]

#Step11:

Original Stack: []
Temporary Stack:[7,11,33,45,89]

Temp = 12

Original Stack: [89]
Temporary Stack:[7,11,33,45]
Original Stack: [89,45]
Temporary Stack:[7,11,33]

Original Stack: [89,45,33]
Temporary Stack:[7,11]

Original Stack: [89,45,33]
Temporary Stack:[7,11,12]

#Step12,13,14:

Original Stack: [89,45]
Temporary Stack:[7,11,12,33]

Original Stack: [89]
Temporary Stack:[7,11,12,33,45]

Original Stack: []
Temporary Stack:[7,11,12,33,45,89]```

### C++ Program to Sort a Stack Using Temporary Stack is as follows:

```/* C++ Program to Sort a Stack Using Temporary Stack */
#include<bits/stdc++.h>
using namespace std;
stack<int> sortStack(stack<int>&st)
{
stack<int> tmp;

while(!st.empty())
{
/*
Pop the top element of the Original
Stack and store it into 'temp' Variable
*/
int temp = st.top();
st.pop();

/*
If the Temporary stack 'tmp' is empty or top element of the stack is smaller
than or equal to 'temp' variable, then push 'temp' into temporary stack 'tmp'
*/
if(tmp.empty() || tmp.top() <= temp)
{
tmp.push(temp);
}
else
{
/*
Else, pop the elements from the temporary stack ‘tmp’ and push them back into the
original stack ‘st’ until top element of the stack is smaller than or equal to the
‘temp’ element and stack is empty. Then, push ‘temp’ into the stack.
*/
while(!tmp.empty() && tmp.top() > temp)
{
st.push(tmp.top());
tmp.pop();
}
tmp.push(temp);
}
}
return tmp;
}
int main()
{
stack<int>st;

/* Push Some Random Elements into the Stack */
st.push(12);
st.push(45);
st.push(11);
st.push(7);
st.push(89);
st.push(33);

stack<int> tmp = sortStack(st);
cout<<"Stack Elements in Sorted Order are:\n";
while(!tmp.empty())
{
cout<<tmp.top()<<" ";
tmp.pop();
}

}
```
```OUTPUT:
Stack Elements in Sorted Order are:
89 45 33 12 11 7
The worst case time complexity of this solution is O(n2)```

Related Posts:

### 2 Responses

1. Very good post. I am facing many of these issues as well.. Agace Hal Roswell

2. porno says:

Muchos Gracias for your article post. Really looking forward to read more. Much obliged. Melba Jasun Volny