Data Structures and Algorithms (Some Questions for You - Answer to Question 3) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

How can you reverse a string using stack? Give one example and show how you can reverse a given string using stack.

Given a string, reverse it using stack. 

Example:

Input: str = “GeeksQuiz”
Output: ziuQskeeG

Input: str = “abc”
Output: cba

Approach:

The idea is to create an empty stack and push all the characters from the string into it. Then pop each character one by one from the stack and put them back into the input string starting from the 0’th index. As we all know, stacks work on the principle of first in, last out. After popping all the elements and placing them back to string, the formed string would be reversed.

Follow the steps given below to reverse a string using stack. 

• Create an empty stack.
• One by one push all characters of string to stack.
• One by one pop all characters from stack and put them back to string.

Below is the implementation of the above approach:

• C++
• C
• Java
• Python3
• C#
• Javascript

// C program to reverse a string using stack #include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h>   // A structure to represent a stack struct Stack {     int top;     unsigned capacity;     char* array; };   // function to create a stack of given // capacity. It initializes size of stack as 0 struct Stack* createStack(unsigned capacity) {     struct Stack* stack         = (struct Stack*)malloc(sizeof(struct Stack));     stack->capacity = capacity;     stack->top = -1;     stack->array         = (char*)malloc(stack->capacity * sizeof(char));     return stack; }   // Stack is full when top is equal to the last index int isFull(struct Stack* stack) {     return stack->top == stack->capacity - 1; }   // Stack is empty when top is equal to -1 int isEmpty(struct Stack* stack) {     return stack->top == -1; }   // Function to add an item to stack. // It increases top by 1 void push(struct Stack* stack, char item) {     if (isFull(stack))         return;     stack->array[++stack->top] = item; }   // Function to remove an item from stack. // It decreases top by 1 char pop(struct Stack* stack) {     if (isEmpty(stack))         return INT_MIN;     return stack->array[stack->top--]; }   // A stack based function to reverse a string void reverse(char str[]) {     // Create a stack of capacity     // equal to length of string     int n = strlen(str);     struct Stack* stack = createStack(n);       // Push all characters of string to stack     int i;     for (i = 0; i < n; i++)         push(stack, str[i]);       // Pop all characters of string and     // put them back to str     for (i = 0; i < n; i++)         str[i] = pop(stack); }   // Driver program to test above functions int main() {     char str[] = "GeeksQuiz";       reverse(str);     printf("Reversed string is %s", str);       return 0; }

Output

Reversed string is ziuQskeeG

Time Complexity: O(N)  

Auxiliary Space: O(N) for Stack.

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds