{"id":27076,"date":"2018-01-02T22:09:18","date_gmt":"2018-01-02T16:39:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27076"},"modified":"2018-01-02T22:09:18","modified_gmt":"2018-01-02T16:39:18","slug":"c-algorithm-sort-stack-using-recursion","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-sort-stack-using-recursion\/","title":{"rendered":"C Algorithm – Sort a stack using recursion"},"content":{"rendered":"

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:<\/span><\/p>\n

is_empty(S)  : Tests whether stack is empty or not.\r\npush(S)\t     : Adds new element to the stack.\r\npop(S)\t     : Removes top element from the stack.\r\ntop(S)\t     : Returns value of the top element. Note that this\r\n               function does not remove element from the stack.<\/pre>\n
Example:<\/p>\n
Input:  -3  <--- Top\r\n        14 \r\n        18 \r\n        -5 \r\n        30 \r\n\r\nOutput: 30  <--- Top\r\n        18 \r\n        14 \r\n        -3 \r\n        -5<\/pre>\n
We strongly recommend you to minimize your browser and try this yourself first.<\/b>
\nThis problem is mainly a variant of Reverse stack using recursion.<\/p>\n
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 in sorted order. Here sorted order is important.<\/p>\n[ad type=”banner”]
\nAlgorithm<\/strong>
\nWe can use below algorithm to sort stack elements:<\/p>\n
sortStack(stack S)\r\n\tif stack is not empty:\r\n\t\ttemp = pop(S);  \r\n\t\tsortStack(S); \r\n\t\tsortedInsert(S, temp);\r\n<\/pre>\n
Below algorithm is to insert element is sorted order:<\/p>\n
sortedInsert(Stack S, element)\r\n\tif stack is empty OR element > top element\r\n\t\tpush(S, elem)\r\n\telse\r\n\t\ttemp = pop(S)\r\n\t\tsortedInsert(S, element)\r\n\t\tpush(S, temp)\r\n<\/pre>\n[ad type=”banner”]
\nIllustration:<\/strong><\/p>\n
Let given stack be\r\n-3\t<-- top of the stack\r\n14\r\n18\r\n-5\r\n30<\/pre>\n
Let us illustrate sorting of stack using above example:<\/p>\n
First pop all the elements from the stack and store poped element in variable ‘temp’. After poping all the elements function’s stack frame will look like:<\/p>\n
temp = -3\t--> stack frame #1\r\ntemp = 14\t--> stack frame #2\r\ntemp = 18\t--> stack frame #3\r\ntemp = -5\t--> stack frame #4\r\ntemp = 30       --> stack frame #5<\/pre>\n
Now stack is empty and ‘insert_in_sorted_order()’ function is called and it inserts 30 (from stack frame #5) at the bottom of the stack. Now stack looks like below:<\/p>\n
30<\/b><\/span>\t<-- top of the stack<\/pre>\n
Now next element i.e. -5 (from stack frame #4) is picked. Since -5 < 30, -5 is inserted at the bottom of stack. Now stack becomes:<\/p>\n
30\t<-- top of the stack\r\n-5<\/b><\/span><\/pre>\n
Next 18 (from stack frame #3) is picked. Since 18 < 30, 18 is inserted below 30. Now stack becomes:<\/p>\n
30\t<-- top of the stack\r\n18<\/b><\/span>\t\r\n-5<\/pre>\n[ad type=”banner”]\n
Next 14 (from stack frame #2) is picked. Since 14 < 30 and 14 < 18, it is inserted below 18. Now stack becomes:<\/p>\n
30\t<-- top of the stack\r\n18\r\n14<\/b><\/span>\t\r\n-5<\/pre>\n
Now -3 (from stack frame #1) is picked, as -3 < 30 and -3 < 18 and -3 < 14, it is inserted below 14. Now stack becomes:<\/p>\n
30\t<-- top of the stack\r\n18\r\n14\r\n-3<\/span><\/b>\t\r\n-5<\/pre>\n

\nImplementation: <\/strong>
\nBelow is C and Java implementation of above algorithm.<\/p>\n[ad type=”banner”]\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ C program to sort a stack using recursion#include <stdio.h>#include <stdlib.h> \/\/ Stack is represented using linked liststruct stack{    int data;    struct stack *next;}; \/\/ Utility function to initialize stackvoid initStack(struct stack **s){    *s = NULL;} \/\/ Utility function to chcek if stack is emptyint isEmpty(struct stack *s){    if (s == NULL)        return 1;    return 0;} \/\/ Utility function to push an item to stackvoid push(struct stack **s, int x){    struct stack *p = (struct stack *)malloc(sizeof(*p));     if (p == NULL)    {        fprintf(stderr, "Memory allocation failed.\\n");        return;    }     p->data = x;    p->next = *s;    *s = p;} \/\/ Utility function to remove an item from stackint pop(struct stack **s){    int x;    struct stack *temp;     x = (*s)->data;    temp = *s;    (*s) = (*s)->next;    free(temp);     return x;} \/\/ Function to find top itemint top(struct stack *s){    return (s->data);} \/\/ Recursive function to insert an item x in sorted wayvoid sortedInsert(struct stack **s, int x){    \/\/ Base case: Either stack is empty or newly inserted    \/\/ item is greater than top (more than all existing)    if (isEmpty(*s) || x > top(*s))    {        push(s, x);        return;    }     \/\/ If top is greater, remove the top item and recur    int temp = pop(s);    sortedInsert(s, x);     \/\/ Put back the top item removed earlier    push(s, temp);} \/\/ Function to sort stackvoid sortStack(struct stack **s){    \/\/ If stack is not empty    if (!isEmpty(*s))    {        \/\/ Remove the top item        int x = pop(s);         \/\/ Sort remaining stack        sortStack(s);         \/\/ Push the top item back in sorted stack        sortedInsert(s, x);    }} \/\/ Utility function to print contents of stackvoid printStack(struct stack *s){    while (s)    {        printf("%d ", s->data);        s = s->next;    }    printf("\\n");} \/\/ Driver Programint main(void){    struct stack *top;     initStack(&top);    push(&top, 30);    push(&top, -5);    push(&top, 18);    push(&top, 14);    push(&top, -3);     printf("Stack elements before sorting:\\n");    printStack(top);     sortStack(&top);    printf("\\n\\n");     printf("Stack elements after sorting:\\n");    printStack(top);     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Stack elements before sorting:\r\n-3 14 18 -5 30 \r\n\r\nStack elements after sorting:\r\n30 18 14 -3 -5<\/pre>\n
Exercise:<\/strong> Modify above code to reverse stack in descending order.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C Algorithm – Sort a stack using recursion- Data Structure – Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,73012,79607],"tags":[80224,80704,80703,80225,80705,80702,80780,80223,80222,80779,80221,80227,80706],"class_list":["post-27076","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-data-structures","category-stack","tag-c-program-to-reverse-a-stack-without-using-recursion","tag-recursion-explanation-using-stack","tag-recursion-using-stack-example","tag-recursion-using-stack-in-c","tag-recursion-using-stack-in-data-structure","tag-reverse-a-stack-using-recursion","tag-reverse-a-stack-using-recursion-in-java","tag-reverse-stack-c","tag-reverse-stack-using-two-stacks","tag-sort-a-stack-in-ascending-order-using-another-stack","tag-sort-a-stack-using-recursion","tag-sort-a-stack-using-recursion-in-c","tag-sort-stack-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27076"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27076\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}