Sorting a Stack Using a Temporary Stack

Sorting a Stack Using a Temporary Stack
Sorting a Stack Using a Temporary Stack

Introduction

Sorting a stack is one of the frequently asked questions in interviews. Sorting a stack could be tricky and challenging, but don’t worry; today, in this article, we will discuss this problem in-depth and make it a cakewalk for you!

But before starting, let’s take a look at the problem statement.

“Given a stack, sort the elements inside it in ascending order using only push and pop operation.”

The problem statement is self-explanatory, and we could implement this in two ways: either by using recursion or a temporary stack.

In this blog, we would discuss sorting a stack using a temporary stack.

We have already discussed sorting a stack using recursion in this blog.

But before moving to a solution, let’s discuss some basics of stacks.

Stack

Stack is a linear data structure similar to arrays and linked lists that allow us to store and retrieve data sequentially. In general, insertion operation is called “push,” and deletion operation is called “pop.” They are helpful when dynamic addition and deletion of elements are required.

 Push_Operation
 Push Operation
 Pop_Operation
 Pop Operation

At any given time, one can only access the top element of a stack. Due to this reason, it is a LIFO (Last In First Out) data structure. In this, the element added last is accessed first. The time complexity for all operations in a stack is O(1), making it efficient and improving performance.

Check out Stack Notes to learn stack in detail.

blog banner 1

Recommended: Please try to solve Reverse Stack Using Recursion on “CODESTUDIO” first before moving on to the solution.

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.

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(n2) 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.

Key Takeaways

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 take a look at the recursive approach for sorting a stack here.

If you are a beginner in coding and want to learn DSA, you can look out for our guided path for DSA, which is absolutely free!

If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at Code Studio.

Happy Learning! 

By: Pranchal Agrahari