How to check for a Palindrome string using stack in java / Java program to find Palindrome of a string using stack

A string is said to be Palindrome which when reversed is the same as original string. In other words, when a string and its reversed form are same, the string is called a Palindrome string.
Example, “radar”, “rececar”, “madam”, “refer” are all palindrome strings.

There are many ways to check for a Palindrome string in java. This post will focus on testing for Palindrome string using a java.util.Stack.

A stack is a data structure which holds its elements in Last In First Out (LIFO) principle. Element added to the top of the stack is retrieved first from it and element added first is retrieved last. Adding element to the stack is called push operation and removing element from the stack is called pop.

import java.util.LinkedList;
import java.util.Stack;

public class PalindromeCheckerUsingStack {

	public static void main(String[] args) {
		checkPalindromeUsingStack();
	}

	public static void checkPalindromeUsingStack() {
		String stringToCheck = "abccba";
		String palindromeString = "";
		// initialize a stack
                Stack stack = new Stack();
                // iterate over the string
		for (int i = 0; i < stringToCheck.length(); i++) {
			char character = stringToCheck.charAt(i);
			stack.push(character);
		}
                // iterate over the stack till it is empty
		while (!stack.isEmpty()) {
                        // add the character at the top to a string   
			palindromeString = palindromeString + stack.pop();
		}
                // compare original and reversed strings  
		if (stringToCheck.equals(palindromeString)) {
			System.out.println("String is palindrome");
		} else {
			System.out.println("String is not palindrome");
		}
	}
}

Output

String is palindrome

Explanation

Iterate over the string and in each iteration, get the character at current loop counter and add it to stack. Thus, the character at the start of the string are inserted at the bottom of the stack and the characters towards the end are inserted at the top of stack. After the iteration of string completes, the stack contains the characters of the string in reverse order with the last character at the top of stack and the first character at the bottom.
Now the stack is iterated till it becomes empty. In every iteration of the stack, the character at the top of the stack is popped off and added to a new string which means the character at the end of original string becomes the character at the start of the new string. These strings are then compared. If they are same means the original string was palindrome otherwise not.

This method can also be used to determine palindrome string of another string. The string formed after removing all the characters from the stack is the required palindrome string.

Leave a Reply