Priority Queue JavaScript Data Structure
In this lesson, you'll learn how we can combine several queues to create a new data structure: a priority queue. A priority queue allows the user to add items to the queue that are deemed to be high priority, and get moved ahead in the line. This added complexity is simple to achieve and is a good example of how we can build up complexity through the use of data structures.
Instructor: [00:00] We can easily make a PriorityQueue by using two queues, a high priority queue and a low priority queue, together.
[00:07] Our API will be the same as a normal queue. We'll have an enqueue, dequeue, peek, and is-empty method, as well as a length property, but we'll make some modification.
[00:17] First, we'll create two queues that we store in closure, a low priority queue and a high priority queue.
[00:23] Next, our enqueue method receives a second argument to indicate that an item is high priority. We'll set it to false by default. If an item is deemed high priority, we put it in the high priority queue. Otherwise, it goes into the low priority queue. We'll use a turn area to determine which priority queue it should go into.
[00:43] Next, our dequeue method will make sure that the high priority queue is empty before it dequeues from the low priority queue. This ensures that all high priority items are dequeued first. This time, we'll use an if statement to early return from the high priority queue, or otherwise return from the low priority queue.
[01:04] Next, our peek method gets a similar change. Just like we dequeue from the high priority queue first, we're going to peek from the high priority queue first as well. In fact, I can copy-paste this code and just make a change to which method is being called.
[01:18] Next, our length property is the addition of each queue's length property.
[01:24] Lastly, our is-empty method is the conjunction of the two queues' is-empty methods.
[01:30] Now that we've built our priority queue, let's try it out. Let's imagine your manager has given you a few tasks. A fix here, a bug there, and a new feature to build here. If we take a peek at our queue as it currently is, the item we should get back is a fix here.
[01:48] Great. That's working as we expect. That fix here was pretty easy. Let's dequeue it and make sure that's worked as well. Great. We dequeued a fix here, and now we're on a bug there.
[01:59] Let's say our manager comes to us with an emergency task, a task that needs to be done right away. Normally, we couldn't put something at the front of our queue. It has to wait in line, like every other task. But, using the second argument in our enqueue method, we can put it to the front of the tasks we need to do. If I save this and we take a peek at our queue now, that emergency task should be what comes up.
[02:21] Let's say we've averted the crisis, we've solved our emergency task, and we're going to dequeue it. Let's make sure that's what we get back when we dequeue and see that we're back to a bug there being the thing we need to fix.
[02:33] Great. We dequeued the emergency task, and a bug there is what we need to do. On with our tasks for the rest of the day.