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.

f(f(n)) = -n

Originally from stackoverflow
While working on this puzzle, became confused, but this can be simplified if we first write the state diagram and then the code. The state diagram should consider odd/even and +ve/-ve numbers.
A simple control flow can be as follows:
A: 1 → 2
B: 2 → -1
C: -1 → -2
D: -2 → 1
E: 1 → 2

Notice that E and A are same.
Once we have this,

if n is +ve:
   if n is odd : return n+1
   if n is even : return -1* (n-1)
else if n is -ve:
   if n is odd : return n-1
   if n is even : return -1 * (n+1)

We get the highest rated solution on stackoverflow.

Sorting and array of 0 and 1's in single pass

Question from Princeton.edu's sorting and searching :

Partitioning. Write a static method that sorts a Comparable array that is known to have at most two different values.

Hint: Maintain two pointers, one starting at the left end and moving right, the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

Solution in python:

"""
Sort an array of 0's and 1's

Loop invariant
[0 0 0 0 0 0 |----unknown-----| 1 1 1 1 1 1]
             i                j
All elements < i are 0
All element > j are 1
elements between i and j are unknown.
"""

a1 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1]
a2 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
a3 = [ 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]

def sort_01(a):
    i=0
    j=len(a)-1
    while i < j:
        while i < j and (a[i] < a[j] or a[i]==0): i += 1
        while i < j and a[i] <= a[j]: j -= 1
        if i < j: a[i],a[j] = 0,1
    print(a)

sort_01(a1)
sort_01(a2)
sort_01(a3)