C Algorithm – Reverse a stack using recursion

Write a program to reverse a stack using recursion. You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:
isEmpty(S)
push(S)
pop(S)

Solution:
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

For example, let the input stack be

    1  <-- top
    2
    3
    4   

First 4 is inserted at the bottom.
    4 <-- top

Then 3 is inserted at the bottom
    4 <-- top    
    3

Then 2 is inserted at the bottom
    4 <-- top    
    3 
    2
     
Then 1 is inserted at the bottom
    4 <-- top    
    3 
    2
    1

So we need a function that inserts at the bottom of a stack using the above given basic stack function.

void insertAtBottom((): First pops all stack items and stores the popped item in function call stack using recursion. And when stack becomes empty, pushes new item and all items stored in call stack.

void reverse(): This function mainly uses insertAtBottom() to pop all items one by one and insert the popped items at the bottom.

[ad type=”banner”]

C Programming:

[pastacode lang=”c” manual=”%2F%2F%20C%20program%20to%20reverse%20a%20stack%20using%20recursion%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%23define%20bool%20int%0A%20%0A%2F*%20structure%20of%20a%20stack%20node%20*%2F%0Astruct%20sNode%0A%7B%0A%20%20%20%20char%20data%3B%0A%20%20%20%20struct%20sNode%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20Prototypes%20*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%3B%0Aint%20pop(struct%20sNode**%20top_ref)%3B%0Abool%20isEmpty(struct%20sNode*%20top)%3B%0Avoid%20print(struct%20sNode*%20top)%3B%0A%20%0A%2F%2F%20Below%20is%20a%20recursive%20function%20that%20inserts%20an%20element%0A%2F%2F%20at%20the%20bottom%20of%20a%20stack.%0Avoid%20insertAtBottom(struct%20sNode**%20top_ref%2C%20int%20item)%0A%7B%0A%20%20%20%20if%20(isEmpty(*top_ref))%0A%20%20%20%20%20%20%20%20push(top_ref%2C%20item)%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Hold%20all%20items%20in%20Function%20Call%20Stack%20until%20we%0A%20%20%20%20%20%20%20%20%20%20%20reach%20end%20of%20the%20stack.%20When%20the%20stack%20becomes%0A%20%20%20%20%20%20%20%20%20%20%20empty%2C%20the%20isEmpty(*top_ref)becomes%20true%2C%20the%0A%20%20%20%20%20%20%20%20%20%20%20above%20if%20part%20is%20executed%20and%20the%20item%20is%20inserted%0A%20%20%20%20%20%20%20%20%20%20%20at%20the%20bottom%20*%2F%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20pop(top_ref)%3B%0A%20%20%20%20%20%20%20%20insertAtBottom(top_ref%2C%20item)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Once%20the%20item%20is%20inserted%20at%20the%20bottom%2C%20push%20all%0A%20%20%20%20%20%20%20%20%20%20%20the%20items%20held%20in%20Function%20Call%20Stack%20*%2F%0A%20%20%20%20%20%20%20%20push(top_ref%2C%20temp)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Below%20is%20the%20function%20that%20reverses%20the%20given%20stack%20using%0A%2F%2F%20insertAtBottom()%0Avoid%20reverse(struct%20sNode**%20top_ref)%0A%7B%0A%20%20%20%20if%20(!isEmpty(*top_ref))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Hold%20all%20items%20in%20Function%20Call%20Stack%20until%20we%0A%20%20%20%20%20%20%20%20%20%20%20reach%20end%20of%20the%20stack%20*%2F%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20pop(top_ref)%3B%0A%20%20%20%20%20%20%20%20reverse(top_ref)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Insert%20all%20the%20items%20(held%20in%20Function%20Call%20Stack)%0A%20%20%20%20%20%20%20%20%20%20%20one%20by%20one%20from%20the%20bottom%20to%20top.%20Every%20item%20is%0A%20%20%20%20%20%20%20%20%20%20%20inserted%20at%20the%20bottom%20*%2F%0A%20%20%20%20%20%20%20%20insertAtBottom(top_ref%2C%20temp)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Driveer%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20sNode%20*s%20%3D%20NULL%3B%0A%20%20%20%20push(%26s%2C%204)%3B%0A%20%20%20%20push(%26s%2C%203)%3B%0A%20%20%20%20push(%26s%2C%202)%3B%0A%20%20%20%20push(%26s%2C%201)%3B%0A%20%0A%20%20%20%20printf(%22%5Cn%20Original%20Stack%20%22)%3B%0A%20%20%20%20print(s)%3B%0A%20%20%20%20reverse(%26s)%3B%0A%20%20%20%20printf(%22%5Cn%20Reversed%20Stack%20%22)%3B%0A%20%20%20%20print(s)%3B%0A%20%20%20%20return%200%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20check%20if%20the%20stack%20is%20empty%20*%2F%0Abool%20isEmpty(struct%20sNode*%20top)%0A%7B%0A%20%20%20%20return%20(top%20%3D%3D%20NULL)%3F%201%20%3A%200%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20push%20an%20item%20to%20stack*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20sNode*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20(struct%20sNode*)%20malloc(sizeof(struct%20sNode))%3B%0A%20%0A%20%20%20%20if%20(new_node%20%3D%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20exit(0)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*top_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*top_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20pop%20an%20item%20from%20stack*%2F%0Aint%20pop(struct%20sNode**%20top_ref)%0A%7B%0A%20%20%20%20char%20res%3B%0A%20%20%20%20struct%20sNode%20*top%3B%0A%20%0A%20%20%20%20%2F*If%20stack%20is%20empty%20then%20error%20*%2F%0A%20%20%20%20if%20(*top_ref%20%3D%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20exit(0)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20top%20%3D%20*top_ref%3B%0A%20%20%20%20%20%20%20%20res%20%3D%20top-%3Edata%3B%0A%20%20%20%20%20%20%20%20*top_ref%20%3D%20top-%3Enext%3B%0A%20%20%20%20%20%20%20%20free(top)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Functrion%20to%20pront%20a%20linked%20list%20*%2F%0Avoid%20print(struct%20sNode*%20top)%0A%7B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20while%20(top%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%20%25d%20%22%2C%20top-%3Edata)%3B%0A%20%20%20%20%20%20%20%20top%20%3D%20%20top-%3Enext%3B%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]

Output:

 Original Stack 
 1  2  3  4 
 Reversed Stack 
 4  3  2  1

[ad type=”banner”]