Ex$3.$ Sort them out

$30$ points

Task # $1$

Implement function void stack$\_$sort$($stack& s$),$ which sorts the elements of the received stack. The best way to solve such a question in real$-$life is to copy all the elements of the stack into an array, sort the array using an efficient sorting algorithm, and then copy back all the elements. The $($unrealistic$)$ catch in this question is that you are not allowed to use, queues, arrays, lists, sets, vectors or maps. You are only allowed to define and use other stacks, but nothing else.

Task # $2$

Implement function void freq$\_$sort$($vector& v$),$ which sorts the elements of v $($regardless of their type$)$ based on their frequency in non$-$decreasing order. If two elements have the same frequency, then the smaller element appears before the larger. For example, if v $=\{2,5,3,3,9,9,2,2,2,5,3\},$ then v becomes $\{5,5,9,9,3,3,3,2,2,2,2\}.$