Implementing stack using queues and vice versa

To implement stack using queues, with two cases : constant insertion time, linear removal time and vice-a-versa, see this stack overflow discussion

To implement a queue using two stacks,

// Basic solution
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( !s1.empty() ) s1.push(t);
        else  s2.push(t);
    }

    T dequeue()
    {
        T t;
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        return __dequeue(s1,s2);
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

// optimized solution : by saving the last operation
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( last_operation == Dequeue ) 
            move( s2,s1);
        s1.push(t);
        last_operation = Enqueue;
    }

    T dequeue()
    {
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        // if the last operation was dequeue, the required element
        // is already on the temp usage stack s2
        if ( last_operation == Dequeue )
            return s2.pop();

        T t= __dequeue(s1,s2);
        last_operation = Dequeue;
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

Also there is a interesting solution in Algorithms and Programming: Problems and Solutions - Page 90

We maintain the following invariant relation: stacks whose bottoms are
put together, form the queue. (In other words, listing all elements of one stack from
top to bottom and then of the other stack from bottom to top, we list all the queue
elements in the proper order.) To add an element to the queue, it is enough to add it to
one of the stacks. To check if the queue is empty, we must check that both stacks are
empty. When taking the first element from the queue, we should distinguish between
two cases. If the stack that contains the first element is not empty, there is no problem.
If that stack is empty, the required element is buried under all the elements of the
second stack. In this case, we move all the elements one-by-one onto the first stack
(their ordering is reversed) and return to the first case.
The number of operations for this step is not limited by any constant. However,
the requirement posed in the problem is still met. Indeed, any element of the queue
can participate in such a process at most once during its presence in the queue.