Sort A Stack Using Another Stack
Data structures are the building blocks of any programming language. There are different types of data structures available which are categorized into linear and non-linear data structures.
One of the most used linear data structures is a stack. Stack is simply an ordered collection of data elements where the addition or deletion of elements takes place from one end only. It follows a first in last out approach which simply means that the element that you will enter at first will be popped out at the end whereas the element you will enter at last will be popped out first.
However, one thing that you need to know here is that a stack can contain elements in unsorted order as well. A sorted stack is generally preferred because operations are easier to carry on a sorted stack.
But what do you do if you need to sort a stack?
If you are still figuring out how to sort a stack, we have come up with a guide to help you sort a stack with the help of another stack. However, let's begin with understanding how a stack works.
How does Stack work?
This linear data structure follows a LIFO approach which implies that the last item that you will enter will be popped out first. You can also consider an example of a pile of plates.
When you place an element on the top of the stack, it is known as a push operation whereas, when you delete an element from the stack, it is called a pop operation.
The working of stack data structure can be summarised as follows:
You will have to use a pointer named top to keep track of the uppermost element present in the stack.
When you Initialise the stack, keep the value of the top to -1. This is done in order to check if the given stack is empty or not.
While pushing a stack, we will have to increase the value of the top by 1 and at the same time, add the element on the index where the top has pointed.
Other than that, when we pop an element from a stack, we need to reduce the value of the top and print the value present at the index where the top was pointing.
Before you push an element in the stack, you need to check if the given stack is empty or not.
Other than that, when you pop an element, you need to check if the given stack is empty already.
So, this was all about how a stack works. Here, now we will discuss how you can sort a stack with the help of another stack. First, let's understand the problem statement.
Understanding The Problem Statement
You are given a stack of unsorted orders. You need to sort the elements of the given stack. Here, you can use another stack.
For instance, if you are given a stack: [ 4, 7 2]
The sorted stack must look like this: [2, 4, 7].
Algorithm To Sort A Stack
To begin with, initialise a temporary stack named tempstack.
While the original stack is not empty, carry out the following steps:
Pop an element to save it in the tempstack
Now, while tempstack is not null and the top of tempstack is greater, pop the element from tempstack and push it into the original stack.
Now, push the temp element in the tempstack.
You will receive all the numbers in sorted order in tempstack.
Working Example Of Sorting A Stack
So, now you have an idea of how you can sort a stack with the help of another stack. To make things clearer to you, let's go through a working example of the algorithm.
Input stack: [ 34, 31, 3, 98, 92, 23]
Element selected: 23
Input stack: [ 34, 31, 3, 92, 98]
Tempstack: 23
Element selected: 92
Input stack: [34, 31, 3, 98]
Tempstack: [23, 92]
Element selected: 98
Input stack: [34, 31, 3]
Tempstack: [23, 92, 98]
Element selected: 3
Input stack: [ 34, 31, 98, 92, 23]
Tempstack: [3]
Element selected: 23
Input stack: [34, 31, 98, 92]
Tempstack: [3, 23]
Element selected: 92
Input stack: [34, 31, 98]
Tempstack: [3, 23, 92]
Element selected: 98
Input stack: [34, 31]
Tempstack: [3, 23, 92, 98]
Element selected: 31
Input stack: [ 34, 98, 92]
Tempstack: [3, 23, 31]
Element selected: 92
Input stack: [ 34, 98]
Tempstack: [3, 23, 31, 92]
Element selected: 98
Input stack: [ 34]
Tempstack: [3, 23, 31, 92, 98]
Element selected: 34
Input stack: [98, 92]
Tempstack: [ 3, 23, 31, 34]
Element selected: 92
Input stack: [98]
Tempstack: [ 3, 23, 31, 34, 92]
Element selected: 98
Input stack: []
Tempstack: [ 3, 23, 31, 34, 92, 98]
So, this is how the temporary stack will store all the elements of the original stack in the sorted order.
Complexity Analysis
Time complexity: The time complexity of this method is calculated as O(n2). Here, n is the total number of elements present in the stack.
Space complexity: Now that we are using an additional stack of size n, the space complexity will be calculated as O(n).
Along with sorting a stack, another problem which is often asked by interviewers is Partition equal subset sum problem.
In this problem, you will have a set of positive numbers. You need to find the partition of the set into two subsets in such a way that the sum of the elements present in both of the subsets is equal. For instance, you are given an input: {1, 3, 4 2}. The output will be TRUE.
Explanation: subsets possible from the given set are {1, 4} and {2, 3}.
Conclusion
A Stack is one of the commonly used data structures as it is easy to comprehend and is dynamic in nature.
However, when it comes to working on a stack in real life, a sorted stack is preferred as it makes processes easier.
Therefore, it is often asked by interviewers to sort a stack. To sort it, you can use a temporary stack and store the elements in sorted order in the temporary stack.
Comments
Post a Comment