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. Largest Rectangular Area in Histogram
  2. Length of Longest Valid Substring
  3. Reverse a String using Stack
  4. Implement two stacks in a single array
  5. Print Bracket Number
  6. Next Greater Frequency Element
  7. Infix to Postfix Conversion
  8. Infix to Prefix Conversion
  9. Prefix to Infix Conversion
  10. Prefix to Postfix Conversion
  11. Postfix to Infix Conversion
  12. Postfix to Prefix Conversion
  13. Check whether given Parentheses String are Balanced Parentheses or Not.
  14. Next Greater Element
  15. Find Minimum number of bracket reversals required to make an expression balanced.
  16. Implement Queue Using Two Stacks.
  17. Merge Overlapping Intervals using Stacks
  18. Implement Stack Using Linked List
  19. Program to count total number of words in a string.
  20. Program to find smallest and largest word of the String.

You may also like...

Leave a Reply

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