This content originally appeared on DEV Community and was authored by Raul Melo
When we talk about queue as a data structure, it's exactly the same as you can imagine in real-world examples: a lot of things a line one in front of the other, waiting for something, like the imagine hero shows.
In this post, we're gonna talk about the basic implementation of a queue (like a supermarket queue), a priority queue (like a hospital queue), and also a circular queue (like a list of things you have to do repetitively).
Basic Queue
The basic queue will give us the base for the other queues. Here, we need to implement a mechanism called FIFO (First In, First Out), which means the first element added will be the first to be removed.
To start, let's see the API interface we need to implement that:
-
enqueue(element)- add new element(s) to the queue; -
dequeue()- remove first element from the queue; -
front()- returns the first element from the queue (for checking purposes); -
isEmpty()- returns if the queue is empty or not; -
size()- returns how many elements the queue contains.
Keep in mind that the API might differ from different languages which have Queue native or other implementations, but the principles are the same.
There are many ways of creating this structure, some people would straight use JS class but personally, I like to use the factory approach.
So let's create a factory function with a placeholder for all those methods:
function QueueFactory() {
const items = [];
return {
enqueue,
dequeue,
front,
isEmpty,
size,
};
function enqueue() {}
function dequeue() {}
function front() {}
function isEmpty() {}
function size() {}
}
.enqueue(element)
This method will simple take an element as argument and add to the end of the list:
function enqueue(element) {
items.push(element)
}
.dequeue()
Dequeue will remove the first element of our items and return it. We can simple use Array.prototype.shift for that task:
function dequeue() {
return items.shift();
}
Friendly reminder that shift mutates
itemsarray.
.front()
This method will only return for visibility purposes the first element of the list:
function front() {
return items[0];
}
.isEmpty()
As the name says, this method will check if our queue is empty or not:
function isEmpty() {
return items.length === 0;
}
.size()
This will simply return the length of our list:
function size() {
return items.length;
}
(Optional) .print() / .queue()
It's important that we don't expose our queue as part of the public interface because the whole idea is having a custom implementation for arrays.
Also, arrays are mutable, which means that if the user (we or other devs) push has access to the reference, new elements could be pushed or removed.
So if you want to provide a method to check the entire list, you could return a copy of this list:
function queue() {
return [...items];
}
Or maybe a method which prints the list:
function print() {
console.log(items.toString());
// or console.log(JSON.stringify(items))
}
Final result
function QueueFactory() {
const items = [];
return {
enqueue,
dequeue,
front,
isEmpty,
size,
print
};
function enqueue(element) {
items.push(element);
}
function dequeue() {
return items.shift();
}
function front() {
return items[0];
}
function isEmpty() {
return items.length === 0;
}
function size() {
return items.length;
}
function print() {
console.log(items.toString());
}
}
const myQueue = QueueFactory();
myQueue.enqueue(3);
myQueue.enqueue(2);
myQueue.enqueue(6);
console.log(myQueue.front()); // 3
myQueue.print(); // 3,2,6
console.log(myQueue.dequeue()); // 3
myQueue.print(); // 2,6
Priority Queue
In some cases, only the basic queue isn't enough. We need that behavior but we also want to take into account priorities, like a hospital emergency queue where the worst case has the highest priority no matter when it arrives first.
The good news is that from our previous implementation, only a few changes will be necessary.
Internal data structure
Before we were simply pushing the element we received from our enqueue method into a list.
Now, to keep tracking which element has higher or lower priority we might want to have an internal structure, a simple object where we simply hold the element and the priority:
function createQueueElement(element, priority) {
return {
element,
priority,
};
}
Now, iniside the enqueue method, we have to also accept a priority, so we create our element with our internal structure:
function enqueue(element, priority) {
const newEl = createQueueElement(element, priority);
items.push(newEl)
}
Nothing has changed until here, only our internal data structure.
Priority
To take into account where to add the element we'll need to loop over all items and check if the current element has higher priority than the one we're trying to add.
Don't forget that when the element we're comparing has the same priority as the one we're trying to add, the new one should be added after it (respecting FIFO):
// q.enqueue('Martin', 1);
{element: 'Karen', priority: 1}
{element: 'Caroline', priority: 1}
<- Martin should be added here
{element: 'John', priority: 2}
Since we need the index of the iteration to insert an element in between a list, let's use a simple for loop:
function enqueue(element, priority) {
const newElement = createQueueElement(element, priority);
let added = false;
for (let index = 0; index < items.length; index++) {
const currentElement = items[index];
if (newElement.priority < currentElement.priority) {
items.splice(index, 0, newElement);
added = true;
break; // We don't need to keep running the loop
}
}
if (!added) {
items.push(newElement);
}
}
Summarizing the operation:
- We create a controller variable "added" for the cases where our loop condition is not satisfied (like empty list or first element with that priority);
- We loop over all elements in the queue;
- If the current element has greater priority than our new element, we set our new element in the current element position using the method
Array.prototype.splice; - We set our controller variable to true and break the loop because the operation that matters was completed;
- If was not added because was the first element, for example, we just add the element with
.push()
.print()
Our previous print method was simple and good enough because we had an array of strings.
Now we have some structure, might be good to enhance the code to better visualize all elements with their priorities.
function print() {
for(const item of items){
console.log(`element: ${item.element} - priority: ${item.priority}`)
}
}
Final Result
function PriorityQueueFactory() {
const items = [];
return {
enqueue,
dequeue,
front,
isEmpty,
size,
print,
};
function createQueueElement(element, priority) {
return {
element,
priority,
};
}
function enqueue(element, priority) {
const newElement = createQueueElement(element, priority);
let added = false;
for (let index = 0; index < items.length; index++) {
const currentElement = items[index];
if (newElement.priority < currentElement.priority) {
items.splice(index, 0, newElement);
added = true;
break;
}
}
if (!added) {
items.push(newElement);
}
}
function dequeue() {
return items.shift();
}
function front() {
return items[0];
}
function isEmpty() {
return items.length === 0;
}
function size() {
return items.length;
}
function print() {
for(const item of items){
console.log(`element: ${item.element} - priority: ${item.priority}`)
}
}
}
var q = PriorityQueueFactory();
q.enqueue('John', 2);
q.enqueue('Olivia', 1);
q.enqueue('Karmen', 3);
q.enqueue('Oliver', 1);
q.print(); /*
element: Olivia - priority: 1
element: Oliver - priority: 1
element: John - priority: 2
element: Karmen - priority: 3
*/
Since the logic from this method is pretty much the same as the basic Queue, we could break it in a way of using either function composition (my preferred way) or class inheritance but for the sake of the tutorial let's focus on the data structure implementation itself.
Circular Queue
Unfortunately, we don't have as many applications for circular queues as we have for the others, but it's still important to know we have this concept.
A circular queue has the same principles as the regular queue. The only difference is that when it achieves the end of the queue, it returns for the first element and starts over again.
In that sense, we'll need to change our implementation a bit because we can't simply remove elements from the queue but we need to keep them somewhere else.
Usage example
Let's imagine we've created a small application that has a list of tasks to do every 3 hours.
We're going to run this list of tasks till the end and after 3 hours, it'll start over again.
I know we could simply run a function which has these tasks inside and every time has these new 3 elements, but help me here in the exercise ?
To do that, let's create something on top of our already existing basic queue.
The first step is creating a factory function that adds a queue into its closure and returns an object (API interfaces later)
function SchedulerFactory() {
const queue = QueueFactory();
return {};
}
We'll then create 3 methods for this data structure:
-
.add(element): will add a new task; -
.pick(): will return the next task to be executed; -
.size(): will return how many tasks it has.
.add(element)
Adding a new task will be very straight forward, we'll just enqueue the task:
function SchedulerFactory() {
const q = QueueFactory();
return {
add
};
function add(task){
q.enqueue(task)
}
}
.pick()
For picking a new task, we'll need to store the current task which was pick:
function SchedulerFactory() {
const q = QueueFactory();
let currentTask;
return {
add
};
function add(task){
q.enqueue(task)
}
}
Then, we'll need to:
- if there is a current task, we have to enqueue that (will move to the end of the queue)
- assign the current Task to the result of
dequeue(pick the first element of our queue) - return current task
In other words, we'll add the previous element back to the queue and replace it with the first queue element.
function SchedulerFactory() {
const q = QueueFactory();
let currentTask;
return {
add,
pick
};
function add(task){
q.enqueue(task)
}
function pick(){
if(currentTask){
q.enqueue(currentTask); // add the previous task to the end
}
currentTask = q.dequeue(); // get next task
return currentTask;
}
}
.size()
For the size, we cannot rely on the queue size because it'll always miss an element (the task we're currently executing).
So we can create an internal counter and increment 1 every time a new task is added:
function SchedulerFactory() {
const q = QueueFactory();
let currentTask;
let numberOfTasks = 0;
return {
add,
pick,
size,
};
function add(task) {
q.enqueue(task);
numberOfTasks++;
}
function pick() {
if (currentTask) {
q.enqueue(currentTask);
}
currentTask = q.dequeue();
return currentTask;
}
function size() {
return numberOfTasks;
}
}
Using SchedulerFactory
Now, we can use use our SchedulerFactory:
var taskScheduler = SchedulerFactor();
taskScheduler.add("Clean up memory");
taskScheduler.add("Check weather");
taskScheduler.add("Check stocks prices");
taskScheduler.add("Scrape website");
taskScheduler.add("Send email with info");
executeAllTasks(taskScheduler);
function executeAllTasks(scheduler) {
console.log("Starting Tasks...");
for (
let taskIndex = 0;
taskIndex < scheduler.size;
taskIndex++
) {
const task = scheduler.pick();
console.log(`Task[${taskIndex}]: ${task}`);
}
console.log("Finish Tasks");
}
The function executeAllTasks just loop over all tasks (using the scheduler size) and console them. Of course in real scenarios it'll be more complex tasks and executions but note that everything you call executeAllTasks with the same task scheduler (taskScheduler), it'll execute all tasks and start from the beginning:
executeAllTasks(taskScheduler);
executeAllTasks(taskScheduler);
executeAllTasks(taskScheduler);
// Starting Tasks... debugger eval code:40:11
// Task[0]: Clean up memory debugger eval code:49:13
// Task[1]: Check weather debugger eval code:49:13
// Task[2]: Check stocks prices debugger eval code:49:13
// Task[3]: Scrape website debugger eval code:49:13
// Task[4]: Send email with info debugger eval code:49:13
// Finish Tasks debugger eval code:52:11
// Starting Tasks... debugger eval code:40:11
// Task[0]: Clean up memory debugger eval code:49:13
// Task[1]: Check weather debugger eval code:49:13
// Task[2]: Check stocks prices debugger eval code:49:13
// Task[3]: Scrape website debugger eval code:49:13
// Task[4]: Send email with info debugger eval code:49:13
// Finish Tasks debugger eval code:52:11
// Starting Tasks... debugger eval code:40:11
// Task[0]: Clean up memory debugger eval code:49:13
// Task[1]: Check weather debugger eval code:49:13
// Task[2]: Check stocks prices debugger eval code:49:13
// Task[3]: Scrape website debugger eval code:49:13
// Task[4]: Send email with info debugger eval code:49:13
// Finish Tasks
Conclusion
Well, that's it about queues.
I hope you could understand that the data structure itself isn't that complicated to understand and the implementation isn't rocket science.
This is another tool for your toolbox of problem-solving in development. Every time you realize you're trying to solve a queue problem but you don't have the exact data structure, create your modeling of a queue to help you out.
This content originally appeared on DEV Community and was authored by Raul Melo
Raul Melo | Sciencx (2021-06-22T05:56:54+00:00) Data Structure with JavaScript: Queue. Retrieved from https://www.scien.cx/2021/06/22/data-structure-with-javascript-queue/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.