Everything About Queue Data Structure in Python

[This article was first published on PyShark, and kindly contributed to python-bloggers]. (You can report issue about the content on this page here)
Want to share your content on python-bloggers? click here.

In this article we will focus on a complete walk through of a Python queue data structure.

Table of Contents


What is a queue

A queue is an array-like data structure that stores the items using the FIFO (First In First Out) approach.

You can think of a queue as a line up of people, where the first person in the line gets served first, and a new person joining the line is the last one:

What is a queue

As you can see, the people were added to queue in the following order: 1 -> 2 -> 3, where person 3 was added last.

Now, if we would like to serve person 3, we will need to serve person 1 first, then person 2, and then person 3, making it the following order order: 1 -> 2 -> 3.

The above examples show the methodology behind the FIFO principle: the first person added will be served first.


How to create a queue in Python

There are multiple ways of creating queues in Python:

In this tutorial we will use the simplest approach and create queues in Python using the list data structure.

Creating an empty queue is identical to creating a list in Python using square brackets [].

Let’s start with creating a new class and initializing it as an empty queue:

class Queue():
    
    
    def __init__(self):
        self.elements = []

Then we will create an empty queue and print in out:

queue = Queue()

print(queue.elements)

You should get:

[]

How to check if a queue is empty in Python

When working with queues, we often need to know whether they are empty as a requirement for some operations.

For example, when removing elements from a queue, we need to make sure that there are elements to remove (since we can’t remove elements from an empty queue).

Since our implementation of a queue data structure is based on Python list, we can simply check the length of the queue to determine whether it’s empty or not.

In this section we will implement a method check_empty() for checking whether there are elements in a queue for the Queue() class.

def check_empty(self):
    if len(self.elements)==0:
        return True
    else:
        return False

It will be added as a method of the Queue() class:

class Queue():
    
    
    def __init__(self):
        self.elements = []
    
    
    def check_empty(self):
        if len(self.elements)==0:
            return True
        else:
            return False

We can test it with an empty queue:

queue = Queue()

queue.check_empty()

And you should get:

True

How to add elements to a queue in Python

Once we have a queue, we can start adding elements to it.

This queue operation is referred to as enqueue into a queue.

Since our queue is created as a list, we can use the .append() method of Python list for adding elements.

In this section we will implement a method enqueue() for adding elements to a queue for the Queue() class.

def enqueue(self, data):
    self.elements.append(data)

It will be added as a method of the Queue() class:

class Queue():
    
    
    def __init__(self):
        self.elements = []
    
    
    def check_empty(self):
        if len(self.elements)==0:
            return True
        else:
            return False
    
    
    def enqueue(self, data):
        self.elements.append(data)

Let’s create the same queue as in example section and print out the elements of the queue:

queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.elements)

And you should get:

[1, 2, 3]
Add elements to queue in Python using enqueue()

How to remove elements from a queue in Python

Once we have a queue with elements, we may want to remove some of them from the queue.

Recall that queues use the FIFO (First In First Out) approach, meaning that we can only remove elements that are at the beginning of the queue at every iteration.

This queue operation is referred to as dequeue out of a queue.

Since our queue is created as a list, we can use the .pop() method of Python list for removing elements (and reference index 0 for the beginning of the queue).

In this section we will implement a method dequeue() for removing elements from a queue for the Queue() class.

def dequeue(self):
    if self.check_empty():
        raise IndexError('Index out of range, the queue is empty.')
    else:
        self.elements.pop(0)

It will be added as a method of the Queue() class:

class Queue():
    
    
    def __init__(self):
        self.elements = []
    
    
    def check_empty(self):
        if len(self.elements)==0:
            return True
        else:
            return False
    
    
    def enqueue(self, data):
        self.elements.append(data)

        
    def dequeue(self):
        if self.check_empty():
            raise IndexError('Index out of range, the queue is empty.')
        else:
            self.elements.pop(0)

Let’s test create the same queue as in previous section, then dequeue one element and print out the elements of the queue:

queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

queue.dequeue()

print(queue.elements)

And you should get:

[2, 3]
Remove elements from queue in Python using dequeue()

Conclusion

This article is an introductory walkthrough for queue data structure in Python and its functionality which is important to learn as they are used in many areas of programming and in machine learning.

Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Data Structures articles.

The post Everything About Queue Data Structure in Python appeared first on PyShark.

To leave a comment for the author, please follow the link and comment on their blog: PyShark.

Want to share your content on python-bloggers? click here.