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

3 Steps to Understand and Implement a Queue in Python

What will we cover in this tutorial?

We will cover what a Queue is. A Queue is a data structure used by computers. It resembles a queue as we know it.

The key things a Queue should have are efficient operations for insertion (enqueue) and removal (dequeue) of the queue. In this tutorial we will understand what a is, how to represent it, and how to implement the efficient operations.

Step 1: Understand a Queue

A Queue is like a queue in real life.

A Queue is used in computer science in many scenarios. One scenario is when a resource is shared among multiple consumers, then a Queue is set in front.

This resembles the real world, where we use queues in the grocery store, pharmacy, you name it. In all stores, where we have more consumers than registers (the resource) to serve.

A Queue serves the principle, First-in-first-out or FIFO.

A simple diagram shows the operations of a Queue.

A queue with the two operations enqueue and dequeue

The above queue shows the direction of the Queue and the order they have been added symbolized with the numbers 1 to 8, where 8 is about to be added.

The operations on the Queue are as follows.

  • enqueue Adds an element to the back of the Queue.
  • dequeue Removes the element of the front of the Queue.

Normally, a Queue would also have a function is_empty, which checks whether the Queue is empty.

Step 2: How to represent a Queue item with an element

How do you represent the above items of the Queue?

Well, we need to be able to keep an order of the Queue. Let’s try to draw it and see what we can figure out.

The structure we need to keep.

Surprised? Well, the Queue goest from left to right, while the arrows between the items go from right to left.

Actually, the items of the Queue can be represented by a simple Node class.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

This simple Node class has an element and the pointer to next_node. Hence, the next_node are the arrows in the diagram above. And the element are representing the numbers in the above diagram. Obviously, the element can contain anything.

Step 3: Create a Queue class to represent the enqueue and dequeue operations

Let’s start in the simple.

Given the Nodes, we need a class Queue with a head and tail to implement the operations enqueue and dequeue

The above suggest that if we have head and tail pointer, we can have what we need to implement a Queue data structure.

The enqueue function has the special case where the Queue is empty, otherwise it will do as follows.

  • enqueue Create a new Node with the element. Point tails next_node at created Node. Then update tail to point at created Node.

Here we can implement it as follows.

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

The dequeue is a bit more involved.

  • dequeue Get the element from the Node that head points at. If head Node and tail Node is the same (that is if it is the last Node in the Queue), then point tail and head at None. Otherwise, set the head to point at the the next_node head points at.
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

Notice that the dequeue does fail if the Queue is empty. This is dealt with by creating a is_empty function, which returns whether the Queue is empty.

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

That is it.

The full code including a string representation to enable it to be printed

See the full code below. It also contains the __str__(…) function, witch enables it to be printed. Also, how to use it.

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] + "]"

q = Queue()
for i in range(10):
    q.enqueue(i)
while not q.is_empty():
    print(q.dequeue(), '', end='')

The above code will result in the following output.

[0 1 2 3 4 5 6 7 8 9]
0 1 2 3 4 5 6 7 8 9

Implement a Queue using a Circular Linked List with Only One Pointer

What will we cover?

Think about the following challenge. Given a circular linked. Create a queue with constant time operations for enqueue and dequeue. Also, you can only have one pointer to the Circular Linked List.

Example of a circular linked list and a queue with only one pointer.

Consider the above diagram. How will you insert a new element? Okay, that seems easy. But how do you remove the oldest element from it? With constant time!

Yes, that is not that trivial.

Step 1: Create the node class used to represent the circular linked list

There are of course many ways to go about how to create a linked list, and more specifically a circular linked list.

Some implement the classes together, that is both the node and the linked list together. I like to split them from each other. That way, you keep things simple.

Hence, to represent the circular linked list, I suggest the following simple class for a node. Then have the logic of the circular linked list in a different class.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

Notice, that the above Node could also be used in a linked list alone. It is a simple building block, which can be used as you please.

Step 2: Create the Queue using a circular linked list

You could create a class for a circular linked list, but we will use it closely from the queue.

The art is to create a queue with only one pointer to the circular linked list structure. The circular linked list can be represented with the Node class above.

The first operation we need is to enqueue an element in the queue. That is to insert an element in the queue.

The special case of inserting the first element, would result in a circular linked list with only one Node, which points at itself.

It is first when we insert the second element it becomes tricky. Which Node should the Queue pointer point at?

