Question 9 of 9advanced✨ CreateLong Answer5 marks

Write a python program to check whether the given string is palindrome or not, using deque. (Hint: refer to algorithm 4.1)

Correct Answer

python def isEmpty(myDeque): if len(myDeque) == 0: return True else: return False

def insertRear(myDeque, element): myDeque.append(element)

def deletionFront(myDeque): if not isEmpty(myDeque): return myDeque.pop(0) else: print("Queue underflow")

def deletionRear(myDeque): if not isEmpty(myDeque): return myDeque.pop() else: print("Queue underflow")

def isPalindrome(str): myDeque = [] # Step 1 & 2: Insert all characters in deque from rear for char in str: insertRear(myDeque, char)

# Step 4, 5 & 6: Remove from both ends and match
while len(myDeque) > 1:
    front_char = deletionFront(myDeque)
    rear_char = deletionRear(myDeque)
    if front_char != rear_char:
        return False
return True

Main program

string = input("Enter a string: ") if isPalindrome(string): print(string, "is a Palindrome") else: print(string, "is not a Palindrome")

Exercise: EXERCISE | Q: 8 | (Page 14)
For More Understanding

Explanation

This program implements Algorithm 4.1 from the textbook. The algorithm works by first inserting all characters of the string into the deque using INSERTREAR operation. Then, characters are removed from both ends (front and rear) using DELETIONFRONT and DELETIONREAR operations. These two characters are matched - if they are same, the process continues until the deque is empty or has only one character left, confirming the string is a palindrome. If any pair doesn't match, the string is not a palindrome.

Solution Steps

  1. Step 1: Define isEmpty(), insertRear(), deletionFront(), and deletionRear() functions for deque operations

  2. Step 2: Create isPalindrome() function that takes a string as argument

  3. Step 3: Traverse the string left to right and insert each character in deque using insertRear()

  4. Step 4: Use a while loop to remove characters from both front and rear ends until deque has 1 or 0 characters

  5. Step 5: Compare the two removed characters - if they don't match, return False

  6. Step 6: If loop completes without mismatch, return True (string is palindrome)

Previous