-
Insert function.
- If stack is empty OR
x
is the largest element, then we can directly insert it at last position. - else we need to insert
x
at it's correct position. - Get the top element of the stack and reduce its size by 1.
- Insert
x
recursively. - finally insert value which is poped.
- If stack is empty OR
-
Sort function.
- If stack contains only one element then it is sorted iteself.Return.
- Get the last element of the stack.
- Reduce the size of input for recursion.
- Recursively sort remaining the stack which has one element less.
- Insert the element in sorted stack at its right position.
#include <bits/stdc++.h>
void insertSorted(stack<int>& st, int x) {
if (st.empty() || st.top() <= x) {
st.push(x);
} else {
int temp = st.top();
st.pop();
insertSorted(st, x);
st.push(temp);
}
}
void sortStack(stack<int>& stack)
{
if (stack.empty())
return;
int x = stack.top();
stack.pop();
sortStack(stack);
insertSorted(stack, x);
}