How to sort a stack using recursion in C++

Learn how to sort a stack using a recursion problem using C++. Here, We will write program code to sort a given unsorted stack into ascending order with the help of recursion.

Firstly, We will pop all the elements from the stack one by one until the stack becomes empty. After being empty, start inserting the poped elements one by one back into the stack into sorted order.

Now the sorted element is in the stack. Lastly, Print the elements from the stack.

Examples:

Here are some examples of input and output stack:

Input  : [3, 21, 26, 11, 17, 13]
Output : [3, 11, 13, 17, 21, 26]

Input  : [1, 7, 9, 3, 5]
Output : [1, 3, 5, 7, 9]

Program:

#include <iostream>
using namespace std;


struct list
{
    int data;
    struct list *next;
};

void initialList(struct list **l)
{
    *l = NULL;
}

// Function to check whether list is empty or not
int isEmpty(struct list *l)
{
    if (l == NULL)
        return 1;
    return 0;
}

// Function to push an item into list
void push(struct list **l, int x)
{
    struct list *s = (struct list *)malloc(sizeof(*s));

    if (s == NULL)
    {
        fprintf(stderr, "Failed to allocate memory.\n");
        return;
    }
    s->data = x;
    s->next = *l;
    *l = s;
}

// Function to remove an item from list
int pop(struct list **l)
{
    int x;
    struct list *tempt;

    x = (*l)->data;
    tempt = *l;
    (*l) = (*l)->next;
    free(tempt);

    return x;
}

// Function to find top item
int top(struct list *l)
{
    return (l->data);
}

// Function to insert an item in sorted way
void sorted(struct list **l, int x)
{

    if (isEmpty(*l) or x > top(*l))
    {
        push(l, x);
        return;
    }

    // If top is greater, remove the top item and recur
    int tempt = pop(l);
    sorted(l, x);

    // Put back the top item removed earlier
    push(l, tempt);
}

// Function to sort stack
void sortList(struct list **l)
{
    // If list is not empty
    if (!isEmpty(*l))
    {
        // Remove the top item
        int x = pop(l);
        sortList(l);

        // Push item back in sorted list
        sorted(l, x);
    }
}

// Function to print list
void printList(struct list *l)
{
    while (l)
    {
        cout << l->data << " ";
        l = l->next;
    }
    cout << "\n";
}

// Main Program
int main(void)
{
    struct list *top;

    initialList(&top);
    push(&top, 1);
    push(&top, 7);
    push(&top, 3);
    push(&top, 9);
    push(&top, 5);

    cout << "Input :\n";
    printList(top);

    sortList(&top);
    cout << "\n";

    cout << "Output :\n";
    printList(top);
    return 0;
}

Output:

Output for the given input in the above-given program.

Output : [1, 3, 5, 7, 9]

Thank you!

I hope this will help you.

atomic_flag in C++

Templates in C++