'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Sep 23, 2023
Easy

Reverse a String using Stack

Author Vaibhav Agarwal
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Reverse a String using stack

Introduction

Reversing a string using a stack and Reserve a string in C++ and C is a common question in all interviews. Most of the technical interviews focus on the string as a major Data Structure.

How can somebody solve a string data structure?

It would be very easy to solve a string data structure if you know the arrays because Strings are nothing but character arrays. One who has good command over array data structure can solve the string problems easily. Another data structure to be used to reverse the string is stack. A most common example to understand the stack data structure is the bunch of the plates we normally see.

Reversing a string can be done in different ways. One of the ways to do the same is using build-in methods like reverse(); We can consider some of the examples like “Coding”, the return after the reverse of coding would be “gnidoC”, in a similar fashion we can consider “stack”, the return type of this after the reverse is “kcats”. 

Below are the following steps to reversing a String using Stack.

  • String to Char[].
  • Create a Stack.
  • Push all characters, one by one.
  • Then Pop all characters, one by one and put into the char[].
  • Finally, convert to the String.

Also read about  Starcat () in C

Stack Data Structure and its Operations

A stack is a data structure or a container where only the top elements can be accessed or operated. It operates on the principle of LIFO (Last In First Out). There could be multiple visualisations to understand the same. Let’s assume a bunch of books, you can see the book at the top only and that can be accessed first only. In order to access the book in the middle or in the bottom, you first need to remove the books above them.

You can also read about the - hash function in data structure

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Basic Operations of the stack includes

PUSH Operation:

It is basically the insertion of the elements. In the case of the stack, we call it PUSH Operation. Now, how many ways insertions can be done in a stack? There is only one-way insertion is done in a stack and it is the top of the stack. So push operation can be performed on the top of the stack.

Implementation:

1. Using Array: Whenever a new element is inserted, the value of top increases by 1. 

void push(int item)
{
if ( top == capacity - 1 )
print( "Stack overflow!" )
else
{
arr[top+1] = item
top = top + 1
}
}

 

2. Using Linked List: The benefit of using Linked List for implementation is there would be no worry to check if the stack is full or not.

void push(int item)
{
ListNode temp = ListNode(item)
temp.next = head
head = temp
}

POP Operation:

The most important operation of the stack is the POP Operation, what we usually say, deletion in other data structures is something we call POP in the case of the stack. We can simply remove the top element of the stack by calling the POP operation. We can also choose to return the value of the popped element if we want to return the element, this is completely the programmer’s choice.

Implementation:

1. Using Arrays:

void pop()
{
if ( isEmpty() == True )
print( "Stack is empty!" )
else
top = top - 1
}

 

2. Using Linked List: The top is represented by the head. Hence deletion can be done in this way.

void pop()
{
if ( head == NULL )
print ( "Stack is empty!" )
else
head = head.next
}

 

PEEK Operation:

This operation is just there to see the top element of the stack. Users would not be able to modify the stack in this operation. This is similar to the top operation we see in other data structures.

Implementation:

  1. Using Array:
int peek()
{
if ( isEmpty() == True )
{
print( "Stack is empty!" )
return -1
}
else
return arr[top]
}

 

2. Using Linked List:

int peek()
{
if ( head == NULL )
{
print ( "Stack is empty!" )
return -1
}
else
return head.val
}

isEmpty Operation:

This operation is just to check if the stack is empty or not. This operation's return type is boolean, which indicates whether the stack is empty.

Implementation:

  1. Using Array:
bool isEmpty()
{
if ( top == -1 )
return True
else
return False
}

 

2. Using Linked List:

bool isEmpty()
{
if ( head == NULL )
return True
else
return False
}

Algorithm to reverse String using Stack:

It is very important to focus on the algorithm, to write better code. This could be the first step in order of picking the problem, one must think of the best algorithm before jumping to the implementation and the code.

The following steps could be helpful:

  • The first step would be, creating an empty stack.
     
  • Then pick the characters from the string one by one and put them to the stack, so that the last character of the string comes at the top of the stack.
     
  • Now, in the last step, pop the stack and put the popped characters back in the empty string.

Also, see Recursion

Implementation:

//implementing Stack class
import java.util.*;
class Stack
{
int size;
int top;
char[] a;
boolean isEmpty()
{
return (top < 0);
}
Stack(int n)
{
top = -1;
size = n;
a = new char[size];
}
//implementing push function
boolean push(char x)
{
if (top >= size)
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
return true;
}
}
//implementing pop function
char pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
char x = a[top--];
return x;
}
}
}
// reversing the string ( main function )
public class ReverseStringUsingStack
{
public static String reverseString(String str)
{
String reversedString = "";
int lenghOfString = str.length();
Stack stack = new Stack(lenghOfString);
for (int i = 0; i < lenghOfString; i++) {
stack.push(str.charAt(i));
}
for (int i = 0; i < lenghOfString; i++)
{
char ch = stack.pop();
reversedString = reversedString+ ch;
}
return reversedString;
}
public static void main(String args[])
{
String s= new String("CodingIsLove");
String result = reverseString(s);
System.out.println("Reversed string is " + result);
}
}

Output:

The reversed string is evoLsIgnidoC

output image

We could have used StringBuilder to reverse the string, which could be a better choice for reversing the string as it is mutable, unlike the String class.

Difference between String and StringBuilder

Let’s see the differences that string and stringBuilder have

  • The first and foremost difference would be mutability. Strings are immutable in nature, which means string objects cannot be changed while StringBuilder is mutable by nature which tells that it can be changed as per the need.
     
  • We can use strings when it is going to be constant throughout the program, while StringBuilder is used when there is a need to manipulate strings a lot of times in writing the code.
     
  • Strings can easily be converted to StringBuilder by just passing the String object to StringBuilder class.
     

Let’s see the differences that string and stringBuilder have

  • The first and foremost difference would be mutability. Strings are immutable in nature, which means string objects cannot be changed while StringBuilder is mutable by nature which tells that it can be changed as per the need.
     
  • We can use strings when it is going to be constant throughout the program, while StringBuilder is used when there is a need to manipulate strings a lot of times in writing the code.
     
  • Strings can easily be converted to StringBuilder by just passing the String object to StringBuilder class.
     

Must Read Stack Operations

Frequently Asked Questions

How to reverse a string?

The reversal of a string can be done using many ways. One of them is using stack. As the stack follows LIFO ( Last in, first out ) principle, the order of popped elements would be the reverse of the original string. 

How to reverse a string in Java using stack?

To reverse a string using a stack in Java, first, create an empty stack of characters. Then, push each character of the original string onto the stack. Pop each character off the stack and append it to a new string to get the reversed string.

How do you reverse items in a stack?

To reverse the items in a stack, create an empty stack first. When the original stack is still full, pop each item and place it on the empty stack. The items in the original stack will be rearranged as a result of this.

Conclusion

So, a string can be reversed easily with the help of the Stack and it uses its basic operations like push and pop to achieve the same. Hope you liked the code and enjoyed the article.

Recommended Problems:

Related articles:

Happy Coding and learning with Coding Ninjas!

Previous article
How To Sort A Stack Using Recursion?
Next article
Check if an array is stack permutation of other
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass