Table of Contents
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”.
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.
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:
- 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 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. The return type of this operation is boolean and it tells whether the stack is empty or not.
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 a 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, the last step, pop the stack and put the popped characters back in the empty string.
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 as well 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.
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
Happy Coding and learning with Coding Ninjas!
By Deepak Jain
