Data structures example: the queue class

FIFO – First In, First Out

The queue class is rather basic, which saves me a lot of writing :-). The idea is simple: Think of waiting in a line at a movie theater; you get in line at the end to buy a ticket (enqueue); you reach the head of the line (peek) and finally buy the ticket and leave the line (dequeue). To use the queue class you only need three basic methods. Here are the method signatures:

var success:Boolean = myQueue.enqueue(obj);
var obj:* = myQueue.peek();
var obj:* = myQueue.dequeue();

Enqueue() obviously enqueues an item, peek() returns an instance to the front item and dequeue() removes and returns the front item at the same time. Here is a simple demonstration (first click flash to get focus):

Use key e to enqueue an item and d to dequeue the front item (blue colored circle). The numbers indicate the order of the items inside the queue. Lower numbers leave the queue before higher numbers. Also if the queue is full, all nodes are purple colored.

Size matters

A limitation of the queue class is that it has be to initialized with a fixed size. So in case the queue is full, the enqueue() method does nothing and just returns false:

var success:Boolean = myQueueInstance.enqueue(obj);

Defining a size for a new queue is also a bit different from other classes in the package because it has to be a multiple of two – this is needed for a fast bitwise modulo to speed up the array access. A queue is used so often in game programming that it should run as fast as possible, although it wasts some memory – the array might be bigger than actually needed. Instead of passing the target size directly, you pass the exponent by which 2 is raised:

var myQueueInstance:ArrayedQueue = new ArrayedQueue(4);

The queue above can store 16 items, because 2^4 (eq. 1 << 4) is 16. To be able to store 32 items, pass 5 (2^5) and so on.

Performance

If you now think “Who needs a class for it ? I keep it real and just use the native flash array methods push() and shift() !” then I have a surprise for you. Lets create a really big queue with more than 100,000 elements (131,072 to be exactly, which is 2^17). Now we enqueue items until its full, then empty it with dequeue.

The push/shift version (or unshift/pop, it doesn’t matter) takes 13 seconds(!) on my machine:

var size:int = 1 << 17;
var que:Array = [];
for (var i:int = 0; i < size; i++)
{
    que.push("foo");
}
for (var i:int = 0; i < size; i++)
{
    var result:String = que.shift();
}

Now the queue class, which takes only 40 milliseconds:

var aq:ArrayedQueue = new ArrayedQueue(17);
var success:Boolean;
do
{
    success = aq.enqueue("foo");
}
while (success);

var result:String;
do
{
    result = aq.dequeue();
}
while (result);

Here is a comparison table using a queue with a more realistic size:

time in milliseconds
size push/shift enqueue/dequeue
16384 211 5
8192 56 2
4096 15 1
2048 4 1
1024 1 1

As you see, the queue class grows linearly in processing time, while the array methods increases more drastically. This is because the flash player has to move a lot of data around inside the memory every time you add or remove the first element of an array (or any other in between except for the last one).

For very small queues, the class is a little bit slower. On the other hand it manages the size of the queue for you and also provides an iterator and implements the collection interface.

So this should be all you need to know about queues. Besides, the package contains also the LinkedQueue, which is based on a linked list, thus has no size limitations and performs the same no matter how many elements are stored inside it. The class itself is simple – it just defines some wrapper functions for a the linked list to provide queue-like access.

A command queue

Finally a little real-world example of what is called a command queue. I used it to create a very basic waypoint system. Click on the flash to add a waypoint, and the ‘plane’ (the colored circle) follows all waypoints until the queue is empty.

The sources for the flash examples can be downloaded here (Flash CS3 required). Next in the series will be the graph class, so stay tuned :-)

See also:
Linked lists
The tree class
The graph class