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.
Leave a Reply