Reversing a String Using
Stack in C
Instructor: Maliha Bushra Hoque — Lecturer, Software Engineering, Daffodil International
UniversityStudent: Mohammad Ali Nayeem — ID: 232-35-022
Date: Aug 2025 · Course: Data Structures & Algorithms · Theme accent: #f20374
Why Reverse Strings? — Motivation & Use Cases
Reversing a string is a common exercise that illustrates memory, indexing, and algorithmic thinking. Use cases include:
preparing palindromic checks, parsing text formats, simple encryption transformations, and building utilities in text-processing
pipelines.
Data Structure Algorithm Programming
Understand how stack memory and See how a linear-time approach (O(n)) Hands-on C implementation enforces
element order relate to string uses LIFO to reverse efficiently. pointers, arrays, and function design.
manipulation.
Stacks: Definition &
Behavior (LIFO)
A stack is an abstract data type that stores elements with two principal
operations: push (insert) and pop (remove). It follows Last-In, First-Out
(LIFO) order — the last item pushed is the first popped. This natural reversal
property makes stacks ideal for reversing sequences.
Push
Place a character on top of the stack. In C: increment top, assign value.
Pop
Remove and return top character. In C: read value, decrement top.
Algorithm & Pseudocode
Idea: push every character from the input string onto the stack, then pop all characters back into the string (or a new buffer).
Complexity: O(n) time, O(n) extra space for the stack. Safe handling: check stack overflow, preserve null terminator.
// Pseudocode function reverseString(s): create stack of size length(s) for each char c
in s until '\0': push(stack, c) i = 0 while stack not empty: s[i] =
pop(stack) i = i + 1 s[i] = '\0'
Tip: For in-place reversal without extra stack, swap symmetric characters — but the stack approach maps directly to LIFO
reasoning and is simpler to teach.
C Implementation — Reverse Using Stack
The example below uses an explicit char stack. Highlighted keywords: #include, malloc, free, for, while.
#include <stdio.h> #include <stdlib.h> #include <string.h> void reverse(char
*s) { int n = strlen(s); char *stack = malloc(n); int top = -1;
for (int i=0; i<n; ++i) stack[++top] = s[i]; // push int i = 0; while
(top >= 0) s[i++] = stack[top--]; // pop s[i] = '\0';
free(stack); } int main() { char str[100] = "Daffodil"; reverse(str);
printf("Reversed: %s\n", str); return 0; }
Notes: allocate exactly n bytes for the stack (no +1 since we store characters only). For larger inputs
use dynamic resizing or check buffer limits to avoid overflow.
Diagram: Push/Pop
Sequence (Example:
"DAFF")
Walkthrough: input "DAFF". Push D→A→F→F. Stack top holds last 'F'. Pop
sequence returns F→F→A→D, producing "FFAD" (i.e., reversed).
Visualizing this step-by-step clarifies why LIFO equals reversal.
Step 1
Traverse input left to right, push each char.
Step 2
Pop until empty, appending to output — that yields reversed string.
Conclusion, Extensions &
Next Steps
Key takeaways: stacks implement LIFO, making them an intuitive tool to
reverse strings with O(n) time and O(n) extra space. Advantages: conceptual
clarity, easy mapping to push/pop primitives, and safe for teaching
recursion/iterative thinking.
• Extensions: implement with linked-list stack, use in-place two-pointer swap
to avoid extra memory.
• Applications: palindrome detection, HTML/XML tag matching, undo/redo features.
• Next steps: write test cases (empty string, Unicode/UTF-8 bytes, max-
length input), then measure memory/time.
For instructor review: include error handling (NULL checks, malloc
failure) and discuss character encoding (C strings are byte sequences;
reversing UTF-8 safely requires rune-aware logic).
Contact: [email protected]
