Avoid Common Object Oriented Programming Pitfalls

What will we cover in this tutorial?

I did them myself. When you first learn about object oriented programming, you get exited about it and want to turn everything into objects.

Very often it fails to make the code easier to maintain and understand. Yes, that is one core goal of creating object oriented programming, to make it easier to maintain and understand.

Often we just turn the traditional way of programming into objects. But that is not the point. The point is to model it in an object oriented way.

Before that, let’s just look at why we use object oriented programming.

Step 1: Why use object oriented programming?

When introducing object oriented programming to beginners it often introduces too many concepts at once.

Simply because object oriented programming is awesome and can do so many things.

Let’s just start simple with the core of the object oriented programming idea.

We want to make your program easier to understand and maintain.

That is the goal for any programmer. Also, when it comes to object oriented programming.

Object oriented programming tries to make the link between the real world and the programming world as close as possible. We humans understand the objects in the real world better than we understand how a computer pushes bits and bytes around in the memory and CPU.

Luckily, we do not need to understand all that. We just need to understand how to program the computer through a programming language.

Object oriented programming tries to make that easier with modeling the programs with objects, which are related to the way we humans understand things.

Let’s try with a simple example of a Stack.

A Stack has a top and bottom, it has operations push and pop.

How would you model the above without using object oriented programming.

stack_size = 8
stack = [None]*stack_size
top = -1 # empty stack
def pop():
    global top, stack
    if top == -1:
        return None
    else:
        top -= 1
        return stack[top + 1]
def push(element):
    global top, stack, stack_size
    if top + 1 >= stack_size:
        stack += [None]*stack_size
        stack_size *= 2
    top += 1
    stack[top] = element
def print_stack():
    global top, stack, stack_size
    for i in range(top + 1):
        print(stack[i], '', end='')
    print(" (size: " + str(stack_size) + ")")

print_stack()
for i in range(10):
    push(i)
print_stack()
for i in range(8):
    pop()
print_stack()

That is confusing code, right?

First of all, we use global variables. That makes the function calls hard to understand, as they have side effects.

This is made more confusing than necessary. It does use Python lists like an Array. That is not needed, but it is just to exemplify how difficult it is to make intuitive code if you model the world like a computer works.

Step 2: Using object oriented programming to solve the above (first step – the less bad, but still not good solution)

First time you are asked to create stack using an object oriented approach, you will probably do it in a non intuitive way.

Say, you think of a Stack like a object. The stack is the full object.

What does a stack consists of?

Well items which are piled on top of each other, and you can take the top off.

How could that be modeled?

Often the straight forward way from a classical thinking way into the a class.

class Stack:
    def __init__(self):
        self.stack_size = 8
        self.stack = [None]*self.stack_size
        self.top = -1 # empty stack
    def pop(self):
        if self.top == -1:
            return None
        else:
            self.top -= 1
            return self.stack[self.top + 1]
    def push(self, element):
        if self.top + 1 >= self.stack_size:
            self.stack += [None]*self.stack_size
            self.stack_size *= 2
        self.top += 1
        self.stack[self.top] = element
    def print_stack(self):
        for i in range(self.top + 1):
            print(self.stack[i], '', end='')
        print(" (size: " + str(self.stack_size) + ")")

s = Stack()
s.print_stack()
for i in range(10):
    s.push(i)
s.print_stack()
for i in range(8):
    s.pop()
s.print_stack()

If you inspect the code, it is actually the same code. Which in some ways has improved it.

  1. We do not have global variables anymore. They are tied to the Stack class.
  2. The function calls push and pop are also tied to the Stack class.
  3. Also, when we use the Stack, it is clear from the context, as it is tied to the variable s, in this case.

So what is wrong?

Well, it is still not simple to understand what happens in the code. It takes time to understand, even with this simple code.

The functions use variables like top and assigns it to -1 if the stack is empty. It requires you to investigate pop and the constructor to understand that.

The key is to keep it simple.

So how to do that?

Step 3: A simple way to model it

Let’s take a look at the drawing again.

A stack.

A stack actually consists of object on it. Hence, the stack is the abstraction that keeps objects in a specific order.

That said, we need to model that closer, as it will be easier to understand for the reader of the code.

The objects on the stack we will call Nodes.

What characterizes a Node? It lies either on the bottom or on top of another Node.

What characterizes a Stack? It knows the top of the stack and can push and pop Nodes.

How can that be turned into 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.top = None
    def push(self, element):
        self.top = Node(element, self.top)
    def pop(self):
        element = self.top.element
        self.top = self.top.next_node
        return element

s = Stack()
for i in range(20):
    s.push(i)
for i in range(10):
    print(s.pop(), '', end='')
print()

How is that code? Easier to understand?

Of course, normally a Stack would as a minimum have a helper function is_empty() to return if stack is empty. That can be added easily. You see how?

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

class Stack:
    def __init__(self):
        self.top = None
    def push(self, element):
        self.top = Node(element, self.top)
    def pop(self):
        element = self.top.element
        self.top = self.top.next_node
        return element
    def is_empty(self):
        return self.top == None

s = Stack()
for i in range(20):
    s.push(i)
while not s.is_empty():
    print(s.pop(), '', end='')
print()

Do you get the sense of it now?

Model the code as closely to the reality we humans understand. It makes the code easy to read and understand. Hence, easy to maintain.

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