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).
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.
I am a software Developer, experienced in both front and back-end development, proficient in HTML5, CSS3, SASS, JavaScript, Reactjs, Nodejs, Expressjs and Mongodb etc.
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).
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.
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)