Stack and Queues in Python

 Background

In the last few posts, we saw how to work with classes in Python and how it can be used in an object-oriented way. In this post, I will explain how you use a stack and queue implementation in Python. This is needed if you are doing problem-solving questions using Python or in general using Python for coding.

Remember:

• Stack:  "Last in First out"
• Queue:  "First in First out"

Using stack in Python 

Stack works on logic "Last in First out".Stack is pretty straightforward. You can use a standard Python list as your stack. See below the Python code

stack = []
stack.append("Aniket")
stack.append("Abhijit")
stack.append("Awantika")
print(stack)
print("Pushing Anvi to Stack")
stack.append("Anvi")
print(stack)
print(f"Popped {stack.pop()}")
print(stack)
print(f"Popped {stack.pop()}")
print(stack)

This prints the following:

['Aniket', 'Abhijit', 'Awantika']
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Anvi
['Aniket', 'Abhijit', 'Awantika']
Popped Awantika
['Aniket', 'Abhijit']

As you can see initial values in the stack were "Aniket", "Abhijit" & "Awantika". Then we pushed "Anvi" to the stack. Then we popped which gave us "Anvi", then we popped again and we got "Awantika". Remember stack is "Last in First out" and the above behavior is in line with it.

NOTE: The list works better at the end of the list, so append and pop operations happen in O(1) time complexity. So if you need a stack implementation go ahead and use a list. You could also use dequeue implementation for a stack with the same O(1) complexity - It has append and pop methods similar to queue. (That's not the case for the queue - see below).

Using Queue in Python

The queue is "First in First out". You could use list implementation in Python for queue as well but remember the note from above - The list works better at the end of the list. It does not work well with the start of the list, so if you try to remove the element from the beginning of the list, the list needs to be shifted back one place making the time complexity O(N).

You should use dequeue implementation from the collections module for O(1) push/pop operations in the queue. I will show both use cases below. 

Using a list for queue implementation (Not recommended)

See below the Python code:

queue = []
queue.append("Aniket")
queue.append("Abhijit")
queue.append("Awantika")
print(queue)
print("Pushing Anvi to Queue")
queue.append("Anvi")
print(queue)
print(f"Popped {queue.pop(0)}")
print(queue)
print(f"Popped {queue.pop(0)}")
print(queue)

The output in this case is:

['Aniket', 'Abhijit', 'Awantika']
Pushing Anvi to Queue
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Aniket
['Abhijit', 'Awantika', 'Anvi']
Popped Abhijit
['Awantika', 'Anvi']

As you can see this time it popped "Aniket" & "Abhijit" which are first in the list (Remember - "First in First out").

Using dequeue for queue implementation (recommended)

A deque is a generalization of the stack and a queue (It is short for "double-ended queue"). Deques support thread-safe, memory-efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction. (See documentation for more details)

NOTE: Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

See below the Python code:

from collections import  deque

queue = deque([])
queue.append("Aniket")
queue.append("Abhijit")
queue.append("Awantika")
print(queue)
print("Pushing Anvi to Queue")
queue.append("Anvi")
print(queue)
print(f"Popped {queue.popleft()}")
print(queue)
print(f"Popped {queue.popleft()}")
print(queue)

Output is the same as that of above (as using list for queue) but internally the operation is O(1) in case of dequeue unlike O(N) in case of list.

['Aniket', 'Abhijit', 'Awantika']
Pushing Anvi to Queue
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Aniket
['Abhijit', 'Awantika', 'Anvi']
Popped Abhijit
['Awantika', 'Anvi']

Add in the comments if you have any questions.

Related Links

• Working with classes in Python (OSFG)
• Static methods vs class methods in Python (OSFG)
• Decorators in Python (OSFG)
• Python dequeue official documentation

Static methods vs class methods in Python

 Background

In the last post, we saw how to work with classes in Python. We saw private methods, instance variables, class variables, etc. In this post, we are going to explore static and class methods in Python. If you are from a Java background you would use class methods or static methods interchangeably but that is not the case with Python. 

Class methods in Python

• Class methods are your methods that are at class level (they belong to the class & not individual instances).
• They will get the reference to the class as the implicit first argument (similar to how instance methods get a reference to self)
• Class methods have access to class variables /state and can modify them

Consider the following  example:

class Employee:

    BASE_INCOME = 10000

    def __init__(self, name :str) -> None:
        self.name = name

    @classmethod
    def get_base_income_with_cls_method(cls) -> int:
        return cls.BASE_INCOME

    @classmethod
    def set_base_income_with_cls_method(cls, income: int) -> None:
        cls.BASE_INCOME = income


e = Employee("Aniket")
print(Employee.BASE_INCOME)
print(Employee.get_base_income_with_cls_method())
print(e.get_base_income_with_cls_method())
Employee.set_base_income_with_cls_method(100)
print(Employee.BASE_INCOME)
print(e.get_base_income_with_cls_method())
e.set_base_income_with_cls_method(10)
print(Employee.BASE_INCOME)
print(e.get_base_income_with_cls_method())

It prints:

10000

10000

10000

100

100

10

10

Notice

• You declare a method as a class method using @classmethod decorator
• The class method automatically gets an implicit argument cls which is a reference to the class.
• BASE_INCOME is defined outside __init__ and hence is a class variable.
• We have defined two class methods get_base_income_with_cls_method and set_base_income_with_cls_method which get and set that class variable (You actually do not need this and can do it directly with class reference E.g., Employee.BASE_INCOME=X etc. but have added to show how the class method has access to class variables via cls - 1st implicit argument).
• Changes made to the state by class methods are reflected across all instances of the class.

This is what you would know as a static method in Java.

Now let's see what a static method in Python looks like:

Static methods in Python

• A static method does not get an implicit first argument (as class methods did). 
• Similar to class methods a static method is also bound to the class (and not the object of the class) however this method can’t access or modify the class state. 
• It is simply present in a class because it makes sense for the method to be present in class (rather than at individual instance level, for eg., some utility methods).
• You can create a static method using @staticmethod decorator.

Consider the following example:

class Employee:

    def __init__(self, name: str) -> None:
        self.name = name

    @staticmethod
    def is_same_name(name1: str, name2: str) -> bool:
        return name1 == name2


print(Employee.is_same_name("Aniket", "Abhijit"))
print(Employee.is_same_name("Aniket", "Aniket"))

It prints:

False

True

As you can see these can be used for simple utility methods.

When to use class methods and static methods?

• Class methods are generally used to create factory methods. Factory methods return class objects depending on the usecase.
• Static methods are generally used to create utility functions.

Related Links

• Working with classes in Python (OSFG)

Working with classes in Python

 Background

In the last few posts, we saw how Python works, what are closures, decorators, etc. In this post, I am going to explain how to write a class in Python and work with it. As you might already be aware though Python is used as a scripting language we can use it as an Object-oriented programming language.

Writing classes in Python

Let's start with a simple class and how to use it.

class Employee:
    def __init__(self, name: str, age: int) -> None:
        self.name = name
        self.age = age

    def __str__(self) -> str:
        return f"Employee with name {self.name} and age {self.age}"

e = Employee("Aniket", 32)
print(e)

The above code prints: Employee with name Aniket and age 32

Let's try to understand what the above code does.

• First, we have defined a simple class Employee using a keyword class
• Then we have defined two magic methods (We will see what magic methods are later, for now just imagine these are special methods that are created for some specific intended functionality, wherever you see a method starting with double underscores you know it is a magic method)
• __init__ : __init__() method in Python is used to initialize objects of a class. It is also called a constructor. 
• __str__: The __str__() method returns a human-readable, or informal, string representation of an object. This method is called by the built-in print() , str() , and format() functions. If you don't define a __str__() method for a class, then the built-in object implementation calls the __repr__() method instead.
• Notice how the constructor takes 3 arguments
• self: Every method of a class that is an instance method (& not a class/static method - more on this later) will always have self as 1st argument. It is a reference to the instance created itself (e instance in the case of above).
• name & age: These are 2 new parameters that init takes which means when we want to create an instance of Emploee we need to pass name and age. These are our class instance variables.
• Also, notice how we have provided hints for the type of arguments (E.g., the name being of str type) and return type of method (-> None). These are optional but good to have. These are called annotations and are used only as hints (Nothing is actually enforced at run time)
• Lastly, we have just created an instance of Employee and printed it. Notice unlike Java you don't need to use a new keyword here. Since we defined our own implementation of __str__ it printed the same when we printed the object (Else it would have printed something like <__main__.Employee object at 0x000001CB20653050>).

Class variables and private methods

• Unlike Java, we do not define the type of variables (It's dynamic). 
• If you have declared variables inside __init__ using self then those are instance variables (specific to the instance you created).
• If you declare variables outside __init__ then those belong to the class (are called class variables) and can be accessed as ClassName.variable.
• Similarly, there are no access modifiers like Java
• If you want a method or variable to be private just start it with a single underscore. 
• E.g., _MY_PRIVATE_ID = "ABC"
• Please note this is more of a convention and nothing is enforced at run time (similar to the hints annotations I explained above). If you see such variables/methods then you should use caution before you use them as public variables/methods.

Let's look at an example to understand class variables and private methods.

class Employee:
    _BASE_INCOME = 10000

    def __init__(self, name: str, age: int) -> None:
        self.name = name
        self.age = age
        self.income = None

    def _calculate_income(self) -> int:
        return Employee._BASE_INCOME * self.age

    def get_income(self) -> int:
        return self._calculate_income()


e = Employee("Aniket", 32)
print(Employee._BASE_INCOME)
print(e._BASE_INCOME)
print(e.get_income())
print(e._calculate_income())

Above prints:
10000
10000
320000
320000

A couple of points to note here

• _BASE_INCOME since it is defined outside __init__ is a class variable. It can be accessed using class - Employee._BASE_INCOME. As you can see this starts with an underscore and is a private variable.
• _calculate_income is a private method defined to calculate income based on _BASE_INCOME and age. There is a public method get_inome exposed that uses the private method to compute the actual income.
• As you can see even though both variables and methods mentioned above are private you can access them. That is because as I mentioned before python does not enforce these, it's the developers' responsibility to use these with caution.

Now the natural question is how do we add validations to ensure that the instance variables are of the correct type. Let's see that next.

Using Properties

If you have worked on Java before you know that you can have getters and setter for instance variables. In Python, you can do the same using properties. See the below code for example:

class Employee:
    _MAX_AGE = 150

    def __init__(self, age: int) -> None:
        self._age = None
        self.age = age

    @property
    def age(self) -> int:
        return self._age

    @age.setter
    def age(self, value: int) -> None:
        if value > Employee._MAX_AGE:
            raise ValueError(f"Age cannot be more that {Employee._MAX_AGE}, Passed: {value}")
        self._age = value


e = Employee(200)

This prints:

Traceback (most recent call last):
...
  File "C:\Users\Computer\Documents\python\test.py", line 15, in age
    raise ValueError(f"Age cannot be more that {Employee._MAX_AGE}, Passed: {value}")
ValueError: Age cannot be more that 150, Passed: 200

Process finished with exit code 1

Notice

• How we are using a corresponding private variable(_name) to track the actual value stored internally and using the name as an interface to be used publically.
• When you try to create an Employee instance by passing age as 200 it actually calls the setter method which checks it is more than 200 and throws a ValueError.

Lastly, let's see a compact way to write the classes using dataclass decorator.

Using the dataclass decorator

You can use the dataclass decorator to write a class compactly. See the following example.

from dataclasses import dataclass, field


@dataclass
class Employee:
    name: str
    age: int
    BASE_INCOME: int = field(init=False, repr=False)


e = Employee("Aniket", 33)
print(e)

Above prints: Employee(name='Aniket', age=33)

Note here

• Notice the import of dataclass
• Once you decorate your class with @dataclass you get a few things for free
• It automatically creates instance variables with variables defined with annotation (name and age in the above case)
• You do not need to define an __init__ method for this.
• If you do not provide annotation hints then it automatically considers it as class variables.
• If you want to use hints annotations and still want it to be a class variable then you can initialize it with the field method by passing init and repr arguments as False. Eg., in the above case BASE_INCOME is not a class variable and will not be used in init or repr mafic methods.

Related Links

• Installing Python & related tools on Windows (OSFG)
• How Python works? (OSFG)
• Decorators in Python (OSFG)
• Understanding Python closures (OSFG)