After, writing about STACKS, the positive feedback, and all the support and nice DMs I got on Instagram and Twitter has made me turn this into a series, yeah you read that right.
This is going to be a series of data-structures and algorithms using javascript.
I hope you reading this enjoys it. Let’s go…🤓🤓🤓
In today’s blog article, we would be talking about queues!
What is a queue A queue is a data structure that follows the first in first out (FIFO)principle.
Example: people standing in a line (first come first serve) to get groceries from a grocery store, etc.
Queues are very similar to stack, but instead of using the LIFO principles like stacks do they use the FIFO principle which we would implement as we go on.
In javascript, we have array methods that define the queue class which is a push() and shift() method.
Adding an item to the queue is commonly known as enqueuing and removing an item from the queue is known as dequeuing.
push() is used to enqueue while shift() is used to dequeue.
The shift() is a javascript array method that removes and returns the first element of an array.
Let’s create a queue
Let’s write some codes, shall we? As usual, we start with the basics and declare a class using an array in the constructor property of our class.
// Queue class
Class Queue{
constructor() {
this.items=[];
}
//Methods to be
implemented go here
enqueue(item)
dequeue()
front()
isEmpty()
size()
print()
}
Let’s implement each method for our queue class.
Enqueue: This adds a new item to the back of the queue, this is similar to standing in a line (queue) to get items from a grocery store.
enqueue(item) {
//enqueuing items onto the queue
this.items.push(item)
}
Dequeue: This removes and returns the first item on the queue, this is the first come first serve.
The first person to get to our imaginary grocery store is the first person to be attended to.
dequeue(){
//remove items from the queue
this.items.shift()
}
Front: This method returns the first item from the queue, but it does not modify the queue.
In our imaginary grocery store, let’s imagine that the grocery store attendant wants to know who is first on the queue.
Note that he has not attended to this person yet in our case has not modified the queue.
He just wants to know who is first on the queue.
front() {
//returns the first item on the queue
this.items[0]
}
isEmpty: This returns false if the queue contains items or is greater than 0, and returns true if the queue is empty.
In our imaginary grocery store, let’s imagine that the grocery store attendant wants to know if there are more customers to attend to, if there are customers, that means the queue is not empty so as a result, we get false.
But if the grocery attendant has attended to everyone in the queue, then that means the queue is empty so as a result, we get true
isEmpty() {
this.items.length == 0;
}
Size: This gives us the number of items in our queue.
Back to our imaginary grocery store where we have a queue of customers.
Let’s imagine that the grocery store attendant for some reasons best known to him wants to know how many people he is attending to at the moment (people on the queue) then he will have to count them right? Yeah.
size() {
//check the number of items on the queue
this.items.length;
}
Just like when we implemented the STACKS class. We could go a step further to add a print method to help us print all the items in the queue whenever we want.
print() {
//log all the items in the queue
console.log(items to String())
}
Let’s use the queue class First, we have to instantiate the queue class we created
//instantiating the queue
let queue = new Queue()
Next, we can add items to our queue (since we are using the imaginary grocery store queue we would use real peoples names and enqueue them unto our queue. Let's use Vivian, Gideon, and Shalom)
// pushing a new item (customers) to the queue
queue.enqueue("Vivian")
queue.enqueue("Gideon")
queue.enqueue("Shalom")
Next, we can go ahead to check if items are on the queue (checking if anyone is on our grocery store queue)
//returns false
console.log(queue.isEmpty())
Next, we call the front() method, by doing so we would get Vivian because she happens to be the first person in the queue.
//returns vivian
queue.front()
Now, we want to check the size of our queue to see how many items (customers) are on it.
//returns 3
Console.log(queue.size())
Let’s print out all the items in our queue
//returns [“Vivian”, “Gideon”, “Shalom”]
queue.print()
Let’s remove items from the queue.
In our imaginary grocery store, we have to attend to our customers right? Yeah! If that be the case this has to happen in a first come first serve format (FIFO)).
Let’s do this
//remove each item from the queue
queue.dequeue()
queue.dequeue()
if we run
queue.print()
we see that Vivian and Gideon has left the queue (our first two customers have been tended too) so we have only shalom to attend too.
Let’s not waste his time let’s attend to him, so once again we run the dequeue method of our queue class
queue.dequeue ()
To confirm our last action we can once again check if our queue is empty. This should return true
//returns true
queue.isEmpty()
With this, we can say we have successfully implemented a queue in JavaScript KUDOS 
you made it to this point but one more thing…
Whenever a new tab is opened in a browser a task queue is created.
This is because of something we call the event loop and in the event loop only a single thread handles all the tasks for a single tab.
The browser handles several tasks such as handling user interaction (keyboard clicks, mouse clicks, etc), processing and executing async requests, executing javascript, and rendering HTML.
This is amazing that a very powerful and yet popular language like javascript uses queues to handle its internal control. You could learn more about it here
Once again as always thanks for being with me till the end.
Next, I would be writing about a very popular kind of queue implementation or maybe a linked list.
Well, I don’t know which to write about if you could make that choice for me I’d really appreciate you could consider sending a DM on Twitter or Instagram (join our 36k community members).
Cheers! Keep Grinding❤️
Top comments (11)
The problem with push() and shift() is that they involve a lot of memory copies for each operation. For example if you insert N items, you're going to have to move around N(N+1)/2 items around (ie. O(N^2) copies).
A better implementation is to have an array of a certain size, and 2 indices. Call them first, and last.
When you add an item to the queue you increment last:
last = (last + 1) % arr.length
When you remove an item from the queue you delete it and increment the first:
arr[first] = null
first = (first +1) % arr.length
Your queue is full when
function isFull() {
return (last + 1) % arr.length == first
}
If you don't want it ever to get full then you can detect it getting full and reinsert all items into a bigger array like you would in a hash table or dynamic array.
This gives you an O(N) implementation that does only a logarithmic number of copies if you support auto growing the array (which is often optional).
This awesome! Would definitely play around with this! Thanks
isEmpty would be:
first == last
(note that one space is wasted for isFull() otherwise you wouldn't be able to distinguish if it's full or empty)
Slightly confused over the need for last=(Last+1)%arr.lergth
Being that (x-1)%x always= x-1, shouldn't last just be=Last+1
Cheers
Where did you see x-1?
There should be no subtraction at all in a Queue.
The first pointer increments when you remove items. The last pointer increments when you add items.
The modulus is important to make the Queue circular and reuse the unused space. But in your implementation you should check that you aren't already full before accepting to add items.
Hope this helps.
TQ 4 point in deep. Can i ask u to add some time-scheduling && memory-allocation ideas? Kinda dynamic recursion-like programming. How about to make each (task|thread) a generator, And the queue set as main generator, which can consume a little one above? Can u make IT real with JS?
If I understand, you are suggesting I add some time-schedulling and memory allocation ideas using JavaScript to the series. Yes?
Javascript: How to implement a queue VIA GENERATOR*?
Saving this for later. Thank you for taking the time to write this out!
You are welcome! Am glad you found value in it!
Add some challenge and use C to do the same them you will learn how to really create data-structures.
Javascript it's to high level for such things.
Some comments have been hidden by the post's author - find out more