VietMX Staff asked 3 years ago
A stack performs push and pop operations. So, the push and pop operations are carried out between the input_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack.
Solution Steps:
- Create a temporary stack say aux_stack.
- Repeat until the input_stack is not empty
- Pop an element from input_stack call it temp_value.
- While aux_stack is not empty and top of the aux_stack < temp_value, pop data from aux_stack and push it to the input_stack
- Push temp_value to the aux_stack
- return the aux_stack.
Implementation
Stack sort_stack(Stack input_stack) {
Stack aux_stack
while(!input_stack.empty())
{
int temp_value = input_stack.top()
input_stack.pop()
while(!aux_stack.empty() and aux_stack.top() > temp) {
input_stack.push(aux_stack.top())
aux_stack.pop()
}
aux_stack.push(temp_value)
}
return aux_stack
}