[leet] Reverse Stack without using extra memory

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

template<typename STACK, typename T>
void pop(STACK&& stk, T&& val)
{
    if(stk.size() != 0)
    {
        auto tmp = stk.top();
        stk.pop();
        pop(stk, std::forward<T>(val));
        stk.push(tmp);
    }
    else
    {
        stk.push(std::forward<T>(val));
    }
}

template<typename STACK>
void reverse(STACK&& stk)
{
    if (stk.size() != 0)
    {
        auto tmp = stk.top();
        stk.pop();
        reverse(stk);
        pop(stk, tmp);
    }
}

int main()
{
    stack<int> stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    stk.push(4);
    reverse(stk);
    cout << stk.top() << endl;
    stk.pop();
    cout << stk.top() << endl;
    stk.pop();
    cout << stk.top() << endl;
    stk.pop();
    cout << stk.top() << endl;
    stk.pop();
}