C program to reverse a stack using recursion

C program to reverse a stack using recursion - Source code

struct node
{
    int n;
    struct node *next;
};
 
void generate_stack(struct node **);
void display_stack(struct node *);
void stack_reverse(struct node **, struct node **);
void delete(struct node **);
 
int main()
{
    struct node *head = NULL;
 
    generate_stack(&head);
    printf("\nThe sequence of contents in stack\n");
    display_stack(head);
    printf("\nReversing the contents of the stack\n");
    if (head != NULL)
    {
        stack_reverse(&head, &(head->next));
    }
    printf("\nThe contents in stack after reversal\n");
    display_stack(head);
    delete(&head);
 
    return 0;
}
 
void stack_reverse(struct node **head, struct node **head_next)
{
    struct node *temp;
 
    if (*head_next != NULL)
    {
         temp = (*head_next)->next;
        (*head_next)->next = (*head);
        *head = *head_next;
        *head_next = temp;
        stack_reverse(head, head_next);
    }
}
 
void display_stack(struct node *head)
{
    if (head != NULL)
    {
        printf("%d  ", head->n);
        display_stack(head->next);
    }
}
 
void generate_stack(struct node **head)
{
    int num, i;
    struct node *temp;
 
    printf("Enter length of list: ");
    scanf("%d", &num);
    for (i = num; i > 0; i--)
    {
        temp = (struct node *)malloc(sizeof(struct node));
        temp->n = i;
        if (*head == NULL)
        {
            *head = temp;
            (*head)->next = NULL;
        }
        else
        {
            temp->next = *head;
            *head = temp;
        }
    }
}
 
void delete(struct node **head)
{
    struct node *temp;
    while (*head != NULL)
    {
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

Program Output

Enter length of list: 20

The sequence of contents in stack
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
Reversing the contents of the stack

The contents in stack after reversal
20  19  18  17  16  15  14  13  12  11  10  9  8  7  6  5  4  3  2  1

Program Explanation

1. This C program comprises of four major functions. These functions are for generating stack, to display the generated stack, to reverse the stack and finally to free the memory.

2. Here stack in implemented using a linked list. Stack is simply created in the form of a list starting form 1 up to the number entered by the user.

3. The stack is reversed using the recursion. The function stack_reverse is called recursively until the next of node becomes null. The elements of the list are swapped with the next element using a temporary list.

4. Function display_stack is used to display the contents of the list at any time.