How to Implement a Stack in Python and Check the Run-time Performance

We will cover the following in this article

  • What is a Stack – a short introduction
  • How to implement a Stack in Python
  • Investigate the run-time performance

What is a Stack

A Stack is a useful concept that is used in daily life, and hence, a concept that is important to understand and master as a programmer.

To understand Stacks just think of a stack of plates. There are two main operations you can do. First, you can add a plate on top of the stack. That operation is called push adds the element on top of the stack. Second, you can remove the top plate of the stack. That operation is called pop, and returns the top element of the stack.

In the diagram below a Stack is pictured. It contains of a Stack of element on the left side. The operation push of the element 03 is executed and results is pictured on the right side. Notice, that the push operation puts the element on top of the stack.

Below the operation pop is executed. Notice, that the pop operation takes from the top of the stack.

Implementation of a Stack in Python

It is a good idea to have a helper class Node that represents the elements on the stack.

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

The actual functionality of the Stack is kept in a Stack class.

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

Now you can use your stack. Like the example below.

s = Stack()
for i in range(5):
    s.push(i)
while not s.is_empty():
    print(s.pop())

Will give the following output.

4
3
2
1
0

Notice the order of the element being removed from the stack by pop.

Run-time Performance

If we look at how the stack perform in order of the data size. To investigate the run-time performance the cProfile library is a good choice and simple to use. The following piece of code will help you investigate the performance.

import cProfile
def profile_stack(n):
    s = Stack()
    for i in range(n):
        s.push(i)
    while not s.is_empty():
        s.pop()

cProfile.run("profile_stack(100000)")

See the following graph.

As you see, the push and pop operations are constant, O(1), resulting in a linear performance of n push and pop operations as in the above experiment.

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.