Reverse a stack "in-place"

While i am searchig data structure questions on
the net, i encountered a very nice question
about stacks.Thanks Gowri Kumar for this
question and solution.

Write a C Program to reverse a stack "in place"
using recursion ?
You can only use the following ADT functions
on Stack:
IsEmpty
IsFull
Push
Pop
Top

What we require is:
Before : A B C D
After : D C B A

Before : A B C D
Step 1 : D A B C
Step 2 : D C A B
Step 3 : D C B A

Basically, at each step I am bringing the
bottom most element to the top of the
stack and pushing all the other elements one
down (this I call Percolate, (pecolating up).

void percolate_up( stack_t *stack ) {
    int a, b;
    if ( !stack ) return;
    a = Pop( stack );
    if ( isEmpty( stack ) ) {
        Push( stack, a );
        return;
    }
    percolate_up( stack );
    b = Pop( stack );
    Push( stack, a );
    Push( stack, b );
}

Before(Step 0) : A B C D
After (Step 1) : D A B C

| A B C D
a = A | B C D
a = B | C D
Now only two elements in the stack, do a
direct reversal
a = C | D
b = D |
Push(a) | C
Push(b) | D C
b = D
Push(a) | B C
Push(b) | D B C
b = D | B C
Push(a) | A B C
Push(b) | D A B C

void reverse_stack( stack_t * stack ) {
    int a;
    if ( !stack ) return;
    if ( isEmpty( stack ) ) {
        return;
    }
    percolate_up( stack );
    a = Pop( stack );
    reverse_stack( stack );
    Push( stack, a );
}

I do it in the following steps:
Before : A B C D

After one PercolateUp
Step 1 : D A B C
After one PercolateUp
Step 1 : D A B C

D is in right postion, Pop it and do the Reverse
on the remaining elements. After the reverse
of remaining elements, push the element which
we stored earlier.

PercolateUp reminds me the Bubble Sort,
which has a similar work mechanism.
Bubble sort moves the largest element
to the end of the list in each step
and Percolate function moves
the bottom element to the top of the
list in each step similarly.






Sorting a Stack "in-place"
Lets think about how to sort a stack
by stick to "in-place".
Actually, i have given a hint when mentioned
about the similarity between PercolateUp and
Bubble Sort algorithm.
Make some changes on PercolateUp:

void sorting_percolate_up( stack_t * stack ) {
    int a, b;
    a = Pop( stack );
    if ( isEmpty( stack ) ) {
        Push( stack, a );
        return;
    }
    sorting_percolate_up( stack );
    b = Pop( stack );
    if ( a < b ) {
        Push( stack, b );
        Push( stack, a );
    } else {
        Push( stack, a );
        Push( stack, b );
    }
}

void sort_stack( stack_t * stack ) {
    int a;
    if ( !stack ) return;
    if ( isEmpty( stack ) ) return;
    sorting_percolate_up( stack );
    a = Pop( stack );
    sort_stack( stack );

    Push( stack, a );

}

Now, you have a stack sort function,
by making a few changes.
that's all :)