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:

1. Check whether given Parentheses String are Balanced Parentheses or Not.
2. Next Greater Element
3. Find Minimum number of bracket reversals required to make an expression balanced.
4. Implement Queue Using Two Stacks.
5. Merge Overlapping Intervals using Stacks
6. Implement Stack Using Linked List
7. Largest Rectangular Area in Histogram
8. Length of Longest Valid Substring
9. Reverse a String using Stack
10. Implement two stacks in a single array
11. Print Bracket Number
12. Next Greater Frequency Element
13. Find Most Frequent Character of the String.
14. Check Anagram Strings.
15. Check Whether Given String is Palindromic Anagram or Not.
16. Check Whether Given String is Panagram or Not.
17. Find First Non-Repeating Character of the String.
18. Find Most Frequent Element of the Array.
19. Find Pair in an Array with Given Sum.
20. Find First Repeating Element of an Array.