Yes, I know the adage "Don't reinvent the wheel", but for educational purposes, it's sometimes worth doing that.
Implementing Queue in JavaScript
Sometimes, fancy problems require fancy solutions. Implementing a custom queue is not an everyday task. Although many libraries can handle this, it's beneficial to understand how it works and how to implement one yourself - this helps avoid unnecessarily coupling your codebase with external libraries. Today, we'll delve into this topic, write a custom queue, and explore potential use cases for it.
The final solution is here: source code.
Required Theory
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed - mimicking a real-life queue like a line at a store. A queue supports two primary operations:
- Enqueue: This operation adds an element to the end of the queue.
- Dequeue: This operation removes the element at the front of the queue.
Queues are used to manage objects in processing tasks in the order they were created or received, making them essential in scenarios like:
- Task Scheduling: Queues can manage tasks in multi-threading environments, ensuring that tasks are executed in the order they were initiated.
- Handling Requests: In web servers, queues are used to handle incoming request data, serving requests in the sequence they arrive.
- Data Streaming: In streaming services, queues help manage data packets, ensuring they are processed in the correct order.
- Resource Sharing: Queues are effective in situations where multiple users or processes need access, and the order of read operation is important.
- Complex UI Behavior: Queues simplify complex client behavior like API requests, UI updates, and side effects.
Why and Where Do We Need a Queue?
Let's say you have several requests to process in a typical front-end application. You want a scalable and easy-to-use mechanism. Without it, your code might look like the following:
// Let's say it's an API request.
const mock = (delay: number) => {
return () =>
new Promise((resolve) => {
setTimeout(() => {
resolve({});
}, delay);
});
};
const request1 = mock(1300);
const request2 = mock(200);
const request3 = mock(5000);
const runAll = async () => {
// Requests are chained and performed in sequence.
await request1();
await request2();
await request3();
};
runAll();Doing this repeatedly can be somewhat redundant and additionally requires some caution on your part. If you forget to use await even once, you might end up with requests being executed in an unpredictable order.
To improve it, you may use loop:
const runAll = async () => {
for (const request of [request1, request2, request3]) {
await request();
}
};
runAll();However, this approach also carries the risk of errors. Additionally, it can result in code that is difficult to read and understand, especially in more complex operations.
Lastly, consider a scenario in which a specific event occurs in the application, such as user interaction, and you need to dynamically add a new request that must be processed only after all previous are finished. Without queue solution, achieving this in an easy and maintainable way is challenging.
const request1 = mock(1000);
const request2 = mock(20);
const request3 = mock(5000);
let promises = [request1, request2, request3];
const runAll = async () => {
for (const request of promises) {
await request();
}
};
const handleClick = () => {
// No guarantee of order.
// There may be other promises pending.
const newRequest = mock(222)();
await newRequest;
};
runAll();
// Some JSX component-based library/framework.
<button onClick={handleClick}>Click Me</button>;Isn't it easier and more pleasing to the eye to do it in the following manner? Of course, by doing that, we'll ensure the requests are in the correct order!
import { queue } from "queue";
const { enq } = queue();
const handleClick = () => {
// New requests will be queued and executed in the correct order.
const newRequest = mock(1000);
enq(newRequest);
};
const request1 = mock(1000);
const request2 = mock(20);
const request3 = mock(5000);
// Instead of the "runAll" function.
enq(request1, request2, request3);I think you'll agree with me - let's implement this beast!
Queue Implementation Process
We need to store the list of current tasks that will be added. We'll use an array for that.
// A task is a function that returns a promise.
type QueueTask = () => Promise<unknown>;
const queue = () => {
const allTasks: QueueTask[] = [];
};
export { queue };Next, we need to have a method that will add n tasks to the allTasks array. All tasks should be added at the end.
const queue = () => {
const allTasks: QueueTask[] = [];
return {
enq: async (...tasks: QueueTask[]) => {
// Pushing tasks at the end of array.
tasks.forEach((task) => allTasks.push(task));
},
};
};Now we want to call these tasks in sequence. However, here's a challenge: What if a situation arises where a developer wants to call enq(...tasks) multiple times? Just like this:
const { enq } = queue();
enq(task1, task2);
enq(task3);
enq(task4);The first idea may be to use the following mechanism:
for (const task of allTasks) {
await task();
// Removes the first element from an array.
allTasks.shift();
}However, it only guarantees the order of a single enq call. If we use some kind of builder pattern, where one method is used to build the tasks list and another method is used to execute them, it will be much easier, and the code above may work effectively.
// @@@ queue.ts file
// The "run" function implementation idea in "queue".
const run = () => {
for (const task of allTasks) {
await task();
// Removes first element from an array.
allTasks.shift();
}
};
// @@@ example.ts file
const { enq, run } = queue();
enq(task1, task2);
enq(task3);
enq(task4);
run(); // Runs queue.It will work 100% fine, but the "interaction" aspect is missing. We need to build and run it once, which requires caution to perform additional tasks at the beginning. However, this is not the case with queue. It must be dynamic and always maintain the correct order, reflecting the moment of addition from any place or module where the instance is used.
So, we need to use something else. Something that ticks, takes into account the current allTasks variable, and runs each task added to this list one by one. You may say I'm crazy, but without setInterval, it's impossible to achieve order between different execution contexts and the dynamic nature of queues. So, here is how we'll do that:
- The interval will run.
- If there are no tasks, it will stop.
- Only one interval may run.
- Interval starts when there is at least one task.
- When a task is in progress, all next waiting.
It will be similar to the typical
game development, where an infinite loop ticks until the game is finished. The "finish" in our case will be the moment of having empty tasks.
We need to add two flags: ticking and processing. The first one will indicate if the interval is working, and the second one will indicate if there is any task in progress.
const queue = () => {
const allTasks: QueueTask[] = [];
let ticking = false;
let processing = false;
};Then, if there is no ticking, we'll call a tick function.
return {
enq: async (...tasks: QueueTask[]) => {
tasks.forEach((task) => allTasks.push(task));
// If ticking falsy, run the "tick()".
ticking || tick();
},
};
};Almost last, is the tick function implementation. It will manage tasks execution and their order.
const queue = () => {
const allTasks: QueueTask[] = [];
let ticking = false;
let processing = false;
const tick = () => {
ticking = true;
const interval = setInterval(async () => {
// Skips if there is at least one task being processed.
// Thanks to that, all other intervals will do nothing
// until the current task is finished.
if (processing) return;
// Removes the first task from the array and assigns it to the variable.
const task = allTasks.shift();
// If the task is a function, it's called.
if (typeof task === `function`) {
// Blocks other tasks processing.
processing = true;
// Runs a task.
await task();
// Unblocks task processing.
processing = false;
return;
}
// Removes interval and cleans ticking.
ticking = false;
clearInterval(interval);
}, 50); // It may be any value, depends how often you want to "tick".
};
};The trick is that the shift() method returns a function (our task) or undefined if the array is empty. If the returned task is undefined, we need to stop ticking. In addition, shift mutates the original array, so with each task processed, it will remove one element when the process starts.
Last, the deq method will dequeue the last task.
const queue = () => {
return {
enq: async (...tasks: QueueTask[]) => {
tasks.forEach((task) => allTasks.push(task));
ticking || tick();
},
deq: () => {
// Removes the last task.
allTasks.shift();
},
};
};Queue Final Code, Usage and Demo
Here you have the full version of the queue utility function:
type QueueTask = () => Promise<unknown>;
const queue = () => {
const allTasks: QueueTask[] = [];
let ticking = false;
let processing = false;
const tick = () => {
ticking = true;
const interval = setInterval(async () => {
if (processing) return;
const task = allTasks.shift();
if (typeof task === `function`) {
processing = true;
await task();
processing = false;
return;
}
ticking = false;
clearInterval(interval);
}, 50);
};
return {
enq: async (...tasks: QueueTask[]) => {
tasks.forEach((task) => allTasks.push(task));
ticking || tick();
},
deq: () => {
allTasks.shift();
},
};
};
export { queue };Here you have the usage example in React, but it will work in any JavaScript related code:
import React from 'react';
import { queue } from './queue';
import { mock } from './mock';
import { motion, AnimationProps } from 'framer-motion';
import { Button } from 'design-system/button';
import classNames from 'classnames';
const props: AnimationProps = {
initial: { opacity: 0 },
animate: { opacity: 1 },
};
const { enq, deq } = queue();
type TaskBadge = {
label: string;
status: 'pending' | 'error' | 'skipped' | 'finished';
};
const CreatorView: React.FC = () => {
const [tasks, setTasks] = React.useState<TaskBadge[]>([]);
const addTask = (label: TaskBadge['label']) => {
setTasks((prevTasks) => [...prevTasks, { status: `pending`, label }]);
};
const changeTask = (
label: TaskBadge['label'],
status: TaskBadge['status'],
) => {
setTasks((prevTasks) =>
prevTasks.map((task) =>
task.label === label ? { ...task, status } : task,
),
);
};
const addNewRandomTask = () => {
enq(async () => {
const id = new Date().toISOString().split(`T`)[1];
const request = mock(1000, id);
addTask(id);
await request();
changeTask(id, `finished`);
});
};
React.useEffect(() => {
const request1 = mock(1000, `request1`);
const request2 = mock(500, `request2`);
const request3 = mock(1200, `request3`);
const request4 = mock(100, `request4`);
enq(
async () => {
try {
addTask(`request2`);
await request2();
changeTask(`request2`, `finished`);
} catch (err) {}
},
async () => {
addTask(`request1`);
try {
await request1();
throw Error(`Ups`);
} catch (err) {
changeTask(`request1`, `error`);
}
},
async () => {
addTask(`request4`);
await request4();
changeTask(`request4`, `finished`);
},
);
enq(async () => {
addTask(`request3`);
await request3();
changeTask(`request3`, `finished`);
});
}, []);
return (
<>
<div className="p-4 flex items-center flex-wrap gap-4">
{tasks.map((task) => (
<motion.div
key={task.label}
className={classNames(
`text-xl rounded-md text-black shadow-md p-4`,
{ 'bg-gray-500 animate-pulse': task.status === `pending` },
{ 'bg-green-500': task.status === `finished` },
{ 'bg-red-500': task.status === `error` },
)}
{...props}
>
{task.label}
</motion.div>
))}
</div>
<div className="flex flex-col space-y-2 p-4">
<h6 className="text-2xl">Legend</h6>
<div className="flex items-center space-x-4">
<div className="flex items-center space-x-2">
<strong>Pending:</strong>
<div className="bg-gray-500 animate-pulse h-5 w-5 rounded-full" />
</div>
<div className="flex items-center space-x-2">
<strong>Ok:</strong>
<div className="bg-green-500 h-5 w-5 rounded-full" />
</div>
<div className="flex items-center space-x-2">
<strong>Error:</strong>
<div className="bg-red-500 h-5 w-5 rounded-full" />
</div>
</div>
</div>
<div className="p-4 mt-10 flex space-x-3">
<Button s={2} i={2} auto onClick={addNewRandomTask}>
Enqueue
</Button>
<Button s={2} i={2} auto onClick={deq}>
Dequeue
</Button>
</div>
</>
);
};
export default CreatorView;Please take note that we're performing some additional operations, such as state changes in each task, to indicate its sequential nature. This is how it looks in the app:
Under the following PR, you have the full version with provided examples: source code.
Summary
We did it! Our queue is working and allows us to dynamically enqueue/dequeue new tasks. Some tricks were used (like the one connected with ticking), but I wanted to make it really dynamic and avoid the "builder" approach, which would produce much more code for each feature. Now, you just need to call a single function - enq, and magically, everything is handled within the queue mechanism.
So let's summarize what we've learned:
- The queue is a linear data structure.
- It follows the (FIFO) principle - first in, first out (like a queue in the market).
- To implement it, we can use the builder approach or a more dynamic approach with ticking.