Question

A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. Your task is to construct a python algorithm to receive as input a string of characters and check whether it is a palindrome using a stack and a queue. Your ADTs contains the following methods:

Queue

• Queue() – constructor
• enqueue(e) – enqueue an element
• dequeue(e) – dequeue an element
• len() – returns the number of elements in the queue

Stack

• Stack() - constructor
• push(e) – adds an element into the stack
• pop(e) – removes an element of the stack
• len() – returns the number of elements in the queue

Please explain the solution with details and document the code.

Answer 1

Algorithm:

1. First of all, we take the input.
2. Then, we push/insert the characters of the input string to the stack and the queue character-by-character.
3. After that, we pop() both stack and queue and match character-by-character.
4. When every character matches, then it means the given string is a palindrome. In other cases, the given string is not a palindrome.
5. We have maintained a counter to check, whether each character matches or not.

Please refer to the comments of the program for more clarity.

# Declaring the function to check the palindrome
def checkPalindromeOrNot(givenInput):

    stack = []  #Declaring a stack
    queue = []  #Declaring a queue

    # Adding value to stack and queue
    for char in givenInput:
        stack.append(char)  # Adding value to stack
        queue.append(char)  # Adding value to queue

    counter = 0  # Initializing counter with 0

    # Matching the values of stack and queue
    # Stack is last-in and first-out
    # Queue is first-in and first-out

    # When the given string is palindrome then each pop of stack and pop will match
    for i in range(0, len(givenInput)):
        if(stack.pop() == queue.pop(0)):
            counter+=1  # Increasing the counter when characters match

    # Printing the value
    # When counter == length of the given string, then the given string is a palindrome
    if(counter == len(givenInput)):
        print('Input string is a palindrome')
    else:
        print('Input string is not a palindrome')

# Taking the input
givenInput = input()

# Calling the function
checkPalindromeOrNot(givenInput)

Input/Output - Code/Run - 1:

Input/Output - Code/Run - 2:

Input/Output - Code/Run - 3:

Please let me know in the comments in case of any confusion. Also, please upvote if you like.