Data Structures

# 3 Steps to Understand and Implement a Queue in Python

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

def enqueue(self, 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.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
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.tail = None

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
return element

def is_empty(self):
```

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

def enqueue(self, element):
else:
node = Node(element)
self.tail.next_node = node
self.tail = node

def dequeue(self):
else:
return element

def is_empty(self):

def __str__(self):
return None
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
```

Rune

Share
Rune

## Learn Python FREE Online

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

3 days ago

## How to Check if a Number is Even or Odd with Python

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

1 week ago

## The Truth About Being a Python Software Contractor

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

2 months ago

## Do This and 10X Your Salary as a Software Engineer

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

2 months ago

## Ultimate Guide to the Data Science Career Path

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

2 months ago

## How to Setup a MySQL Server in Docker for Your Python Project

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

4 months ago