Given a string, reverse it using stack. For example “GeeksQuiz” should be converted to “ziuQskeeG”.
Following is simple algorithm to reverse a string using stack.
1) Create an empty stack. 2) One by one push all characters of string to stack. 3) One by one pop all characters from stack and put them back to string.
Following are C and Python programs that implements above algorithm.
C Programming:
[pastacode lang=”c” manual=”%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–%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” message=”” highlight=”” provider=”manual”/]Output:
Reversed string is ziuQskeeG
Time Complexity: O(n) where n is number of characters in stack.
Auxiliary Space: O(n) for stack.
A string can also be reversed without using any auxiliary space. Following C and Python programs to implement reverse without using stack.
C Programming:
[pastacode lang=”c” manual=”%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” message=”” highlight=”” provider=”manual”/]Output:
Reversed string is cba[ad type=”banner”]