Queue Data Structure: Practical Applications & Operations
Learn how queues are used in real applications and it’s implementation in Python and C++
Queue is one of the simplest and most useful data structure, not just in computer science, queues are relevant in our day to day life in lot of different fields.
In this post, we will discuss why queues are so important, how they are used in computer science and finally look at its implementation in Python and C++. The goal is to understand the queue pattern, and understand why they exist, this will hopefully help you appreciate queues and want to learn it.
Practical Applications
So what makes queues special ? A queue is a data structure that follows First In First Out — which means the first item to enter the queue is the first to leave the queue.
In computer science this pattern is useful when processes need to be executed in the order that they are created. It is also used to send messages to a receiver in the order that they were generated.
Queues are useful in the scenario where there is only a single resource, but multiple objects that want to use or access this resource. So a queue can be thought of like a waiting list, for a resource. This resource can be a processor, or maybe a service that executes a function, or it could even be a receiver for a message. Introducing this concept of a waiting list for a resource helps us create asynchronous systems, increasing processing speed and also ensures the resource is utilised efficiently.
As a software engineer, learning about queues is necessary, because I am sure that you will use it at some point in your career. Here are some of the common places where queues are used:
- Message Queues – A message queue is a general concept used for communication between processes. Basically a sender sends a message, and if the receiver cannot receive it immediately maybe because it is busy with something or offline, the message instead of dropping off, waits in some kind of a queue, and when the receiver is ready to receive it, the message is consumed or removed from the queue and sent to the receiver.
For example, when you send an email, it waits in a queue called the SMTP queue, until the receiver logs into their inbox. Same concept is applied when you send a message to someone who is not online on a social network. Your message waits in some kind of a queue on a server, and when the recipient comes online, it is sent to them. - Process Scheduling – All the processes running on your computer now, first wait in a queue called ready queue, waiting to be executed by your processor. There are various scheduling algorithms that decide which process should be executed next based on certain criteria like priority.
- Data Buffers – A buffer implements a queue and is typically used in communication when there is difference between the rate at which data is received and the rate at which it can be processed.
For example in video streaming applications, the video is streamed in bursts and stored in a buffer so that even if the network becomes slow for a while, the playback is not interrupted. Say for example the video is playing at 24fps, then the streaming app may store 240 frames in its buffer, so that it can continue playing for the next 10 seconds even if the network is interrupted. The buffer is also used for sequencing frames, ie, if frames come out of order, they are sorted in the buffer before being played. Buffers also used in disk drives, input/output devices and communication over networks. - It is also used in several algorithms like the Breadth First Search or BFS algorithm, and round robin algorithm.
Now that we understand the importance of queues, let’s look at the queue operations.
Queue Operations
There are four queue operations:
- Enqueue – adding an element to a queue is called enqueuing. The new element is usually added to the back of the queue. In the example, 10 is enqueued, and added to the queue.
- Dequeue – removing an element from a queue is call dequeue. On calling dequeue, the element from the front of the queue (more generally, the opposite end where enqueue was performed) is removed. In the example, 15 is at the front, and on dequeuing it is removed and the value is returned.
- Front – this function simply returns the value at the front of the queue. This will be the element that will be dequeued next.
- Back/Rear – this function returns the value at the back of the queue. This will be the element that was just added to the queue.
Implementing Queue
Here are common implementations of queue in Python and C++, especially useful if you are preparing for coding interviews.
Python
In python the inbuilt list data structure can be used to implement a queue.
C++
In C++, the STL (Standard Template Library) already has an implementation of queue.
The idea behind this post was simply to look at queues from a practical perspective and learn more about them. If you enjoyed this, I am planning to do a series on other data structures as well, so please consider following and check out my YouTube Channel.
For questions, comments, feedback feel free to email me at adarsh1021@gmail.com or connect with me on Twitter (@adarsh_menon_).
