Implementing The Queue Data Structure.

This is the second article in the series. As the title suggests, we’re going to implement the Queue Data Structure in Python.

Photo by Clint Adair on Unsplash

class ArrayQueue:
    DEFAULT_CAPACITY = 10
    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

Internally the Queue class maintains the following three instance variables:

1. _data — is a reference to the list instance with a fixed capacity.
2. _size — is an integer representing the current size of the queue.
3. _front — is an integer representing the index within _data of the first element of the queue.

We initially reserve a list of moderate size for storing data, although the queue formally has a size of zero. As a technicality, we initialize the _front index to zero.

class Empty(Exception):
    """ Error accessing an element from an empty container"""
    pass

When front or dequeue is called within no elements in the queue, we raise an instance of the Empty exception.

Let us first have a look at the supporting methods of the queue.

def __len__(self):
    return self._size
def is_empty(self):
    return self._size == 0
def first(self):
    if self.is_empty():
        raise Empty('Queue is empty')
    return self._data[self._front]

I have discussed the theory of these methods in my previous article.

def dequeue(self):
    if self.is_empty():
        raise Empty('The Queue is empty')
    answer = self._data[self._front]
    self._data[self._front] = None
    self._front = (self._front + 1) % len(self._data)
    self._size -= 1
    return answer
def enqueue(self, e):
   if self._size == len(self._data):
        self._resize(2 * len(self._data))
   avail = (self._front + self._size) % len(self._data)
   self._data[avail] = e
   self._size += 1

The goal of the enqueue method is to add a new element to the back of the queue. We need to determine the proper index at which to place the new element. Although we do not explicitly maintain an instance variable for the back, we compute the location of the next opening using the formula:

avail = (self._front + self._size) % (len(self._data))

When the dequeue method is called, the current value of self._front designates the index of the value that is to be removed and returned. We keep a local reference to the element that will be returned, setting answer = self._data[self._front] just prior to removing the reference to that object from the list, with the assignment self._data[self._front] = None.
Our reason for the assignment of None relates to Python’s mechanism for reclaiming unused space.

def _resize(self, cap):
    old = self._data
    self._data = [None] * cap
    walk = self._front
    for k in range(self._size):
        self._data[k] = old[walk]
        walk = (1 + walk) % len(old)
    self._front = 0

When enqueue is called at a time when the size of the queue equals the length of the list, we rely on a standard technique of doubling the size of the queue. For more details, you can see my article on Dynamic Arrays.

In the implementation of the Queue, more care needs to be taken for the _resize method. After creating a temporary reference to the old list of values, we need to allocate a new list that is twice the size and copy references from the old list to new. While transferring the contents we intentionally realign the front of the queue with index 0 in the new array as shown in the figure.

Resizing the queue, while realigning the front element with index 0

The realignment is not purely cosmetic. Since the modular arithmetic depends on the size of the array, our state would be flawed had transferred each element to its same index in the array.