DEV Community

Cover image for Javascript: How to implement a queue

Javascript: How to implement a queue

chinedu | ddevguys on December 26, 2020

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

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
A 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

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

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

Collapse
 
hugoprudente profile image
Info Comment hidden by post author - thread only accessible via permalink
Hugo Prudente

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