## What will we cover in this tutorial?

We will cover what a **Queue** is. A **Queue** is a data structure used by computers. It resembles a *queue* as we know it.

The key things a **Queue** should have are efficient operations for insertion (**enqueue**) and removal (**dequeue**) of the queue. In this tutorial we will understand what a is, how to represent it, and how to implement the efficient operations.

## Step 1: Understand a Queue

A **Queue** is like a *queue* in real life.

A Queue is used in computer science in many scenarios. One scenario is when a resource is shared among multiple consumers, then a **Queue** is set in front.

This resembles the real world, where we use queues in the grocery store, pharmacy, you name it. In all stores, where we have more consumers than registers (the resource) to serve.

A Queue serves the principle, **First-in-first-out** or **FIFO**.

A simple diagram shows the operations of a **Queue**.

The above queue shows the direction of the **Queue** and the order they have been added symbolized with the numbers 1 to 8, where 8 is about to be added.

The operations on the **Queue** are as follows.

**enqueue**Adds an element to the back of the**Queue**.**dequeue**Removes the element of the front of the**Queue**.

Normally, a Queue would also have a function **is_empty**, which checks whether the **Queue** is empty.

## Step 2: How to represent a Queue item with an element

How do you represent the above items of the **Queue**?

Well, we need to be able to keep an order of the **Queue**. Let’s try to draw it and see what we can figure out.

Surprised? Well, the **Queue** goest from left to right, while the arrows between the items go from right to left.

Actually, the items of the **Queue** can be represented by a simple **Node** class.

class Node: def __init__(self, element=None, next_node=None): self.element = element self.next_node = next_node

This simple Node class has an **element** and the pointer to **next_node**. Hence, the **next_node** are the arrows in the diagram above. And the **element** are representing the numbers in the above diagram. Obviously, the element can contain anything.

## Step 3: Create a Queue class to represent the enqueue and dequeue operations

Let’s start in the simple.

The above suggest that if we have **head** and **tail** pointer, we can have what we need to implement a **Queue** data structure.

The enqueue function has the special case where the Queue is empty, otherwise it will do as follows.

**enqueue**Create a new**Node**with the element. Point**tail**s**next_node**at created**Node**. Then update**tail**to point at created**Node**.

Here we can implement it as follows.

class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, element): if self.head is None: self.head = self.tail = Node(element) else: node = Node(element) self.tail.next_node = node self.tail = node

The **dequeue** is a bit more involved.

**dequeue**Get the**element**from the**Node**that**head**points at. If**head****Node**and**tail****Node**is the same (that is if it is the last**Node**in the**Queue**), then point**tail**and**head**at**None**. Otherwise, set the**head**to point at the the**next_node****head**points at.

class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, element): if self.head is None: self.head = self.tail = Node(element) else: node = Node(element) self.tail.next_node = node self.tail = node def dequeue(self): element = self.head.element if self.tail == self.head: self.tail = self.head = None else: self.head = self.head.next_node return element

Notice that the **dequeue** does fail if the **Queue** is empty. This is dealt with by creating a **is_empty** function, which returns whether the **Queue** is empty.

class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, element): if self.head is None: self.head = self.tail = Node(element) else: node = Node(element) self.tail.next_node = node self.tail = node def dequeue(self): element = self.head.element if self.tail == self.head: self.tail = self.head = None else: self.head = self.head.next_node return element def is_empty(self): return self.head is None

That is it.

## The full code including a string representation to enable it to be printed

See the full code below. It also contains the **__str__(…) **function, witch enables it to be printed. Also, how to use it.

class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, element): if self.head is None: self.head = self.tail = Node(element) else: node = Node(element) self.tail.next_node = node self.tail = node def dequeue(self): element = self.head.element if self.tail == self.head: self.tail = self.head = None else: self.head = self.head.next_node return element def is_empty(self): return self.head is None def __str__(self): if self.head is None: return None node = self.head result = "[" while node is not None: result += str(node.element) + " " node = node.next_node return result[:-1] + "]" q = Queue() for i in range(10): q.enqueue(i) while not q.is_empty(): print(q.dequeue(), '', end='')

The above code will result in the following output.

[0 1 2 3 4 5 6 7 8 9] 0 1 2 3 4 5 6 7 8 9