Mathematica 9 is now available

Queues

A queue is like a stack except that we now must retain a pointer to the "front" and another to the "back" because we put new elements in one end and remove from the other; this is "first in, first out," or FIFO for short. We add at the front and remove at the back. We require routines to (i) get a new queue, (ii) check the length and in particular check if it is empty (could also have a check-for-full-queue function), (iii) add elements, and (iv) remove elements. One method is to use a fixed size table and have front and back indices that wrap around.

[Graphics:../Images/index_gr_61.gif]

Here is a simple example.

[Graphics:../Images/index_gr_62.gif]
[Graphics:../Images/index_gr_63.gif]
[Graphics:../Images/index_gr_64.gif]
[Graphics:../Images/index_gr_65.gif]
[Graphics:../Images/index_gr_66.gif]

We ran out of space. We'll remove an element and then we can put on that last one.

[Graphics:../Images/index_gr_67.gif]
[Graphics:../Images/index_gr_68.gif]
[Graphics:../Images/index_gr_69.gif]

If one does not want to worry about running out of space, or does not want to preallocate alot of memory in order to avoid this, then it is convenient to represent queues in Mathematica using a sparse array. We show a way to implement this below. We require a symbol to give to newQueue. It determines where we attach down-values for queue entries. A small subtlety is due to the desire to remove from memory elements no longer on the queue. To this end we keep a storage slot for one element in the queue structure. When we de-queue an element, we temporarily house it in that slot, remove the sparse array reference for that queue member, then return the warehoused value. An alternative would be to use Module and declare a local variable, but this adds overhead in execution time.

[Graphics:../Images/index_gr_70.gif]

Let us see how this process works. We repeat the previous example. This time we'll not run out of space.

[Graphics:../Images/index_gr_71.gif]
[Graphics:../Images/index_gr_72.gif]
[Graphics:../Images/index_gr_73.gif]
[Graphics:../Images/index_gr_74.gif]
[Graphics:../Images/index_gr_75.gif]
[Graphics:../Images/index_gr_76.gif]
[Graphics:../Images/index_gr_77.gif]

We can see exactly what is in our queue using the Information function. This is in some sense cheating, because queues do not have a function to return all elements. Regard this as a useful debugging tool to check the correctness of our queue. Notice that we now have no sparse array reference to the original first two queue elements, so we are indeed recycling memory.

One might hybridize these approaches to get the faster access associated with a fixed-size array, combined with the memory management associated with sparse functions. This hybridization can be accomplished by, say, doubling the size of the table every time the queue gets full, copying over the entries already on it. Again we sometimes have an O(n) time for an en-queue operation, but the average is O(1). If so desired, one can get more subtle with memory management and allow for the queue table to shrink by some factor, say 1/2, whenever the fraction of entries falls below some threshhold, e.g 1/3, of the full capacity. This again can help to avoid wasting space in cases of once-large queues that have shrunk considerably. So long as fixed ratios are used it is not hard to show that average time for en-queue and de-queue will be O(1) even though occasionally such an operation is O(n).

[Graphics:../Images/index_gr_78.gif]
[Graphics:../Images/index_gr_79.gif]
[Graphics:../Images/index_gr_80.gif]
[Graphics:../Images/index_gr_81.gif]
[Graphics:../Images/index_gr_82.gif]
[Graphics:../Images/index_gr_83.gif]
[Graphics:../Images/index_gr_84.gif]
[Graphics:../Images/index_gr_85.gif]
[Graphics:../Images/index_gr_86.gif]

The advantage to this second approach is we only use the memory we need, and we do not run out (subject to machine limitations). The disadvantage is that, while complexity of each operation is constant time, the constants can be high for adding and removing elements. This is because hash table look-up is happening behind the scenes, and this is alot slower than simple array indexing. Also note that since sparse arrays are implelemted using hashing, occasionally adding elements will be O(n) because crowding in the table can force it to double in size. Thus it is the average time for adding that is constant.

Here is an application of queueing. Suppose we take the stack-based flattening code and everywhere replace stack uses with their queue analogues. What might be the result?

[Graphics:../Images/index_gr_87.gif]
[Graphics:../Images/index_gr_88.gif]
[Graphics:../Images/index_gr_89.gif]

One checks that in addition to flattening, we have reordered the non-list elements based on nesting depth. For comparison, here is a functional programming approach to the same problem.

[Graphics:../Images/index_gr_90.gif]
[Graphics:../Images/index_gr_91.gif]

It unfortunately only works if the elements in the (nested) lists are atomic. It is a more challenging problem to find a clever functional program that does not have this limitation.

While queues are of interest in their own right, it is important to realize that the method of implementation in this section is quite general. One can use similar structures, implemented as sparse arrays with other information e.g. length also available, for a variety of purposes. For example, sets that can evolve over time, with members being added, removed, or merged in from other sets, can be handled in this way.