Q:

C program to reverse a stack using recursion

belongs to collection: C programs - Stacks and Queues

0

This C program reverses the elements of a stack using Recursion. Here, Stack is represented using a linked list. A linked list is an ordered set of data elements, each containing a link to its successor.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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.

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
C program to implement Stack using Linked List... >>
<< C program to implement stack using array...