This is interesting. We need to be able to insert the element in constant time. Hence, if the queue has more element, it should not need to go all the way around the circular linked list. That makes it necessary, for us to be able to find the last element added with constant number of operations.

Also, the element in the circular linked list point in the direction the were inserted.

This results to that we need to point at the last inserted element.

Assuming in the above that the elements are inserted in the order 1, 2, 3, and 4.

Then we can insert the the elements with the following code.

class Queue:
    def __init__(self):
        self.pointer = None
    def enqueue(self, element):
        if self.pointer is None:
            node = Node(element)
            self.pointer = node
            self.pointer.next_node = node
        else:
            node = Node(element, self.pointer.next_node)
            self.pointer.next_node = node
            self.pointer = node

The code of enqueue shows first the base case, where the circular linked list is empty. Then the case where minimum one Node already exists.

Let’s follow the code of above. Before we call enqueue let’s assume it looks as follows.

First thing is to create a new Node (with the new element, below we use 5) and point it at the queues pointer next_node.

Point the queue pointers next_node at the new Node we created.

Then we update the queue pointer to point at the new Node.

That is it. We still have a circular linked list and only one pointer from the Queue. Notice, that this all happens in constant number of operations. That is, it is independent of how many Nodes are in the circular linked list. If we have 6,000 Nodes, we still only use the 3 operations described above. Hence, enqueue has a O(1) worst case run time.

Next step will see if we can dequeue correctly from the structure, while keeping it intact.

Step 3: How to dequeue from the circular linked list

This seems tricky at first.

But look at the following diagram, where we have 4 elements. They have been inserted by the enqueue function given in Step 2. The first element was 1, then 2, then 3, and finally element 4.

Hence, when we dequeue, we want to return and remove element 1. And the circular linked list should look like this afterwards.

Also, the dequeue operation should be done in constant number of operations.

Obviously, there is a special case, when we only have one element in the queue. Then we remove it and make the queue pointer point at None.

class Queue:
    # Continued...
    def dequeue(self):
        if self.pointer is None:
            return None
        if self.pointer.next_node == self.pointer:
            element = self.pointer.element
            self.pointer = None
            return element
        element = self.pointer.next_node.element
        self.pointer.next_node = self.pointer.next_node.next_node
        return element

Otherwise, we get the element from the queue pointers next_node.

Then we update the queue pointers node to point at next_node.next_node. Notice, that this will keep the structure intact. Also, we keep the dequeue function at a constant number of operations, hence, O(1).

The full code with a print queue function

Here is the full code including a representation to print the queue.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

class Queue:
    def __init__(self):
        self.pointer = None
    def enqueue(self, element):
        if self.pointer is None:
            node = Node(element)
            self.pointer = node
            self.pointer.next_node = node
        else:
            node = Node(element, self.pointer.next_node)
            self.pointer.next_node = node
            self.pointer = node
    def dequeue(self):
        if self.pointer is None:
            return None
        if self.pointer.next_node == self.pointer:
            element = self.pointer.element
            self.pointer = None
            return element
        element = self.pointer.next_node.element
        self.pointer.next_node = self.pointer.next_node.next_node
        return element
    def __str__(self):
        if self.pointer is None:
            return "empty"
        first = self.pointer
        node = first.next_node
        result = "["
        while node != first:
            result += str(node.element) + '->'
            node = node.next_node
        return result + str(node.element) + '->...]'

queue = Queue()
for i in range(20):
    queue.enqueue(i)
    print(queue)
for _ in range(21):
    queue.dequeue()
    print(queue)
for i in range(5):
    queue.enqueue(i)
    print(queue)

The beginning of the output will be as follows.

[0->...]
[0->1->...]
[0->1->2->...]
[0->1->2->3->...]
[0->1->2->3->4->...]
[0->1->2->3->4->5->...]

Queue vs Python list – Comparing the Performance – Can a simple Queue beat the default Python list?

How to profile a program in Python

In this video we will see how cProfile (default Python library) can help you to get run-times from your Python program.

Queue vs Python lists

In this video we will compare the performance of a simple Queue implemented directly into Python (no optimisations) with the default Python list.

Can it compare with it on performance?

This is where time complexity analysis come into the picture. A Queue insert and deletion is O(1) time complexity. A Python list used as a queue has O(n) time complexity.

But does the performance and run-time show the same? Here we compare the run-time by using cProfile in Python.

