Reverse a string using a stack data structure
This post will discuss how to reverse a string using the stack data structure in C/C++, Java, and Python.
1. Using explicit stack
The idea is to create an empty stack and push all characters of the string into it. Then pop each character one by one from the stack and put them back to the input string starting from the 0'th index.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <stack> #include <string> using namespace std; // Reverse a string using a stack container in C++. // Note that the string is passed by reference void reverse(string &str) { // create an empty stack stack<int> s; // Push each character in the string to the stack for (char ch: str) { s.push(ch); } // pop all characters from the stack and // put them back to the input string for (int i = 0; i < str.length(); i++) { str[i] = s.top(); s.pop(); } } int main() { string str = "Reverse me"; reverse(str); cout << str; return 0; } |
Output:
em esreveR
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.Stack; class Main { // Reverse a string using a stack container in Java public static String reverse(String str) { // create an empty stack Stack<Character> stack = new Stack<>(); // push each character in the string into the stack char[] chars = str.toCharArray(); for (char c: chars) { stack.push(c); } // pop all characters from the stack and // put them back to the character array for (int i = 0; i < str.length(); i++) { chars[i] = stack.pop(); } // convert the char array to a string and return return new String(chars); } public static void main (String[] args) { String str = "Reverse me"; str = reverse(str); System.out.println(str); } } |
Output:
em esreveR
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
from collections import deque # Reverse a string using a stack def reverse(s): # build a stack from characters in the string stack = deque(s) # pop all characters from the stack and join them back into a string return ''.join(stack.pop() for _ in range(len(s))) if __name__ == '__main__': s = 'Reverse me' s = reverse(s) print(s) |
Output:
em esreveR
The time complexity of the above solution is O(n), where n is the length of the input string. The auxiliary space required by the program is O(n) for the stack data structure.
2. Using implicit stack
We can also use an implicit stack, i.e., call stack., to reverse a string, as demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> // Utility function to swap two characters void swap(char *x, char *y) { char ch = *x; *x = *y; *y = ch; } // Reverse a string using implicit stack (recursion) in C void reverse(char *str, int j) { static int i = 0; // return if we reached the end of the string // `j` now points at the end of the string if (*(str + j) == '\0') { return; } // recur with increasing index `j` by one position reverse(str, j + 1); // swap characters at i'th and j'th index if (i <= j) { swap(&str[i], &str[j]); // advance index `i` by one position, and recursion will take care of index `j` i++; } } // Wrapper function void Reverse(char *str) { reverse(str, 0); } int main(void) { char str[] = "Reverse me"; Reverse(str); printf("%s", str); return 0; } |
Output:
em esreveR
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <algorithm> using namespace std; // Reverse a string using implicit stack (recursion) in C++. // Note that the string is passed by reference void reverse(string &str, int &i, int j) { // base case: `j` reaches string length if (j == str.length()) { return; } reverse(str, i, j + 1); // swap characters at i'th and j'th index if (i <= j) { swap(str[i], str[j]); // advance `i` by one position, and recursion will take care of index `j` i++; } } // Wrapper function void reverse(string &str) { int i = 0; reverse(str, i, 0); } int main() { string str = "Reverse me"; reverse(str); cout << str; return 0; } |
Output:
em esreveR
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Reverse a string using implicit stack (recursion) def swap(s, i, j): temp = s[i] s[i] = s[j] s[j] = temp def reverse(s, i=0, j=0): # base case: `j` reaches string length if j == len(s): return i i = reverse(s, i, j + 1) # swap characters at i'th and j'th index if i <= j: swap(s, i, j) # advance `i` by one position, and recursion will take care of index `j` i += 1 return i if __name__ == '__main__': s = 'Reverse me' chars = [*s] reverse(chars) s = ''.join(chars) print(s) |
Output:
em esreveR
Here’s the alternative, more straightforward approach that takes advantage of the implicit stack to reverse the string.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> #include <string.h> // Utility function to swap two characters void swap(char *x, char *y) { char ch = *x; *x = *y; *y = ch; } // Reverse a string using implicit stack (recursion) in C void reverse(char *str, int i, int j) { if (i < j) { // swap characters at i'th and j'th index swap(&str[i], &str[j]); // recur with increasing i'th index by position and // decreasing j'th index by one position reverse(str, i + 1, j - 1); } } int main(void) { char str[] = "Reverse me"; reverse(str, 0, strlen(str) - 1); printf("%s", str); return 0; } |
Output:
em esreveR
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> using namespace std; // Reverse a string using implicit stack (recursion) in C++. // Note that the string is passed by reference void reverse(string &str, int i, int j) { if (i < j) { // swap characters at i'th and j'th index swap(str[i], str[j]); // recur with increasing i'th index by position and // decreasing j'th index by one position reverse(str, i + 1, j - 1); } } // Wrapper function void reverse(string &str) { reverse(str, 0, str.length() - 1); } int main() { string str = "Reverse me"; reverse(str); cout << str; return 0; } |
Output:
em esreveR
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Main { // Utility function to swap elements at indices `i` and `j` in the array `chars` private static void swap(char[] chars, int i, int j) { char ch = chars[i]; chars[i] = chars[j]; chars[j] = ch; } // Reverse a string using implicit stack (recursion) in Java public static void reverse(char[] chars, int i, int j) { if (i < j) { // swap characters at i'th and j'th index swap(chars, i, j); // recur with increasing i'th index by position and // decreasing j'th index by one position reverse(chars, i + 1, j - 1); } } // Wrapper function public static String reverse(String str) { char[] chars = str.toCharArray(); reverse(chars, 0, str.length() - 1); return new String(chars); } public static void main (String[] args) { String str = "Reverse me"; str = reverse(str); System.out.println(str); } } |
Output:
em esreveR
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Utility function to swap elements at indices `i` and `j` in the array `chars` def swap(chars, i, j): c = chars[i] chars[i] = chars[j] chars[j] = c # Reverse a string using implicit stack (recursion) def reverse(chars, i, j): if i < j: # swap characters at i'th and j'th index swap(chars, i, j) # recur with increasing i'th index by position and # decreasing j'th index by one position reverse(chars, i + 1, j - 1) if __name__ == '__main__': s = 'Reverse me' chars = [*s] reverse(chars, 0, len(s) - 1) rev = ''.join(chars) print(rev) |
Output:
em esreveR
The time complexity of the above solution is O(n), where n is the length of the input string. The auxiliary space required by the program is O(n) for recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)