Data structures example: the queue class
May 23, 2007 on 10:35 pm | In Actionscript, data structures |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
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;)
Comment by maliboo — May, 27 2007 #
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.
Comment by Michael — May, 27 2007 #
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).
Comment by maliboo — May, 27 2007 #
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.
Comment by draw.logic — May, 29 2007 #
[...] Polygonal Labs who share their knowledge and code with the rest of us. I’m looking at his Queue class to hold the state of an object every tick of the game clock. Its advantage is speed. The only [...]
Pingback by Actionscript Rodeo » Queues in Time Travel — June, 30 2007 #
[...] game development. He’s also writing examples on how some of the classes are used, for example Queue and Tree. The hexagon framework will contain similar data structure classes but they will adhere [...]
Pingback by H1DD3N.R350URC3 » AS 3.0 Data Structures For Game Developers — August, 23 2007 #
wow.. great tutorial. that was inspirating me to alot of things :) . thx alot
Comment by yogibali — November, 27 2007 #
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!
Comment by Ramiro Araujo — February, 28 2008 #
can you post some real world examples of queue?and stacks as well.i am in need.please halp…
Comment by grace — March, 3 2008 #
See this book. It has lots of application in all fundamental data structures.
http://www.mhhe.com/mukherjee/ds
Stack is used for several purposes. But they are great when designing parser is needed.
Comment by Sudipta — June, 23 2008 #
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.
Comment by Nicolas — July, 24 2008 #
[...] using the great opensource package from Michael Baczynksy at polygonal.de for the use of lists, queues, stacks and trees . While it works great, it has some explicit design decisions that we do not want [...]
Pingback by The collections package at dpdk Open Source — October, 9 2008 #
[...] Another very important thing if you wish to use the code (and it is noted in the updated code comments) is to make sure you use a far superior option for queuing that Adobe’s pathetically slow “Array as a queue wannabe by using shift()”. Array is Array, and that means that by definition it does not do what linked lists, queues, stacks etc. do with anywhere near the same efficiency. I can suggest Mike Baczynski’s Queue implementation. [...]
Pingback by Visual Harmonics » Post Topic » AS3 conversion of “Modelling Rays for Line of Sight in an Object-Rich World” — January, 26 2009 #
IT’s not a good example..
Comment by Ajeet — January, 23 2010 #
so good these articles.
Comment by daylyn — February, 20 2010 #