Coding a Queue Abstract Data Type using a Linked List in Python

In the previous tutorial I discussed how to code a Stack Abstract Data Type using a linked list as the underlying data structure. In this tutorial I will create a Queue Abstract Data Type using a linked list. The queue will implement the two most common operations of enqueue and dequeue to add and remove an item from the queue. Although a linked list will maintain the state of the queue, the software developer will not interact with the linked list directly. The details of the algorithm and data structures used to perform dequeue and enqueue are encapsulated by the custom Python Queue Class.

Node Class for Linked List

The Node Class used in the previous linked list tutorials is the same. Each Node holds an integer value and a pointer to the next Node in the linked list.

class Node(object):
    def __init__(self, value: int, next_node: "Node" = None):
        self.value = value
        self.next = next_node

    def __repr__(self):
        return "Node <{}>".format(self.value)

Queue Class

A queue is a First-In, First-Out (FIFO) abstract data type. The first value added to the queue will be the first value removed from the queue. My queue is implemented by a Queue Class and offers three common operations.

• enqueue - Adds new value to the Queue.
• dequeue - Retrieves and removes value from Queue.
• is_empty - Returns True if the Queue is empty, othewise False.

All these operations are performed in constant time, O(1).

Here is one solution to implementing a Queue abstract data type using Python.

class Queue(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value: int) -> None:
        new_node = Node(value)

        if self.head is None:
            self.head = new_node
            self.tail = self.head
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self) -> int:
        if self.head is None:
            raise EmptyQueueException("Dequeue from empty queue.")

        value = self.head.value
        self.head = self.head.next

        if self.head is None:
            self.tail = None

        return value

    def is_empty(self):
        return self.head is None

Unlike the Stack Abstract Data Type implmentation in Python which only uses a head pointer to the linked list, the Queue implementation contains both a head and tail pointer of the linked list. By maintaining a head and tail pointer in the linked list, we are able to guarantee that enqueue and dequeue are constant time O(1) operations. The head pointer is used during the dequeue operation, and the tail pointer is used during the enqueue operation.

Custom Python Exception

I created a custom Exception Class, called EmptyQueueException, that gets raised if you attempt to dequeue from an empty queue.

class EmptyQueueException(Exception):
    pass

Black Box Automated Tests

I added a Python script to test the functionality of the Queue Class. These are black box tests, since they test the interface and not the internals of the Queue Class.

if __name__ == '__main__':
    q = Queue()

    try:
        q.dequeue()
    except EmptyQueueException:
        pass

    max_range = 100

    for i in range(max_range):
        q.enqueue(i)

    i = 0
    while not q.is_empty():
        assert q.dequeue() == i
        i += 1

    try:
        q.dequeue()
    except EmptyQueueException:
        pass

Conclusion

As you can see, the linked list is a very handy data structure and can be used internally by both Stack and Queue Abstract Data Types. The linked list is often encapsulated by a custom class. The internal algorithm and data structures are hidden from the software developer, making it easier to refactor and completely change the internals without breaking the interface / API.