1.
Introduction
2.
Stack
3.
Algorithm for sorting a stack
4.
Pseudocode
5.
Implementation In C++
6.
6.1.
What is a Stack data structure?
6.2.
What are the main operations performed on a stack?
6.3.
What is the Push operation in a Stack?
6.4.
What is the Pop operation in a Stack?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sorting a Stack Using a Temporary Stack

Nilesh Kumar
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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 blogBut before moving to a solution, letâ€™s discuss some basics of stacks.

Recommended Topic, Binary to Hex Converter,C Static Function

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.

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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(n2as 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

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!

Live masterclass