Reverse a String using Stack

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

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:

• Sort A Stack
• Stack Permutation
• Max Stack
   

Related articles:

• Reverse A String In C

Happy Coding and learning with Coding Ninjas!