Open In App

How to Reverse a String using Stack

Last Updated : 23 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a string, reverse it using stack. 

Example:

Input: str = “GeeksQuiz”
Output: ziuQskeeG

Input: str = “abc”
Output: cba

Recommended Practice

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 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 reverse 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 <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;
}


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);
    }
}


Python3




# 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


C#




/* C# program to reverse
String using Stack */
using System;
using System.Text;
// stack
class 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
 
// stack
class 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 string
function 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 Code
let s = "GeeksQuiz".split("");
 
// Call reverse method
reverse(s);
 
// Print the reversed string
document.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 module
import string
 
# define a function to reverse a string
def 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 function
if __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 string
console.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 string
System.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.



Previous Article
Next Article

Similar Reads

Reverse the Words of a String using Stack
Given string str consisting of multiple words, the task is to reverse the entire string word by word.Examples: Input: str = "I Love To Code" Output: Code To Love IInput: str = "data structures and algorithms" Output: algorithms and structures data Approach: This problem can be solved not only with the help of the strtok() but also it can be solved
8 min read
Java Program to Reverse a String using Stack
The Stack is a linear data structure that follows the LIFO(Last In First Out) principle, i.e, the element inserted at the last is the element to come out first. Approach: Push the character one by one into the Stack of datatype character.Pop the character one by one from the Stack until the stack becomes empty.Add a popped element to the character
2 min read
C++ Program to Reverse a String Using Stack
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.Recommended PracticeReverse a string
4 min read
Print Reverse a linked list using Stack
Given a linked list, print the reverse of it without modifying the list. Examples: Input : 1 2 3 4 5 6 Output : 6 5 4 3 2 1 Input : 12 23 34 45 56 67 78 Output : 78 67 56 45 34 23 12 Below are different solutions that are now allowed here as we cannot use extra space and modify the list. Recursive solution to print reverse a linked list. Requires e
9 min read
Program to reverse a linked list using Stack
Given a linked list. The task is to reverse the order of the elements of the Linked List using an auxiliary Stack. Examples: Input : List = 3 -&gt; 2 -&gt; 1 Output : 1 -&gt; 2 -&gt; 3 Input : 9 -&gt; 7 -&gt; 4 -&gt; 2 Output : 2 -&gt; 4 -&gt; 7 -&gt; 9 Algorithm: Traverse the list and push all of its nodes onto a stack.Traverse the list from the h
7 min read
Reverse alternate levels of a perfect binary tree using Stack
Given a Perfect Binary Tree, the task is to reverse the alternate level nodes of the binary tree.Examples: Input: a / \ b c / \ / \ d e f g / \ / \ / \ / \ h i j k l m n o Output: Inorder Traversal of given tree h d i b j e k a l f m c n g o Inorder Traversal of modified tree o d n c m e l a k f j b i g h Input: a / \ b c Output: Inorder Traversal
10 min read
Reverse an array using Stack
Given an array arr[] of size N, the task to reverse the array using Stack. Examples: Input: arr[] = { 10, 20, 30, 40, 50 } Output: 50 40 30 20 10 Explanation: Reversing the array modifies arr[] to { 50, 40, 30, 20, 10 } Therefore, the required output is 50 40 30 20 10. Input: arr[] = { 1 } Output: 1 Iterative and Recursive Approach: Refer the artic
12 min read
Reverse a Stack using Queue
Given a stack, the task is to reverse the stack using the queue data structure. Examples: Input: Stack: (Top to Bottom) [10 -&gt; 20 -&gt; 30 -&gt; 40]Output: Stack: (Top to Bottom) [40 -&gt; 30 -&gt; 20 -&gt; 10] Input: Stack: [6 -&gt; 5 -&gt; 4]Output: Stack: [4 -&gt; 5 -&gt; 6] Approach: The problem can be solved based on the following idea: The
5 min read
C Program to Reverse a Stack using Recursion
Write a program to reverse a stack using recursion, without using any loop. Example:  Input: elements present in stack from top to bottom 1 2 3 4 Output: 4 3 2 1  Input: elements present in stack from top to bottom 1 2 3Output: 3 2 1 Recommended PracticeReverse a StackTry It!Reverse a stack using Recursion The idea of the solution is to hold all va
5 min read
How to Reverse a Stack using Recursion
Write a program to reverse a stack using recursion, without using any loop. Example: Input: elements present in stack from top to bottom 1 2 3 4 Output: 4 3 2 1 Input: elements present in stack from top to bottom 1 2 3Output: 3 2 1 Recommended PracticeReverse a StackTry It!Reverse a stack using RecursionThe idea of the solution is to hold all value
11 min read
Article Tags :
Practice Tags :