Queues

Using an Array to process entries in a Stack is relatively straightforward since we only need to access the end of the array and push() and pop() keep track of that position for us.

Another construct that you may want to use is the Queue. If you imagine people lining up to buy tickets to some event. New arrivals join the end of the queue while the next person who gets to buy a ticket is the person at the front of the queue. A queue operates on the First In - First Out principle (FIFO).

Fortunately, in addition to providing a way to add and remove entries from the end of an Array, Javascript also provides a way to add and remove objects at the front of the array (effectively moving all of the other array entries up or down by one in their numerical location within the array).

unshift() can be used to add move all array elements up by one position and then add the extra value to position zero of the array and shift() will retrieve the entry in position zero and move all of the entries down one.

Simply substituting unshift() and shift() for push() and pop() would just give us another stack construct only using the start of the array as the top of the stack instead of the end of the array. In order to get a queue construct we need to combine the two alternatives together using one from each end of the array like this:

var queue = [];
...
queue.push(entry1);
var entry2 = queue.shift();

By using push() and shift() in combination like this we can add new entries to the end of the array and process entries from the start of the array without any need to know how many entries are currently in the array exactly as we want for queue processing.

 

This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow
Donate