Stacks & QueuesProblem 7 of 38
Reverse a String using Stack
Problem Statement
Reverse a string using a stack data structure. The idea is to leverage the LIFO (Last In First Out) property of stacks to reverse the order of characters.
Example:
Input: "hello"
Output: "olleh"
Input: "GeeksforGeeks"
Output: "skeeGrofskeeG"
Input: "Stack"
Output: "kcatS"
Approach 1: Using Stack (Standard)
Intuition
Push all characters of the string onto a stack, then pop them one by one. Due to LIFO property, characters come out in reverse order, giving us the reversed string.
Algorithm
- Create an empty stack
- Push each character of the string onto the stack
- Pop all characters from the stack and append them to form the reversed string
java
import java.util.*;
public class ReverseString {
public static String reverseString(String s) {
Stack<Character> stack = new Stack<>();
// Push all characters onto stack
for (char c : s.toCharArray()) {
stack.push(c);
}
// Pop all characters to form reversed string
StringBuilder reversed = new StringBuilder();
while (!stack.isEmpty()) {
reversed.append(stack.pop());
}
return reversed.toString();
}
// Using char array for in-place modification
public static char[] reverseInPlace(char[] s) {
Stack<Character> stack = new Stack<>();
// Push all characters
for (char c : s) {
stack.push(c);
}
// Pop and overwrite
for (int i = 0; i < s.length; i++) {
s[i] = stack.pop();
}
return s;
}
public static void main(String[] args) {
String s1 = "hello";
System.out.println("Original: " + s1);
System.out.println("Reversed: " + reverseString(s1));
char[] s2 = "GeeksforGeeks".toCharArray();
System.out.println("\nOriginal: GeeksforGeeks");
System.out.println("In-place: " + new String(reverseInPlace(s2)));
}
}Complexity Analysis
- Time Complexity: O(n) - push n characters, pop n characters
- Space Complexity: O(n) - stack stores all n characters
Approach 2: Reverse Words in a String
Intuition
A common variation is to reverse the order of words while keeping each word's characters in order. Use a stack to store words, then pop them to get reversed order.
Algorithm
- Split the string into words
- Push each word onto the stack
- Pop words to form the reversed sentence
java
import java.util.*;
public class ReverseWords {
public static String reverseWords(String s) {
Stack<String> stack = new Stack<>();
// Push each word onto stack
String[] words = s.split(" ");
for (String word : words) {
if (!word.isEmpty()) {
stack.push(word);
}
}
// Pop words to form reversed sentence
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pop());
if (!stack.isEmpty()) {
result.append(" ");
}
}
return result.toString();
}
public static String reverseEachWord(String s) {
Stack<Character> stack = new Stack<>();
StringBuilder result = new StringBuilder();
for (int i = 0; i <= s.length(); i++) {
if (i == s.length() || s.charAt(i) == ' ') {
// Pop all characters of current word
while (!stack.isEmpty()) {
result.append(stack.pop());
}
if (i < s.length()) {
result.append(' ');
}
} else {
stack.push(s.charAt(i));
}
}
return result.toString();
}
public static void main(String[] args) {
String s1 = "Hello World";
System.out.println("Original: " + s1);
System.out.println("Words reversed: " + reverseWords(s1));
String s2 = "The quick brown fox";
System.out.println("\nOriginal: " + s2);
System.out.println("Each word reversed: " + reverseEachWord(s2));
}
}Complexity Analysis
- Time Complexity: O(n) - process each character once
- Space Complexity: O(n) - stack stores characters/words
Key Takeaways
- Stack's LIFO property naturally reverses the order of elements
- Push elements in order, pop them to get reverse order
- This technique works for characters, words, or any sequence
- Common variations:
- Reverse entire string character by character
- Reverse order of words in a sentence
- Reverse each word individually
- While simpler methods exist (two pointers, slicing), stack demonstrates the concept clearly
- Time complexity is always O(n) for any reversal approach