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

from collections import deque

def is_palindrome(text):
    letters = [ch.lower() for ch in text if ch.isalnum()]
    dq = deque(letters)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

for s in ['MADAM', 'Nurses run', 'PYTHON']:
    print(s, '->', is_palindrome(s))

Output

MADAM -> True
Nurses run -> True
PYTHON -> False
``` …

Concept understanding

A queue removes only from the front; a deque (double-ended queue) removes from either end in O(1). That is precisely the operation a palindrome check needs — first vs last, second vs second-last, and so on inward. Using a plain list with pop(0) would also work but costs O(n) per removal because every remaining element shifts left; deque.popleft() is O(1).

We stop when len(dq) <= 1, because a single leftover middle character (odd-length string) has nothing to compare against and never breaks a palindrome.

Algorithm 4.1 applied

1. Read the string.
2. Keep only the alphanumeric characters and convert them to lower case (so Nurses run and Madam are judged on letters alone).
3. Insert all these characters into a deque.
4. While the deque holds more than one character: a. front = dq.popleft() b. rear = dq.pop() c. If front != rear → return False.
5. If the loop finishes → return True.

Program

from collections import deque

def is_palindrome(text):
    '''Return True if text is a palindrome, using a deque.'''
    letters = [ch.lower() for ch in text if ch.isalnum()]
    dq = deque(letters)

    while len(dq) > 1:
        front = dq.popleft()     # remove from the FRONT
        rear = dq.pop()          # remove from the REAR
        if front != rear:
            return False
    return True


# ---- driver ----
for s in ['MADAM', 'Nurses run', 'PYTHON', 'Level']:
    if is_palindrome(s):
        print(repr(s), 'is a palindrome')
    else:
        print(repr(s), 'is NOT a palindrome')

Output

'MADAM' is a palindrome
'Nurses run' is a palindrome
'PYTHON' is NOT a palindrome
'Level' is a palindrome

Dry run — MADAM

Deque starts as ['m','a','d','a','m'].