{"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[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20to%20reverse%20a%20string%20using%20stack%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20stack%0Astruct%20Stack%0A%7B%0A%20%20%20%20int%20top%3B%0A%20%20%20%20unsigned%20capacity%3B%0A%20%20%20%20char*%20array%3B%0A%7D%3B%0A%20%0A%2F%2F%20function%20to%20create%20a%20stack%20of%20given%20capacity.%20It%20initializes%20size%20of%0A%2F%2F%20stack%20as%200%0Astruct%20Stack*%20createStack(unsigned%20capacity)%0A%7B%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20(struct%20Stack*)%20malloc(sizeof(struct%20Stack))%3B%0A%20%20%20%20stack-%3Ecapacity%20%3D%20capacity%3B%0A%20%20%20%20stack-%3Etop%20%3D%20-1%3B%0A%20%20%20%20stack-%3Earray%20%3D%20(char*)%20malloc(stack-%3Ecapacity%20*%20sizeof(char))%3B%0A%20%20%20%20return%20stack%3B%0A%7D%0A%20%0A%2F%2F%20Stack%20is%20full%20when%20top%20is%20equal%20to%20the%20last%20index%0Aint%20isFull(struct%20Stack*%20stack)%0A%7B%20%20%20return%20stack-%3Etop%20%3D%3D%20stack-%3Ecapacity%20-%201%3B%20%7D%0A%20%0A%2F%2F%20Stack%20is%20empty%20when%20top%20is%20equal%20to%20-1%0Aint%20isEmpty(struct%20Stack*%20stack)%0A%7B%20%20%20return%20stack-%3Etop%20%3D%3D%20-1%3B%20%20%7D%0A%20%0A%2F%2F%20Function%20to%20add%20an%20item%20to%20stack.%20%20It%20increases%20top%20by%201%0Avoid%20push(struct%20Stack*%20stack%2C%20char%20item)%0A%7B%0A%20%20%20%20if%20(isFull(stack))%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20stack-%3Earray%5B%2B%2Bstack-%3Etop%5D%20%3D%20item%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20remove%20an%20item%20from%20stack.%20%20It%20decreases%20top%20by%201%0Achar%20pop(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20if%20(isEmpty(stack))%0A%20%20%20%20%20%20%20%20return%20INT_MIN%3B%0A%20%20%20%20return%20stack-%3Earray%5Bstack-%3Etop\u2013%5D%3B%0A%7D%0A%20%0A%2F%2F%20A%20stack%20based%20function%20to%20reverese%20a%20string%0Avoid%20reverse(char%20str%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20stack%20of%20capacity%20equal%20to%20length%20of%20string%0A%20%20%20%20int%20n%20%3D%20strlen(str)%3B%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20createStack(n)%3B%0A%20%0A%20%20%20%20%2F%2F%20Push%20all%20characters%20of%20string%20to%20stack%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20push(stack%2C%20str%5Bi%5D)%3B%0A%20%0A%20%20%20%20%2F%2F%20Pop%20all%20characters%20of%20string%20and%20put%20them%20back%20to%20str%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20str%5Bi%5D%20%3D%20pop(stack)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20char%20str%5B%5D%20%3D%20%22GeeksQuiz%22%3B%0A%20%0A%20%20%20%20reverse(str)%3B%0A%20%20%20%20printf(%22Reversed%20string%20is%20%25s%22%2C%20str)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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=\u201dbanner\u201d]\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[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20to%20reverse%20a%20string%20without%20using%20stack%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20swap%20two%20characters%0Avoid%20swap(char%20*a%2C%20char%20*b)%0A%7B%0A%20%20%20%20char%20temp%20%3D%20*a%3B%0A%20%20%20%20*a%20%3D%20*b%3B%0A%20%20%20%20*b%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20stack%20based%20function%20to%20reverese%20a%20string%0Avoid%20reverse(char%20str%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20get%20size%20of%20string%0A%20%20%20%20int%20n%20%3D%20strlen(str)%2C%20i%3B%0A%20%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%2F2%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20swap(%26str%5Bi%5D%2C%20%26str%5Bn-i-1%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20char%20str%5B%5D%20%3D%20%22abc%22%3B%0A%20%0A%20%20%20%20reverse(str)%3B%0A%20%20%20%20printf(%22Reversed%20string%20is%20%25s%22%2C%20str)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
Reversed string is cba<\/pre>\n[ad type=\u201dbanner\u201d]\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}]}}