Reverse a stack and a queue

Reverse a stack using standard stack operations like push(), pop(), isEmpty().

Strategy:

Even recursion will take extra space, but, the purpose of the question is to come up with a recursive implementation. First, we will implement a function "insertAtBottom()" which inserts an element at the bottom of the stack. And then we will use this function to implement "reverseStack()"

Algo:
- recursively empty the stack.
- add elements back using "insertAtBottom()" 

Code:

void insertAtBottom(stack& s, int x)
{
    if(s.empty())
    {
        s.push(x);
        return;
    }

    int a = s.top();
    s.pop();
    insertAtBottom(s, x);
    s.push(a);
}

void reverseStack(stack& s)
{
    if(s.empty())
        return;

    int a = s.top();
    s.pop();
    reverseStack(s);
    insertAtBottom(s, a);
}

int main()
{
    stack s;

    s.push(5);
    s.push(4);
    s.push(2);
    s.push(7);
    s.push(9);

    //current stack: top - 9 7 2 4 5 - bottom
   
    reverseStack(s);

    //reversed stack: top - 5 4 2 7 9 - bottom
   
    while(!s.empty())
    {
        printf("%d ", s.top());
        s.pop();
    }
    printf("\n");

    return 1;
}

Reverse a queue in O(n).

Strategy:Using a stack
#include<iostream>

//add std library for stack and queue
#include<stack>
#include<queue>
using namespace std;

int main() {

    //define queue and stack ADT
    queue <int> Q;
    stack <int> st;

    //enqueue Q
    Q.push(1);
    Q.push(2);
    Q.push(3);
    Q.push(4);
    Q.push(5);
    Q.push(6);
    Q.push(7);
    Q.push(8);
    Q.push(9);
    Q.push(10);

    //dequeue Q & push elements to st
    while (!Q.empty()){
        st.push(Q.front());
        Q.pop();
    }

   //pop elements from st and enQueue again Q
    while (!st.empty()){
        Q.push(st.top());
        st.pop();
    }

    //finally print queue elements in reverse order
    while (!Q.empty()){
        cout << Q.front();
        Q.pop();
    }
    return 0;

}