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).
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
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.