String Reversal Using Stack: A Practical Guide with Code
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
The problem is simple: Given a string, return the same string with all characters in reverse order. For example:
- Input: "Hello World"
- Output: "dlroW olleH"
We need to create a function that takes a string as input and returns the reversed version of that string.
Using Stack Data Structure
Explanation
The simplest way to reverse a string is to use a stack data structure. A stack follows the Last-In-First-Out (LIFO) principle, which is perfect for string reversal.
Here's how this approach works:
- Push each character of the input string onto a stack
- Pop each character from the stack and append it to a new string
- Return the new string, which will be the reversed version
Since we need to process each character once during the push operation and once during the pop operation, this approach has a time complexity of O(n), where n is the length of the string. The space complexity is also O(n) because we need to store all characters in the stack.
Lets Say We s = “hello”
Step 1: Initialize an empty stack
stack = []
Step 2: Push each character to the stack
After pushing:
stack = ['h', 'e', 'l', 'l', 'o']
Step 3: Pop characters and build reversed string
- reversed_string = ""
Now pop from the stack:
- Pop 'o' → reversed_string = "o"
- Pop 'l' → reversed_string = "ol"
- Pop 'l' → reversed_string = "oll"
- Pop 'e' → reversed_string = "olle"
- Pop 'h' → reversed_string = "olleh"
String Reversal Using Stack Visualization
<visualization-box>
Code (Python)
def reverse_string_using_stack(s):
# Create an empty stack
stack = []
# Push all characters of string to stack
for char in s:
stack.append(char)
# Create an empty string to store the reversed string
reversed_string = ""
# Pop all characters from stack and add them to the reversed string
while stack:
reversed_string += stack.pop()
return reversed_string
Code (C++)
#include <stack>
#include <string>
std::string reverse_string_using_stack(const std::string& s) {
// Create a stack
std::stack<char> stack;
// Push all characters of string to stack
for (char c : s) {
stack.push(c);
}
// Create an empty string to store the reversed string
std::string reversed_string = "";
// Pop all characters from stack and add them to the reversed string
while (!stack.empty()) {
reversed_string += stack.top();
stack.pop();
}
return reversed_string;
}
Code (Java)
import java.util.Stack;
public class Solution {
public static String reverseStringUsingStack(String s) {
// Create a stack
Stack<Character> stack = new Stack<>();
// Push all characters of string to stack
for (int i = 0; i < s.length(); i++) {
stack.push(s.charAt(i));
}
// Use StringBuilder for efficient string concatenation
StringBuilder reversedString = new StringBuilder();
// Pop all characters from stack and add them to the reversed string
while (!stack.isEmpty()) {
reversedString.append(stack.pop());
}
return reversedString.toString();
}
}
Without Using Stack
Explanation
While the stack-based approach works well, we can optimize it further by eliminating the explicit stack data structure and using the string itself. This reduces the overhead of pushing and popping elements from a stack.
Here's how this optimized approach works:
- Initialize two pointers - one at the beginning and one at the end of the string
- Swap the characters at these pointers
- Move the pointers toward each other
- Continue until the pointers meet or cross each other
This approach has a time complexity of O(n/2) which simplifies to O(n), but it uses less memory and fewer operations than the stack approach. The space complexity is O(n) for languages where strings are immutable (like Python and Java), but can be O(1) for languages that allow in-place modifications (like C++).
Lets consider s =”hello”
Convert to list
chars = ['h', 'e', 'l', 'l', 'o'] , This needs to be done if strings are immutable in the language (like python)
left = 0
right = 4
While Loop Iterations:
- Iteration 1:
- Swap chars[0] and chars[4]: 'h' <-> 'o'
- chars = ['o', 'e', 'l', 'l', 'h']
- left = 1, right = 3
- Iteration 2:
- Swap chars[1] and chars[3]: 'e' <-> 'l'
- chars = ['o', 'l', 'l', 'e', 'h']
- left = 2, right = 2
Code (Python)
def reverse_string_optimized(s):
# Convert string to list of characters (since strings are immutable in Python)
chars = list(s)
left = 0
right = len(chars) - 1
# Swap characters from both ends moving inward
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
# Join the list back into a string
return ''.join(chars)
Code (C++)
#include <string>
std::string reverse_string_optimized(std::string s) {
int left = 0;
int right = s.length() - 1;
// Swap characters from both ends moving inward
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
return s;
}
Code (Java)
public class Solution {
public static String reverseStringOptimized(String s) {
// Convert string to char array (since strings are immutable in Java)
char[] chars = s.toCharArray();
int left = 0;
int right = chars.length - 1;
// Swap characters from both ends moving inward
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}
}
Conclusion
In this article, we explored two methods for reversing a string:
1. The stack-based approach, which uses the LIFO property of stacks to naturally reverse the order of characters
2. The two-pointer approach, which directly swaps characters to achieve the same result with less overhead
Both methods have a time complexity of O(n), but the two-pointer approach generally performs better because it requires fewer operations and memory accesses.
