DEV Community

loading...
Cover image for Javascript: How to implement a queue

Javascript: How to implement a queue

chinedu profile image chinedu | ddevguys Originally published at ddevguys.com Updated on ・5 min read

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.

Alt Text

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.

Alt Text

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()
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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()
}
Enter fullscreen mode Exit fullscreen mode

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]
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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())
}
Enter fullscreen mode Exit fullscreen mode

Let’s use the queue class First, we have to instantiate the queue class we created

//instantiating the queue
let queue = new Queue()
Enter fullscreen mode Exit fullscreen mode

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")
Enter fullscreen mode Exit fullscreen mode

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())
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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())
Enter fullscreen mode Exit fullscreen mode

Let’s print out all the items in our queue

//returns [“Vivian”, “Gideon”, “Shalom”]
queue.print()
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

if we run

queue.print()
Enter fullscreen mode Exit fullscreen mode

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 ()
Enter fullscreen mode Exit fullscreen mode

To confirm our last action we can once again check if our queue is empty. This should return true

//returns true
queue.isEmpty()
Enter fullscreen mode Exit fullscreen mode

With this, we can say we have successfully implemented a queue in JavaScript KUDOS Alt Text you made it to this point but one more thing…

Alt Text

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❤️

Discussion (11)

pic
Editor guide
Collapse
aminmansuri profile image
hidden_dude

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).

Collapse
chinedu profile image
chinedu | ddevguys Author

This awesome! Would definitely play around with this! Thanks

Collapse
aminmansuri profile image
hidden_dude • Edited

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)

Collapse
zessu profile image
Wambua Makenzi • Edited

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

Collapse
aminmansuri profile image
hidden_dude

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.

Collapse
rsvp profile image
Аqua 🜉іtæ ℠ • Edited

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?

Collapse
chinedu profile image
chinedu | ddevguys Author

If I understand, you are suggesting I add some time-schedulling and memory allocation ideas using JavaScript to the series. Yes?

Collapse
rsvp profile image
Аqua 🜉іtæ ℠

Javascript: How to implement a queue VIA GENERATOR*?

Collapse
tylerlwsmith profile image
Tyler Smith

Saving this for later. Thank you for taking the time to write this out!

Collapse
chinedu profile image
chinedu | ddevguys Author

You are welcome! Am glad you found value in it!

Some comments have been hidden by the post's author - find out more