Given a string, reverse it using stack.
Example:
Input: str = “GeeksQuiz”
Output: ziuQskeeGInput: 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++ program to reverse a string using stack#include <bits/stdc++.h>using namespace std;// A structure to represent a stackclass Stack {public: int top; unsigned capacity; char* array;};// function to create a stack of given// capacity. It initializes size of stack as 0Stack* 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 indexint isFull(Stack* stack){ return stack->top == stack->capacity - 1;}// Stack is empty when top is equal to -1int isEmpty(Stack* stack) { return stack->top == -1; }// Function to add an item to stack.// It increases top by 1void 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 1char pop(Stack* stack){ if (isEmpty(stack)) return -1; return stack->array[stack->top--];}// A stack based function to reverse a stringvoid 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 codeint 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 <limits.h>#include <stdio.h>#include <stdlib.h>#include <string.h>// A structure to represent a stackstruct Stack { int top; unsigned capacity; char* array;};// function to create a stack of given// capacity. It initializes size of stack as 0struct 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 indexint isFull(struct Stack* stack){ return stack->top == stack->capacity - 1;}// Stack is empty when top is equal to -1int isEmpty(struct Stack* stack){ return stack->top == -1;}// Function to add an item to stack.// It increases top by 1void 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 1char pop(struct Stack* stack){ if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top--];}// A stack based function to reverse a stringvoid 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 functionsint main(){ char str[] = "GeeksQuiz"; reverse(str); printf("Reversed string is %s", str); return 0;} |
Java
/* Java program to reverseString using Stack */import java.util.*;// stackclass 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 codeclass 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); }} |
Python3
# Python program to reverse a string using stack# Function to create an empty stack.# It initializes size of stack as 0def createStack(): stack = [] return stack# Function to determine the size of the stackdef size(stack): return len(stack)# Stack is empty if the size is 0def isEmpty(stack): if size(stack) == 0: return true# Function to add an item to stack .# It increases size by 1def push(stack, item): stack.append(item)# Function to remove an item from stack.# It decreases size by 1def pop(stack): if isEmpty(stack): return return stack.pop()# A stack based function to reverse a stringdef 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 functionsstring = "GeeksQuiz"string = reverse(string)print("Reversed string is " + string)# This code is contributed by Sunny Karira |
C#
/* C# program to reverseString using Stack */using System;using System.Text;// stackclass Stack { public int size; public int top; public char[] a; // function to check if stack is empty public Boolean isEmpty() { return (top < 0); } public Stack(int n) { top = -1; size = n; a = new char[size]; } // function to push element in Stack public Boolean push(char x) { if (top >= size) { Console.WriteLine("Stack Overflow"); return false; } else { a[++top] = x; return true; } } // function to pop element from stack public char pop() { if (top < 0) { Console.WriteLine("Stack Underflow"); return ' '; } else { char x = a[top--]; return x; } }}class GFG { // function to reverse the string public static void reverse(StringBuilder 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[i]); // Pop all characters of string // and put them back to str for (i = 0; i < n; i++) { char ch = obj.pop(); str[i] = ch; } } // Driver code public static void Main(String[] args) { // create a new string StringBuilder s = new StringBuilder("GeeksQuiz"); // call reverse method reverse(s); // print the reversed string Console.WriteLine("Reversed string is " + s); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to reverse// String using Stack // stackclass Stack{ size; top; a = []; // Function to check if stack is empty isEmpty() { return(this.top < 0); } constructor(n) { this.top = -1; this.size = n; this.a = new Array(this.size); } // Function to push element in Stack push(x) { if (this.top >= this.size) { document.write("Stack Overflow<br>"); return false; } else { this.a[++this.top] = x; return true; } } // Function to pop element from stack pop() { if (this.top < 0) { document.write("Stack Underflow<br>"); return 0; } else { let x = this.a[this.top--]; return x; } }}// Function to reverse the stringfunction reverse(str){ // Create a stack of capacity // equal to length of string let n = str.length; let obj = new Stack(n); // Push all characters of string // to stack let i; for(i = 0; i < n; i++) obj.push(str[i]); // Pop all characters of string // and put them back to str for(i = 0; i < n; i++) { let ch = obj.pop(); str[i] = ch; }}// Driver Codelet s = "GeeksQuiz".split("");// Call reverse methodreverse(s);// Print the reversed stringdocument.write("Reversed string is " + s.join(""));// This code is contributed by rag2127</script> |
Output
Reversed string is ziuQskeeG
Time Complexity: O(N)
Auxiliary Space: O(N) for Stack.
Reversing The String become Easy If You Use Stack InBulid liberay (STL).
Here in this approach we have use stack(stl) Which is LIFO type DataStructure.
C++
#include <bits/stdc++.h>#include<iostream>#include<string>#include<stack>using namespace std;//passing str by reference because be need to do changes in str //only not want to create any copy and when return it.void the_helper(string &str){ //stack which takw char input. stack<char>s; //we push all char in stack. for(auto it:str)s.push(it); //here we clear all char present in str. str.clear(); // as stack is LIFO DS we push_back all char and our string is reverse now. while(!s.empty()){ str.push_back(s.top()); s.pop(); }}int main() { //string we want to reverse. string str = "GeeksQuiz"; //the function that make all necessary changes. the_helper(str); //finally return/output the reverse string cout << "Reversed string is : " << str; return 0;} |
Python3
# import the required moduleimport string# define a function to reverse a stringdef the_helper(s): # create an empty stack stack = [] # push all characters of the string into the stack for i in s: stack.append(i) # empty the string s = "" # pop all characters from the stack and append to the string while stack: s += stack.pop() # return the reversed string return s# main functionif __name__ == "__main__": # define the input string str = "GeeksQuiz" # call the function to reverse the string reversed_str = the_helper(str) # print the reversed string print("Reversed string is: ", reversed_str) |
C#
/// c#using System;using System.Collections.Generic;public class GFG { static void the_helper(ref string str) { //stack which takes char input. Stack<char> s = new Stack<char>(); //we push all char in stack. foreach (char ch in str) { s.Push(ch); } //here we clear all char present in str. str = ""; //as stack is LIFO DS we push_back all char and our string is reverse now. while (s.Count != 0) { str += s.Peek(); s.Pop(); } } static void Main() { //string we want to reverse. string str = "GeeksQuiz"; //the function that makes all necessary changes. the_helper(ref str); //finally return/output the reverse string Console.WriteLine("Reversed string is : " + str); }}// ksam24000 |
Javascript
// passing str by reference because be need to do changes in str // only not want to create any copy and when return it.function the_helper(str) {// stack which takw char input. let s = []; // we push all char in stack. for (let i = 0; i < str.length; i++) { s.push(str.charAt(i)); } // here we clear all char present in str. str = ''; // as stack is LIFO DS we push_back all char and our string is reverse now. while (s.length > 0) { str += s.pop(); } return str;}// string we want to reverse.let str = 'GeeksQuiz';// the function that make all necessary changes.str = the_helper(str); // finally return/output the reverse stringconsole.log('Reversed string is: ' + str); |
Java
import java.util.*;public class Main {//passing str by reference because be need to do changes in str//only not want to create any copy and when return it.static void the_helper(StringBuilder str){//stack which takes char input.Stack<Character> s = new Stack<>();//we push all char in stack.for(int i=0;i<str.length();i++) s.push(str.charAt(i));//here we clear all char present in str.str.delete(0, str.length());// as stack is LIFO DS we append all char and our string is reverse now.while(!s.empty()){str.append(s.peek());s.pop();}}public static void main(String[] args) {//string we want to reverse.StringBuilder str = new StringBuilder("GeeksQuiz");//the function that make all necessary changes.the_helper(str);//finally return/output the reverse stringSystem.out.println("Reversed string is : " + str);}} |
Output
Reversed string is : ziuQskeeG
Time Complexity: O(N) Only one traversal to push and pop so O(n)+O(n)==O(n).
Auxiliary Space: O(N) Extra for Stack.
For other methods, please refer reverse a string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
