In our previous post, we saw how to create a custom stack implementation in java. Today we are going to extend the same implementation to perform additional operations like reversing, checking empty or full etc.
Table of Contents
Approach 1: [Simple & Best Approach]
We have used the same Stack class from this post [Java Stack Implementation Simple Example] with small modification like array type changed from int to char.
Modified Stack Class: [Stack.java]
package com.ngdeveloper;
public class Stack {
char item[];
int lastIndex;
int maxArraySize;
public Stack(int arraySize) {
item = new char[arraySize];
maxArraySize = arraySize;
lastIndex--;
}
public char popOut() {
int temp = lastIndex;
// after the value returned need to decrement, but after return we cant
// so created the temp variable here for the same.
--lastIndex;
return item[temp];
}
public void pushIn(char newInput) {
if (isFull()) {
System.out.println("Can't add its already full!");
} else {
lastIndex++;
item[lastIndex] = newInput;
}
}
public boolean isEmpty() {
return (lastIndex == -1);
}
public boolean isFull() {
return (maxArraySize - 1 == lastIndex);
}
}
Main Class [Main.java]:
package com.ngdeveloper;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String enteredInput = input.nextLine();
input.close();
getReverseString(enteredInput);
System.out.println("Input ==> " + enteredInput);
System.out.println("Reversed ==> " + getReverseString(enteredInput));
}
public static String getReverseString(String inputStr) {
String reversedString = "";
Stack stack = new Stack(inputStr.length());
for (int i = 0; i < inputStr.length() ;
i++){
stack.pushIn(inputStr.charAt(i));
}
while (!stack.isEmpty()) {
reversedString = reversedString + stack.popOut();
}
return reversedString;
}
}
Output:
rithu Input ==> rithu Reversed ==> uhtir
Approach 2:
Here, I very lightly used stack for reversing, additional implementations are also implemented. Just for your reference posting this approach as well. But I highly recommend you to check only the Approach 1 for reversing the string using stack implementation.
Things to Note:
1. We have created two arrays named item and reverse. item array used to store the values to the array as the same order. But reverse array stores the values in the reverse order.
2. Reverse array populated like this,
lastIndex++; item[lastIndex] = newInput; reverse[(maxArraySize - 1) - lastIndex] = item[lastIndex];
Here,
lastIndex is the pointer which keeps eye on the current position of the item array.
maxArraySize is the total size of the array when initialized. [Assume it is 2 now]
Example:
if your input is jd
then first time lastIndex would be -1 because in the constructor it is decremented to 1 from the default value 0, so it is -1 now.
so item[0] = j same time,
assumption [maxArraySize = 2]
reverse[(2-1)-0] => reverse[1]=j;
if the maxArraySize is 3 (of course in the below program, it is also dynamic based on the input string)
reverse[(3-1)-0] => reverse[2], now it will have the
so while performing stack pushin itself both the arrays are ready one with input order and the other with reverse order. Of course, it is better to perform reversing separately rather than performing in pushIn method, because even though user do not want reverse string this reverse array will be created here.
This will be corrected in our next stack implementation. But now let’s concentrate on the other stuff’s.
3. Created three setArrayStack() methods to provide more input options to user. One accepts int array, other accepts char and string.
4. We have created push and pop based on our integer inputs, so convertions are happening just to pass the input to integers only. (This can also be changed as per our implementation need).
5. isFull() and isEmpty() methods are created to overcome the arrayindexoutofbounds exception.
Reversing a string using Stack Implementation:
Stack class: [Stack.java]
package com.ngdeveloper;
public class Stack {
int item[];
int reverse[];
int lastIndex;
int maxArraySize;
public Stack(int arraySize) {
item = new int[arraySize];
reverse = new int[arraySize];
maxArraySize = arraySize;
lastIndex--;
}
public int popOut() {
int temp = lastIndex;
// after the value returned need to decrement, but after return we cant
// so created the temp variable here for the same.
--lastIndex;
return item[temp];
}
public void pushIn(int newInput) {
if (isFull()) {
System.out.println("Can't add its already full!");
} else {
lastIndex++;
item[lastIndex] = newInput;
reverse[(maxArraySize - 1) - lastIndex] = item[lastIndex];
}
}
public boolean isEmpty() {
return (lastIndex == -1);
}
public boolean isFull() {
return (maxArraySize - 1 == lastIndex);
}
public int[] getFullArray() {
return item;
}
public int[] getReverseArray() {
return reverse;
}
public char[] getReverseCharArray() {
char[] temp = new char[reverse.length];
for (int i = 0; i < reverse.length; i++) {
temp[i] = (char) reverse[i];
}
return temp;
}
public String getReverseString() {
char[] temp = getReverseCharArray();
return String.copyValueOf(temp);
}
public void setArrayStack(int[] array) {
for (int i = 0; i < array.length; i++) {
this.pushIn((int) array[i]);
}
}
public void setArrayStack(String array) {
this.setArrayStack(array.toCharArray());
}
public void setArrayStack(char[] array) {
for (int i = 0; i < array.length; i++) {
this.pushIn((char) array[i]);
}
}
}
Main class: [Main.java]:
package com.ngdeveloper;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String test = input.nextLine();
input.close();
Stack stack = new Stack(test.toCharArray().length);
stack.setArrayStack(test);
System.out.println("Input ==> " + test);
System.out.println("Reversed ==> " + stack.getReverseString());
}
}
Output:
rithu Input ==> rithu Reversed ==> uhtir
Hope you enjoyed our advanced stack implementation!