Data structures, a simple queue in Python

on , , , 3 minutes reading

I found a simple way to understand algorithms and data structures is just to take a look at the pseudocode and implement it in a language, I usually do that exercise with a few different languages and I had been studying data structures and algorithms for a few weeks, so as I reminder to myself I decided to publish a few of those in my blog so I don’t forget :D

The abstract data structure queue can be implemented in two simple ways:

  • Using a vector (array), this will involve growing and shrinking the vector or implementing a circular queue (I will explore this later -maybe-)
  • Using a linked list (another data structure!)

In both cases we will need a way to point to the head and the tail of the queue, because, well, queues are FIFO structures and we are only allowed to add elements to the tail (back) and remove them from the head (front).

Simple fifo queue

In code this looks a lot simpler, I will use Python’s list to simplify the operation (notice I am using Python’s typing support and Python’s dataclasses):

from typing import Generic, List
from dataclasses import dataclass, field

T = TypeVar('T')

@dataclass
class Queue(Generic[T]):
    elems: List[T] = field(default_factory=list)

    def enqueue(self, elem: T) -> None:
        self.elems.append(elem)

    def dequeue(self) -> T:
        assert self.elems, "Queue is empty"
        return self.elems.pop(0)

    @property
    def isEmpty(self) -> bool:
        return len(self.elems) == 0

    def peek(self) -> T:
        assert self.elems, "Queue is empty"
        return self.elems[0]

see? nothing fancy. A simple test for our queue would look like this:

import unittest

class TestSimpleQueue(unittest.TestCase):
    def setUp(self):
        self.queue = Queue()

    def test_empty_queue(self):
        self.assertTrue(self.queue.isEmpty)

    def test_queue_is_not_empty(self):
        self.queue.enqueue(1)
        self.assertFalse(self.queue.isEmpty)

    def test_queue_can_dequeue(self):
        self.queue.enqueue(1)
        self.queue.enqueue(2)
        self.assertEquals(self.queue.dequeue(), 1)
        self.assertEquals(self.queue.dequeue(), 2)
        self.assertTrue(self.queue.isEmpty)

    def test_queue_can_peek(self):
        self.queue.enqueue(1)
        self.assertEquals(self.queue.peek(), 1)
        self.assertFalse(self.queue.isEmpty)
        self.assertEquals(self.queue.dequeue(), 1)
        self.assertTrue(self.queue.isEmpty)

    def test_dequeue_or_peek_fails_if_empty(self):
        with self.assertRaisesRegex(AssertError, 'Queue is empty'):
            self.queue.dequeue()
        with self.assertRaisesRegex(AssertError, 'Queue is empty'):
            self.queue.peek()

I won’t recommend to implement your own queue in Python at least that you know why and what are you doing it. Python already has a not one but many general and specialized queue classes living in the queue package in the standard library, in fact, it offers asynchronous specialized queues as well in the asyncio package, use those.