In this article, we will learn about the Queue and its implementation in Python.
What is a Queue?
A Queue is a linear data structure that follows the First In/First Out(FIFO) principle. It’s opposite to the Stack data structure. We can compare the queue with a real-life queue at the cinema ticket counter. Let’s see the illustration of a queue as follows.
If you observe the queue at the counter, the second person can go to the counter only after the first person completes his/her work. Here the first person comes to the counter and then the second person. So, here people are following the FIFO(First In/First Out) principle. Whoever comes first, he/she will complete the work first. We can see a similar kind of queues in our day-to-day lives. The Queue data structure also follows the same principle. Now, you know what queues are and its principle. Let’s see the operations that can be performed on a queue data structure.
Operations in Queue
Similar to stack, we will find two main operations in a queue data structure.
enqueue(data)
Adds new data to the queue at the end. The side is called the rear.
dequeue()
Removes data from the front of the queue. The side is called the front. Let’s see the queue operations illustrations for better understanding. One picture speaks a thousand words.
We can write some helper functions to get more info about the queue. There is no limit on the number of helper functions you will have. Let’s stick to the most important once mentioned below for now.
rear()
Returns the first element from the end of the queue.
front()
Returns the first element from the start of the queue.
is_empty()
Returns whether the queue is empty or not.
Isn’t it boring for you? I mean the conceptual topics. For me Yes! But, we can’t do anything without knowing the concepts. We have to complete know it before the implementation. Don’t worry it’s time to make our hands dirty with some code. I assume you have python installed on your PC if not you can also try the online compiler.
Queue Implementation
Implementing a queue won’t take more than 15 mins for a programmer. Once you learned, you will say it. Maybe you can implement it within mins after this tutorial. There are multiple ways to implement the queue in Python. Let’s see different queue implementations step by step.
#1. List
The list is a built-in data type in Python. We are going to use the list data type to implement a queue in a class. We will walk you through different steps to implement the queue data structure from scratch without any modules. Let’s jump into it. Step1: Write a class called Queue. Step2: There has to be some variable to store the data of the queue in the class. Let’s name it elements. And it’s a list of course. Step3: To insert data into the queue, we need a method in the class. The method is called enqueue as we already discussed in the previous section of the tutorial. The method takes some data and adds it to the queue (elements). We can use the append method of the list data type to add data at the end of the queue. Step4: The queue needs to have an exit. And that’s called dequeue. I think you already guessed that we are going to use the pop method of the list data type. If you guessed or not, cheers! The pop method of the list data type deletes an element from the list of the given index. If we didn’t give any index, then it deletes the last element of the list. Here, we need to delete the first element of the list. So, we have to pass the index 0 to the pop method. That’s enough for a queue. But, we need the helper functions to test whether the queue operations are working properly or not. Let’s write the helper functions as well. Step5: The method rear() is used to get the last element of the queue. Negative indexing in list data type helps us to get the last element of the queue. Step6: The method front() is used to get the first element of the queue. We can get the first element of the queue using the list index. Step7: The method is_empty() is used to check whether the queue is empty or not. We can check for the length of the list. Phew! completed the implementation part of the queue data structure. We need to create an object for the Queue class to use. Let’s do it. Now, we have a Queue object. Let’s test it with some series of operations.
Check whether the queue is empty or not using the is_empty method. It should return True. Add the numbers 1, 2, 3, 4, 5 to the queue using the enqueue method. The is_empty method should return False. Check it. Print the front and rear elements using the front and rear methods respectively. Remove the element from the queue using the dequeue method. Check the front element. It should return the element 2. Now, remove all the elements from the queue. The is_empty method should return True. Check it.
I think that’s enough to test our queue implementation. Write the code for each step mentioned above to test the queue. Did you write the code? No, don’t worry. Check the code below. I think you run the above program. You can get an output similar to the following result. We can directly use the list data type as a queue data structure. The above implementation of the queue helps you better understand the queue implementation in other programming languages. You can also use the above class implementation of a queue in a different program of a project by simply creating the object as we do earlier. We have implemented the queue from scratch using the list data type. Are there any built-in modules for the queue? Yeah! we have built-in queue implementations. Let’s see them.
#2. deque from collections
It is implemented as a double-ended queue. Since it supports the addition and removal of elements from both ends, we can use it as a stack and queue. Let’s see the queue implementation using dequeue. It is implemented using other data structures called the doubly-linked list. So the performance of the insertion and deletion of elements are consistent. Accessing elements from the middle linked list took O(n) time. We can use it as a queue as there is no need to access the middle elements from the queue. Let’s check the different methods that the dequeue offers us.
append(data) – used to add the data to the queue popleft() – used to remove the first element from the queue
There are no alternative methods for the front, rear, and is_empty. We can print the whole queue in place of front and rear methods. Next, we can use the len method to check whether the queue is empty or not. We have followed a series of steps to test the queue implementation in the previous. Let’s follow the same series of steps here as well. You will get a result similar to the following output.
#3. Queue from queue
Python has a built-in module called queue that serves a class called Queue for the queue implementation. It’s similar to the one we have implemented before. First, let’ checkout different methods of the Queue class.
put(data) – adds or pushes the data to the queue get() – removes the first element from the queue and returns it empty() – returns whether the stack is empty or not qsize() – returns the length of the queue.
Let’s implement the queue with the above methods. Check the output of the above code. There are some other methods in the Queue class. You can explore them using the dir built-in function.
Conclusion
I hope you have learned about the queue data structure and its implementation. That’s it for the queue. You can use the queue in different places where there need to be processed in FIFO(First In/First Out) order. Use queue in problem-solving whenever you get the case to use it. Interested in mastering Python? Check out these learning resources. Happy Coding 🙂 👨💻
