Data Structures # 3 Steps to Understand and Implement a Queue in Python

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.

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.

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.

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.

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
```

Why learn Python? There are many reasons to learn Python, and that is the power…

3 days ago

What will you learn? How to use the modulo operator to check if a number…

1 week ago

There are a lot of Myths out there There are lot of Myths about being…

2 months ago

To be honest, I am not really a great programmer - that is not what…

2 months ago

What does it take to become a Data Scientist? Data Science is in a cross…

2 months ago

What will you learn? Need to setup a SQL server? You don’t need to install…

4 months ago