Sort stack using another stack
The problem of Sort Stack using Another Stack involves sorting the elements of a given stack in ascending order using only one additional auxiliary stack. The task is to implement a function that takes an unsorted stack as input and returns a new stack containing the sorted elements.
Problem Statement
Given an unsorted stack, implement a function sortStack(Stack<Integer> s)
that takes this
stack as input and returns a new stack containing the sorted elements in ascending order. The original stack
should remain unchanged.
Example
Consider the following stack:
10 <- Top
6
5
8
3
12
1
9
7
4
After sorting the stack using another stack, the result should be:
1 <- Top
3
4
5
6
7
8
9
10
12
Idea to Solve the Problem
To sort the stack using another stack, we can use the following approach:
- Create an auxiliary stack to store the sorted elements.
- While the original stack is not empty, perform the following steps:
- Pop an element
temp
from the original stack. - While the auxiliary stack is not empty and the top element of the auxiliary stack is less than
temp
, pop the top element from the auxiliary stack and push it back to the original stack. - Push
temp
onto the auxiliary stack.
- Pop an element
- After all elements are processed, the auxiliary stack will contain the sorted elements in descending order.
- To get the sorted elements in ascending order, we can simply pop elements from the auxiliary stack and push them back to the original stack.
Algorithm
- Create a new
Stack<Integer>
calledauxiliary
to store the sorted elements. - While the original stack
s
is not empty, do the following:- Pop the top element
temp
froms
. - While
auxiliary
is not empty and the top element ofauxiliary
is less thantemp
, pop the top element fromauxiliary
and push it back tos
. - Push
temp
ontoauxiliary
.
- Pop the top element
- The
auxiliary
stack now contains the sorted elements in descending order. - To get the sorted elements in ascending order, pop elements from
auxiliary
and push them back tos
. - Return the
auxiliary
stack, which now contains the sorted elements in ascending order.
Pseudocode
Function sortStack(Stack s):
Create a new Stack called auxiliary
While s is not empty:
Pop the top element temp from s
While auxiliary is not empty and auxiliary.peek() < temp:
Pop the top element from auxiliary and push it back to s
Push temp onto auxiliary
Return auxiliary
Code Solution
-
1) Sort stack using another stack in java
2) Sort stack using another stack in c++
3) Sort stack using another stack in c
4) Sort stack using another stack in c#
5) Sort stack using another stack in vb.net
6) Sort stack using another stack in php
7) Sort stack using another stack in node js
8) Sort stack using another stack in typescript
9) Sort stack using another stack in python
10) Sort stack using another stack in ruby
11) Sort stack using another stack in scala
12) Sort stack using another stack in swift
13) Sort stack using another stack in kotlin
14) Sort stack using another stack in golang
Time Complexity
The time complexity of the sortStack
function is O(N^2), where N is the number of elements in the
original stack. This is because for each element in the original stack, we may have to perform N operations in
the worst case to maintain the sorted order in the auxiliary stack. Therefore, the overall time complexity of
the sorting process is O(N^2).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment