Question

A palindrome is a string of characters (a word, phrase, or sentence) that is the same regardless of whether you read it forward or backward – assuming that you ignore spaces, punctuation and case. For example, Race car is a palindrome. So is A man, a plan, a canal: Panama.

1. Describe how you could use a stack to test whether a string is a palindrome.

2. Describe how you could use a queue to test whether a string is a palindrome.

Answer 1

Algorithms for both the cases are given below:

1. Algorithm to check palindrome string using stack

• Find the length of the input string using strlen function and store it in an integer variable "length".
• Using a for loop, traverse input string from index 0 to (length-1) and push all characters in stack.
• Remove (Pop) characters from stack one by one using a for loop and compare it with the corresponding character of input string from the beginning(traverse from index 0 to length-1). If we found a mismatch the input string is not a palindrome string otherwise palindrome string.

2. Algorithm to check palindrome string using queue

• Find the length of the input string "input_string" using strlen function and store it in an integer variable "length".
• Using a for loop, traverse input string from index (length-1) to 0 and push all characters in the queue.
• Remove (Pop) characters from queue one by one using a for loop and store them in a new string variable "reverse_string".
• Compare the variables "input_string" with "reverse_string" from the beginning (traverse from index 0 to length-1). If we found a mismatch the input string is not a palindrome string otherwise it is palindrome string.