## What will we cover in this tutorial?

How can you check if a string is a palindrome. Obviously this can be done in various creative ways. In this tutorial we will use a **Queue** and a **Stack** to solve it.

## Step 1: What is a palindrome?

A palindrome is a sequence of characters which reads the same backward as forward.

Common examples are:

- racecar
- madam

Where you notice that RACECAR has the same sequence of characters, whether you read it from *left-to-right*, or from *right-to-left*.

Also, palindromes are also considered with dates. Examples could be:

*11/11/11 11:11**02/02/2020*

If sentences are considered as palindrome, often the spaces, punctuation, and upper/lowercase variations are ignored. Examples could be:

- “Madam I’m Adam”
- “Sit on a potato pan, Otis”
- “Able was I, ere I saw Elba.”

## Step 2: A simple implementation to test palindrome

Let’s start with understanding how we can check if sequence of characters is a palindrome by using a **Stack** and a **Queue**.

If you are new to a **Stack**, then we can propose you read this tutorial or this.

Also, if you are not familiar with a **Queue**, then we propose you read this tutorial or this.

When we insert into a Stack and Queue, they will be removed in opposite orders.

Wow. That is a great idea. Why not add (**push** and **enqueue**) all characters on a **Stack** and **Queue**. Say, we do that for **madam**.

Then they the order of removal (**pop** and **dequeue**) will give the same elements, as it is a palindrome. If it was not a palindrome, say “**12345**“, then the elements removed from simultaneously from the **Stack** and **Queue** would not be identical.

This leads to the following piece of code, where we have included implementations of a **Queue** and **Stack**. See this tutorial for **Stack** and this tutorial for a **Queue**, if you need explanation of the code.

```
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
def is_empty(self):
return self.stack == None
def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
def is_empty(self):
return self.head is None
def __str__(self):
if self.head is None:
return None
node = self.head
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
def is_palindrome(s):
stack = Stack()
queue = Queue()
for c in s:
stack.push(c)
queue.enqueue(c)
print(stack)
print(queue)
while not stack.is_empty():
if stack.pop() != queue.dequeue():
return False
return True
print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))
```

This would result in the following output.

```
[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False
```

## Step 3: Make it work on for general strings

The above code does not work if we encounter a string like, *“Sit on a potato pan, Otis*.*“*

One way to deal with this is to have a function in front of the **is_palindrome** from previous step.

This function can convert the format of a sequence of characters to the format that **is_palindrome** will require. This is a nice way to break down functionality in your code and not overcomplicate functions.

Let’s try that. We will rename **is_palindrome** to **_is_palindrome**, to indicate that it is not to be used.

```
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
def is_empty(self):
return self.stack == None
def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
def is_empty(self):
return self.head is None
def __str__(self):
if self.head is None:
return None
node = self.head
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
def _is_palindrome(s):
stack = Stack()
queue = Queue()
for c in s:
stack.push(c)
queue.enqueue(c)
print(stack)
print(queue)
while not stack.is_empty():
if stack.pop() != queue.dequeue():
return False
return True
def is_palindrome(s):
s = s.lower()
r = ""
for c in s:
if c in "abcdefghijklmnopqrstuvwxzy1234567890":
r += c
return _is_palindrome(r)
print(is_palindrome("123454321"))
print(is_palindrome("racecar"))
print(is_palindrome("112"))
print(is_palindrome("Madam I'm Adam"))
print(is_palindrome("Sit on a potato pan, Otis"))
print(is_palindrome("Able was I, ere I saw Elba."))
print(is_palindrome("Able was I, where I saw Elba."))
```

Which will result in the following output.

```
[1 2 3 4 5 4 3 2 1]
[1 2 3 4 5 4 3 2 1]
True
[r a c e c a r]
[r a c e c a r]
True
[2 1 1]
[1 1 2]
False
[m a d a m i m a d a m]
[m a d a m i m a d a m]
True
[s i t o n a p o t a t o p a n o t i s]
[s i t o n a p o t a t o p a n o t i s]
True
[a b l e w a s i e r e i s a w e l b a]
[a b l e w a s i e r e i s a w e l b a]
True
[a b l e w a s i e r e h w i s a w e l b a]
[a b l e w a s i w h e r e i s a w e l b a]
False
```