# 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.tail = None

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

return

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

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

self.tail = None

return value

def is_empty(self):
``````

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.

Posted by David Hayden David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.