A queue in classic programming is a data structure (DS) used for storing and managing data in a specific order. In the real-world simulation, you can imagine a queue of people waiting for their order, and people who ordered it first will receive it first and vice-versa.
This concept is used widely for different reasons in programming and the most popular are those:
Task scheduling
In distributed computing, queues contain a list of tasks to be executed by a process (or several processes, also called workers). When a task is created, it is added to the end of the queue, and the task waits for a free worker to pick it up. Queues in task scheduling can be different, and they don’t always follow the FIFO principle. It can also be:
Priority queues (Each task has its priority, typically a plain number)
Delayed queues (Each task has its time of execution, for example, scheduled email letters)
Dead letter queues (Tasks that worker can’t process, remain for further investigation)
Real-time event processing (Message brokers)
Queues in event-driven architecture are used as a core component. It allows asynchronous communication between the components of the systems (producer and consumers). The producer adds a message to the broker’s queue, and then as soon as a consumer is available, it will pull messages out.
Any other system
That requires the creation of a real queue simulation, like a call center or online game lobby.
Interface
At the previous stage, we figured out where the queue is being used, and it would be cool to understand what contract this data structure has.
There are several common methods of this DS:
- enqueue
This core method is responsible for adding the item to the queue.
- dequeue
This method is responsible for pulling the element from the queue according to the principle that the queue follows.
- peek (front or rear)
This method allows us to view the item from the rear or front without pulling it out. This can be useful if we accidentally pull an item and our process that handles it falls, in which case a pulled item may be lost. This method solves that problem since it obliges us to confirm that we have already processed the desired task.
- is_empty
This method allows you to check if the queue is empty and it’s useful for handling edge cases like when there are no items to pull.
Implementation
Knowing this information, we can start writing our implementation of this data structure. The easiest way to implement this will be through another data structure, an array. To implement this, I will use Elixir, a dynamic, functional programming language that has absorbed the best programming patterns, and I like it a lot.
Elixir has a great module called GenServer, it allows you to use isolated processes with unified behavior and also provides the ability to store state and execute code asynchronously. Let’s look at all this with a code snippet:
In this screenshot, you can see the client-side implementation of GenServer module, which is responsible for the public interface of our queue which we mentioned before. Let’s go through the code line-by-line:
Line 2 — We use the GenServer behavior which allows us to create an independent process in the Elixir and store the state. init_arg in this case will be passed from the GenServer.start_link/3 function, and it will be an array from the client side or an empty array by default.
Line 8— This function is responsible for starting a separate process, which will hold our queue with a process identifier.
Line 14— Here you can see the presence of all the necessary methods that a public queue interface should have (queue, dequeue, peek, is_empty). These functions will call methods on the server and return the updated result from them.
On the server side, we have all the dirty work, namely how the queue works:
Line 43 — Here you can see how the client call of the enqueue method calls this callback, which in turn operates by adding the necessary element (the usual push to the end of the array).
Line 48 — The dequeue callback checks if the queue is empty, because if it is, the requested item cannot be pulled. If the queue is empty, we return the tuple with an error and a message about the empty queue {:error, :empty}.
Line 58 and 67 — The same as with dequeue, we pull an element by index and make an additional check for array emptiness, so that there would be no runtime error when pulling elements.
Line 72 — Server callback which is responsible for checking the queue for emptiness, the callback calls a private method is_empty that is not available in the public interface.
Result
We’ve implemented our queue using Elixir, which follows the FIFO principle. Let’s take a look at how it works:
Conclusion
Today we learned what a queue is as a data structure in programming, where it is most often used, and how to implement its basic array-based version using Elixir GenServer. In the next article, we will create a library that can enqueue tasks into queues, persist them in the database with Redis, and process those tasks with workers. Thanks for reading and see you soon!
Top comments (0)