The queue is an ordered list in which insertions are done at one end — Front and deletions are done at another end — Rear.
With this 3rd article in — Data Structures & Algo series, you will learn what a queue is. Also, you will find implementation of queue in the most sought after programming language Python.
Let’s begin with a general definition of Queue.
What Is A Queue?
Just like any other data structure, a Queue is used for storing data. The unique thing about a Queue is that it follows the rule — First In First Out, also known as a FIFO data structure.
For example, a Queue data structure is like standing in a queue for getting Covid-19 vaccination. When we enter the line, we stand at the end, while the first person in the line gets the vaccine shot and then second, and so on. As this happens, the person who got the vaccine shot will exit the line and the next will be at the head of the line.
This behaviour of a Queue is very useful in cases where order of arrival is important.
Another example can be a message queue where the messages are always delivered in the order they were received.
Comment if you have gotten your vaccine shot;).
Operations On A Queue
Let’s understand the insertion and removal of items from a queue below -
Queue shown below demonstrates the two major operations that can be performed on a queue —
Two major operations are — Enqueue and Dequeue.
As mentioned earlier, all the enqueue operations are done at one end called — Front and Dequeue operations are done at another end called — Rear. Let us now see what are the different kinds of operations that can be performed on a queue-
- enqueue() — Inserts data in queue
- dequeue() — Removes data from the queue
- front() — Returns the item at the front without removing it.
- size() — Returns the size of a queue
- isEmpty() — Returns true if queue is empty
- isFull() — Returns true if queue is full
Time complexity of all the operations on a queue is O(1).
We will shortly see a full implementation of all 6 operations on a queue.
Queue can be implemented in various ways, but we will cover the following ways for implementing it in Python -
- Using List — 
- Using Inbuilt Python Module — queue
Implementing Queue Using List
We will implement a queue using python List with an Object Oriented approach that you will not find anywhere and is highly recommended way of creating a queue if using a python List.
We will create a class called Queue that will have attributes and functions that can be performed on its object.
Here is the code -
In the above class, the queue is initialized as an empty python list. Also, it takes the max_size as one additional parameters that will specify the maximum number of items a queue can hold.
Queue class consists of all the basic operations that you can perform on the object created using this class, with proper exception handling on the operation level itself. For example -
If a queue is empty and if we try to perform a dequeue() operation, the above implementation will throw an exception saying —
File "Queue\Queue\python_queue.py", line 30, in dequeue
raise Exception('Underflow Error: Queue is empty!')
Exception: Underflow Error: Queue is empty!
Similarly, if a queue is full and if we try to add more items to it —
File "Queue\Queue\python_queue.py", line 17, in dequeue
raise Exception('Overflow Error: Queue is full!')
Exception: Overflow Error: Queue is full!
Now let us perform some of these operations on a queue below -
The output that will be generated is shown below —
List Items ::
Size of Queue :: 5
====== Remove Operation =====
List Items After Dequeue Operation ::
Size of Queue After Dequeue Operation :: 3
As already discussed in 2nd article of Data Structures & Algo series, most software developers use Lists as their primary queue implementation. But there are few problems with this implementation.
In a Python List, items are stored in contiguous memory locations, which means if the List grows, the time to add an item at the end of the list will take longer. List was made for one sole purpose and that was to have constant time when accessing any data within a List.
You can read more about the disadvantages in this article — Implementing Stack In Python.
Now, how do we avoid this problem? Pythons' queue module provides a better way to implement Queue.
Implementing A Queue Using Inbuilt Python Module — queue
There are many inbuilt ways to implement a queue in Python. One of them is using the queue.Queue. This is the simplest and more efficient of implementing a queue in python.
queue is built-in module of Python which is used to implement a queue. queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A max size of zero ‘0’ means a infinite queue. This Queue follows FIFO rule.
Let us see it in the code below -
All the Queue Operations discussed above can be performed on this queue as well. This implementation of queue is especially useful in threaded programming when information must be exchanged safely between multiple threads.
You can read more about this module on official python docs — queue
Practical Use Cases Of Queue
Below listed are few practical implementations of a queue-
- CPU scheduling, Disk Scheduling
- When data is transferred asynchronously between two processes.The queue is used for synchronization.
- Handling of interrupts in real-time systems.
- Call Center phone systems use Queues to hold people calling them in order.
More About The Author
I am a full-time software engineer with 4+ years of experience in Python, AWS, and many more technologies. I have started writing recently as it helps me to read more. I am looking forward to sharing technical knowledge and my life experiences with people out there.