{"id":26861,"date":"2017-12-26T20:33:45","date_gmt":"2017-12-26T15:03:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26861"},"modified":"2017-12-26T20:33:45","modified_gmt":"2017-12-26T15:03:45","slug":"c-algorithm-reverse-string-using-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-reverse-string-using-stack\/","title":{"rendered":"C Algorithm – Reverse a String using Stack"},"content":{"rendered":"

Given a string, reverse it using stack. For example \u201cGeeksQuiz\u201d should be converted to \u201cziuQskeeG\u201d.<\/p>\n

Following is simple algorithm to reverse a string using stack.<\/p>\n

1) Create an empty stack.\r\n2) One by one push all characters of string to stack.\r\n3) One by one pop all characters from stack and put \r\n   them back to string.<\/pre>\n
Following are C and Python programs that implements above algorithm.<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ C program to reverse a string using stack#include <stdio.h>#include <string.h>#include <stdlib.h>#include <limits.h> \/\/ A structure to represent a stackstruct Stack{    int top;    unsigned capacity;    char* array;}; \/\/ function to create a stack of given capacity. It initializes size of\/\/ stack as 0struct Stack* createStack(unsigned capacity){    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));    stack->capacity = capacity;    stack->top = -1;    stack->array = (char*) malloc(stack->capacity * sizeof(char));    return stack;} \/\/ Stack is full when top is equal to the last indexint isFull(struct Stack* stack){   return stack->top == stack->capacity - 1; } \/\/ Stack is empty when top is equal to -1int isEmpty(struct Stack* stack){   return stack->top == -1;  } \/\/ Function to add an item to stack.  It increases top by 1void push(struct Stack* stack, char item){    if (isFull(stack))        return;    stack->array[++stack->top] = item;} \/\/ Function to remove an item from stack.  It decreases top by 1char pop(struct Stack* stack){    if (isEmpty(stack))        return INT_MIN;    return stack->array[stack->top--];} \/\/ A stack based function to reverese a stringvoid reverse(char str[]){    \/\/ Create a stack of capacity equal to length of string    int n = strlen(str);    struct Stack* stack = createStack(n);     \/\/ Push all characters of string to stack    int i;    for (i = 0; i < n; i++)        push(stack, str[i]);     \/\/ Pop all characters of string and put them back to str    for (i = 0; i < n; i++)        str[i] = pop(stack);} \/\/ Driver program to test above functionsint main(){    char str[] = "GeeksQuiz";     reverse(str);    printf("Reversed string is %s", str);     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Reversed string is ziuQskeeG<\/pre>\n

\nTime Complexity: <\/strong>O(n) where n is number of characters in stack.
\nAuxiliary Space: <\/strong>O(n) for stack.<\/p>\n[ad type=”banner”]\n
A string can also be reversed without using any auxiliary space. Following C and Python programs to implement reverse without using stack.<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ C program to reverse a string without using stack#include <stdio.h>#include <string.h> \/\/ A utility function to swap two charactersvoid swap(char *a, char *b){    char temp = *a;    *a = *b;    *b = temp;} \/\/ A stack based function to reverese a stringvoid reverse(char str[]){    \/\/ get size of string    int n = strlen(str), i;     for (i = 0; i < n\/2; i++)        swap(&str[i], &str[n-i-1]);} \/\/ Driver program to test above functionsint main(){    char str[] = "abc";     reverse(str);    printf("Reversed string is %s", str);     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Reversed string is cba<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
 C Algorithm – Evaluation of Postfix Expression – Data Structure -Given a string, reverse it using stack. For example \u201cGeeksQuiz\u201d should be converted <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,82927,1],"tags":[80224,80219,80226,80225,80134,80135,80216,80133,80228,80223,80222,80220,80218,80221,80227,80217],"class_list":["post-26861","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-2","category-coding","tag-c-program-to-reverse-a-stack-without-using-recursion","tag-c-program-using-stack-to-display-reverse-of-the-string","tag-java-program-to-reverse-a-stack-using-recursion","tag-recursion-using-stack-in-c","tag-reverse-a-number-using-stack-in-c","tag-reverse-a-stack-using-recursion-in-c","tag-reverse-a-string-using-stack-in-java","tag-reverse-a-string-using-stack-in-python","tag-reverse-an-array-using-stack-in-c","tag-reverse-stack-c","tag-reverse-stack-using-two-stacks","tag-reverse-words-in-a-string-using-stack","tag-reversing-a-string-using-stack-in-cpp","tag-sort-a-stack-using-recursion","tag-sort-a-stack-using-recursion-in-c","tag-write-an-algorithm-to-reverse-an-input-string-of-characters-using-a-stack"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26861","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=26861"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26861\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}