Want to learn more about Linked-lists, Stacks and Queues?

Check out my Course on Linked Lists, Stacks and Queues

How to Implement a Queue in Python and Compare Performance with a Python list

What will we cover in this article

  • What is a Queue?
  • Implement a Queue in Python
  • Make performance testing of it
  • Compare it with performance of a Python list

What is a Queue?

We all know what a queue is. You go to the grocery store and get spinach, strawberry and bananas for your shake. Then you see a long line of people in front of the register. That line is a queue.

The same holds in programming. You create queues to process data or input of any kind.

How to implement a Queue in Python

It is easier than you think.

First you create a Node class to represent each node in a queue. A node is an abstraction to represent a point to the next node and the actual element.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

Then you create the class for the Queue.

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:
            n = Node(element, self.tail)
            self.tail.next_node = n
            self.tail = n
    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

How does it work. Let’s make a simple example.

q = Queue()
for i in range(10):
    q.enqueue(i)
while not q.is_empty():
    print(q.dequeue())

Which will output.

0
1
2
3
4
5
6
7
8
9

Yes! You guessed it.

How do we test performance?

I like to use the cProfile library. It is easy to use and gives informative results.

So how do you test performance? You simply import the cProfile library and use the cProfile.run(…) call.

You also need to do some operations to see how your Queue performs. See the code as an example.

import cProfile

def profile_queue(n):
    q = Queue()
    for i in range(n):
        q.enqueue(i)
    while not q.is_empty():
        q.dequeue()

def profile(n):
    profile_queue(n)

cProfile.run("profile(100000)")

Which will result in the following output.

   Ordered by: standard name
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.819    0.819 <string>:1(<module>)
   100000    0.310    0.000    0.351    0.000 Queue.py:11(enqueue)
   100000    0.308    0.000    0.308    0.000 Queue.py:19(dequeue)
   100000    0.041    0.000    0.041    0.000 Queue.py:2(__init__)
   100001    0.021    0.000    0.021    0.000 Queue.py:27(is_empty)
        1    0.132    0.132    0.819    0.819 Queue.py:34(profile_queue)
        1    0.000    0.000    0.819    0.819 Queue.py:42(profile)
        1    0.000    0.000    0.000    0.000 Queue.py:7(__init__)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.008    0.008    0.008    0.008 {range}

The interesting line is line 9, which tells us how much time is spend in the call to profile_queue.

But is the result good?

We need to compare it to other implementations.

Performance testing the Queue with a Python list

Python lists are used for anything. Can we use a Python list as a Queue. Of course. Let’s try to implement that and compare it to our Queue.

import cProfile

def profile_queue(n):
    q = Queue()
    for i in range(n):
        q.enqueue(i)
    while not q.is_empty():
        q.dequeue()

def profile_list_as_queue(n):
    q = []
    for i in range(n):
        q.insert(0,i)
    while len(q) > 0:
        q.pop()

def profile(n):
    profile_queue(n)
    profile_list_as_queue(n)

cProfile.run("profile(100000)")

How does that compare? Let’s see.

   Ordered by: standard name
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    3.680    3.680 <string>:1(<module>)
   100000    0.295    0.000    0.331    0.000 Queue.py:11(enqueue)
   100000    0.298    0.000    0.298    0.000 Queue.py:19(dequeue)
   100000    0.036    0.000    0.036    0.000 Queue.py:2(__init__)
   100001    0.019    0.000    0.019    0.000 Queue.py:27(is_empty)
        1    0.104    0.104    0.756    0.756 Queue.py:34(profile_queue)
        1    0.101    0.101    2.924    2.924 Queue.py:42(profile_list_as_queue)
        1    0.000    0.000    3.680    3.680 Queue.py:50(profile)
        1    0.000    0.000    0.000    0.000 Queue.py:7(__init__)
   100001    0.005    0.000    0.005    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   100000    2.805    0.000    2.805    0.000 {method 'insert' of 'list' objects}
   100000    0.012    0.000    0.012    0.000 {method 'pop' of 'list' objects}
        2    0.004    0.002    0.004    0.002 {range}

Wow. Our Queue is way faster than the Python list.

But how is it comparing in general?

Comparing the performance of the Queue and a Python list as a Queue.

While it is difficult to see, the performance of the Queue is O(n) (linear) while the performance of the Python list as a Queue is O(n^2).

Hence, the Queue will outperform the Python list for this use case.