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...
Some comments have been hidden by the post's author - find out more
For further actions, you may consider blocking this person and/or reporting abuse
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.