Learn how you can become a Python programmer in just 12 weeks.

    We respect your privacy. Unsubscribe at anytime.

    Check if Palindrome with a Queue and a Stack in Python

    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.

    A Stack and Queue represented – elements are taken pop/dequeued from right side

    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
    

    Python for Finance: Unlock Financial Freedom and Build Your Dream Life

    Discover the key to financial freedom and secure your dream life with Python for Finance!

    Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.

    Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.

    Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.

    Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!

    Python for Finance a 21 hours course that teaches investing with Python.

    Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.

    “Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.

    Leave a Comment