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

15 thoughts on “Data structures example: the queue class”

  1. Maybe I’m wrong, but it’s seems that you don’t remove data from internal array after dequeueing:
    var data:* = _que[_front++];
    if (_front == _size) _front = 0;
    _count--;
    return data;

    Is it right functionality? This could lead to some memory waste (but not leak) with bigger structures?
    Allthough this lib is awesome;)

  2. Good point :-) Instead of deleting the content I just move the front index to the next slot because the data will be overwritten when you enqueue something later on. This is just to make the function a little bit faster.

    Of course this leads to memory waste when the queue is really big and the garbage collector can’t remove the content until it’s overwritten. Perhaps I change the function so it deletes the content while dequeuing.

  3. Maybe constructor switch with default deleteNode:=true would be helpful. Then with namespace help you could switch between two methods with, and without deleting. But this idea needs to be tested against performance (how namespaces affecting speed).

  4. I constructor would be useful or a property of the object but some smart use of the lib to reduce the size for the game is in order. Frameworks can’t do everything.

    This is a really excellent demo I am just working on some way points using your kit and queued tweens using Tweener. Mighty good timing.

    Quite a show you are putting on here.

  5. Great work! I did find something diferent in the last svn files. In your code you place
    var aq:ArrayedQueue = new ArrayedQueue(17);
    While actually that didn’t work for me. I had to place the actual number 1 << 17 or 131072.
    Has this behavior changed? :) thanks!

  6. can you post some real world examples of queue?and stacks as well.i am in need.please halp…

  7. Good job at creating a containers lib for Action, when i first started doing flash,i was amazed there was now STL like stuff in the core.

    Thanks very much.

Comments are closed.