Given a string, reverse it using stack. For example “GeeksQuiz” should be converted to “ziuQskeeG”.
Following is simple algorithm to reverse a string using stack.
1) Create an empty stack. 2) One by one push all characters of string to stack. 3) One by one pop all characters from stack and put them back to string.
Following programs implements above algorithm.
C++
// CPP program to reverse a string using stack #include <bits/stdc++.h> using namespace std; // A structure to represent a stack class Stack { public: int top; unsigned capacity; char* array; }; // function to create a stack of given // capacity. It initializes size of stack as 0 Stack* createStack(unsigned capacity) { Stack* stack = new Stack(); stack->capacity = capacity; stack->top = -1; stack->array = new char[(stack->capacity * sizeof(char))]; return stack; } // Stack is full when top is equal to the last index int isFull(Stack* stack) { return stack->top == stack->capacity - 1; } // Stack is empty when top is equal to -1 int isEmpty(Stack* stack) { return stack->top == -1; } // Function to add an item to stack. // It increases top by 1 void push(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(Stack* stack) { if (isEmpty(stack)) return -1; return stack->array[stack->top--]; } // A stack based function to reverese a string void reverse(char str[]) { // Create a stack of capacity //equal to length of string int n = strlen(str); 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 code int main() { char str[] = "GeeksQuiz"; reverse(str); cout << "Reversed string is " << str; return 0; } // This code is contributed by rathbhupendra |
C
// C program to reverse a string using stack #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.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 reverese 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; } |
Java
/* Java program to reverse String using Stack */ import java.util.*; //stack class Stack { int size; int top; char[] a; //function to check if stack is empty boolean isEmpty() { return (top < 0); } Stack(int n) { top = -1; size = n; a = new char[size]; } //function to push element in Stack boolean push(char x) { if (top >= size) { System.out.println("Stack Overflow"); return false; } else { a[++top] = x; return true; } } //function to pop element from stack char pop() { if (top < 0) { System.out.println("Stack Underflow"); return 0; } else { char x = a[top--]; return x; } } } // Driver code class Main { //function to reverse the string public static void reverse(StringBuffer str) { // Create a stack of capacity // equal to length of string int n = str.length(); Stack obj = new Stack(n); // Push all characters of string // to stack int i; for (i = 0; i < n; i++) obj.push(str.charAt(i)); // Pop all characters of string // and put them back to str for (i = 0; i < n; i++) { char ch = obj.pop(); str.setCharAt(i,ch); } } //driver function public static void main(String args[]) { //create a new string StringBuffer s= new StringBuffer("GeeksQuiz"); //call reverse method reverse(s); //print the reversed string System.out.println("Reversed string is " + s); } } |
Python
# Python program to reverse a string using stack # Function to create an empty stack. # It initializes size of stack as 0 def createStack(): stack=[] return stack # Function to determine the size of the stack def size(stack): return len(stack) # Stack is empty if the size is 0 def isEmpty(stack): if size(stack) == 0: return true # Function to add an item to stack . # It increases size by 1 def push(stack,item): stack.append(item) #Function to remove an item from stack. # It decreases size by 1 def pop(stack): if isEmpty(stack): return return stack.pop() # A stack based function to reverse a string def reverse(string): n = len(string) # Create a empty stack stack = createStack() # Push all characters of string to stack for i in range(0,n,1): push(stack,string[i]) # Making the string empty since all #characters are saved in stack string="" # Pop all characters of string and # put them back to string for i in range(0,n,1): string+=pop(stack) return string # Driver program to test above functions string="GeeksQuiz"string = reverse(string) print("Reversed string is " + string) # This code is contributed by Sunny Karira |
Output:
Reversed string is ziuQskeeG
Time Complexity: O(n) where n is number of characters in stack.
Auxiliary Space: O(n) for stack.
A string can also be reversed without using any auxiliary space. Following C, Java, C# and Python programs to implement reverse without using stack.
C++
// C++ program to reverse a string without using stack #include <bits/stdc++.h> using namespace std; // A utility function to swap two characters void swap(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } // A stack based function to reverese a string void reverse(char str[]) { // get size of string int n = strlen(str), i; for (i = 0; i < n/2; i++) swap(&str[i], &str[n-i-1]); } // Driver program to test above functions int main() { char str[] = "abc"; reverse(str); cout<<"Reversed string is "<< str; return 0; } //This is code is contributed by rathbhupendra |
C
// C program to reverse a string without using stack #include <stdio.h> #include <string.h> // A utility function to swap two characters void swap(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } // A stack based function to reverese a string void reverse(char str[]) { // get size of string int n = strlen(str), i; for (i = 0; i < n/2; i++) swap(&str[i], &str[n-i-1]); } // Driver program to test above functions int main() { char str[] = "abc"; reverse(str); printf("Reversed string is %s", str); return 0; } |
Java
// Java program to reverse a string without using stack public class GFG { // A utility function to swap two characters static void swap(char a[], int index1, int index2) { char temp = a[index1]; a[index1] = a[index2]; a[index2] = temp; } // A stack based function to reverese a string static void reverse(char str[]) { // get size of string int n = str.length, i; for (i = 0; i < n / 2; i++) { swap(str, i, n - i - 1); } } // Driver program to test above functions public static void main(String[] args) { char str[] = "abc".toCharArray(); reverse(str); System.out.printf("Reversed string is " + String.valueOf(str)); } } // This code is contributed by 29AjayKumar |
Python
# Python program to reverse a string without stack # Function to reverse a string def reverse(string): string = string[::-1] return string # Driver program to test above functions string = "abc"string = reverse(string) print("Reversed string is " + string) # This code is contributed by Sunny Karira |
C#
// C# program to reverse a string without using stack using System; public class GFG { // A utility function to swap two characters static void swap(char []a, int index1, int index2) { char temp = a[index1]; a[index1] = a[index2]; a[index2] = temp; } // A stack based function to reverese a string static void reverse(char []str) { // get size of string int n = str.Length, i; for (i = 0; i < n / 2; i++) { swap(str, i, n - i - 1); } } // Driver program to test above functions public static void Main() { char []str = "abc".ToCharArray(); reverse(str); Console.WriteLine("Reversed string is " + String.Join("",str)); } } // This code is contributed by PrinciRaj1992 |
Output:
Reversed string is cba
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments