Implementing a Queue

The diagrams in Figures 6.9, 6.10, and 6.11 show a simple queue before and after adding a new item and before and after removing an item. At each point, you can add a new item only at the rear of the queue and can remove an item only from the front of the queue. (Note that the front of the queue, where you delete items, is at the left of the diagrams. The rear of the queue, where you add items, appears to the right.)

Maintaining a queue takes a tiny bit more code than maintaining a stack, but not much. Although the queue is handled internally as a linked list, it has some limitations as to where you can add and delete items, and the underlying code handles these restrictions. The queue structure requires two class modules, one each for the Queue and QueueItem classes.

Figure 6.9: A simple queue just before a fourth item is added

Figure 6.10: The simple queue after the fourth item is added and before an item is removed

Figure 6.11: The simple queue after an item has been removed

The QueueItem Class

Just like the StackItem class, the QueueItem class stores just a data value and a pointer to the next data element, as shown in Listing 6.5.

Listing 6.5: Code for the QueueItem Class

' Keep track of the next queue item,
' and the text of this item.
Public NextItem As QueueItem
Public Value As Variant

The Queue Class

As with the Stack class, all the interesting code required in working with the data structure is part of the parent class—in this case, the Queue class. It’s here you’ll find the methods for adding and removing items in the queue, as well as a read-only property that indicates whether the queue is currently empty. Because a queue needs to be able to work with both the front and the rear of the queue, the Queue class includes two pointers rather than just one, making it possible to add items at one end and to remove them from the other. These pointers are defined as qFront and qRear, as shown here, and are module-level variables:

Dim qFront As QueueItem
Dim qRear As QueueItem

Adding an Item to the Queue

To add an item to a queue, you “enqueue” it. That is, you add it to the rear of the queue. To do this, the Add method follows these steps:

Creates the new node.
Places the value to be stored in the new node.
If the queue is currently empty, makes the front and rear pointers refer to the new node.
Otherwise, links the new node into the list of nodes in the queue. To do that, it makes the final node (the node the “rear pointer” currently points to) point to the new item. Then it makes the rear pointer in the queue header object refer to the new node.

The code in Listing 6.6 shows the Add method of the Queue class.

Listing 6.6: Use the Add method to Add a New Item to a Queue

Public Sub Add(varNewItem As Variant)
    Dim qNew As New QueueItem
    qNew.Value = varNewItem
    ' What if the queue is empty? Better point
    ' both the front and rear pointers at the
    ' new item.
    If QueueEmpty Then
        Set qFront = qNew
        Set qRear = qNew
    Else
        Set qRear.NextItem = qNew
        Set qRear = qNew
    End If
End Sub

The diagrams in Figures 6.12 and 6.13 demonstrate the steps for adding a new node to an existing queue.

Figure 6.12: After you create the new node, the Add method is ready to attach it to the queue.

Figure 6.13: To finish adding the node, set qRear to point to the new node.

What if the queue was empty when you tried to add an item? In that case, all you need to do is make the head and rear of the queue point to the new node. Afterward, the queue will look like the one in Figure 6.14.

Figure 6.14: After a new node is added to an empty queue, both the head and rear pointers refer to the same node.

Removing Items from the Queue

Removing an item from the queue both removes the front node from the data structure and makes the next front-most item the new front of the queue. In addition, this implementation of the queue data structure returns the value of the removed item as the return value from the Remove method.

The code for the Remove method, as shown Listing 6.7, follows these steps:

Makes sure there’s something in the queue. If not, the Remove method doesn’t do anything and returns a null value.
Sets the return value of the function to the value of the front queue item.
If there’s only one item in the queue, sets both the head and rear pointers to Nothing. There’s nothing left in the queue.
If there was more than one item in the queue, sets the front pointer to refer to the second item in the queue. This effectively kills the old first item.

Listing 6.7: Use the Remove Method to Drop Items from a Queue

Public Function Remove() As Variant
    ' Remove an item from the head of the
    ' list, and return its value.
    If QueueEmpty Then
        Remove = Null
    Else
        Remove = qFront.Value
        ' If there’s only one item
        ' in the queue, qFront and qRear
        ' will be pointing to the same node.
        ' Use the Is operator to test for that.
        If qFront Is qRear Then
            Set qFront = Nothing
            Set qRear = Nothing
        Else
            Set qFront = qFront.NextItem
        End If
    End If
End Function

How can you tell when there’s only one item in the queue? The Is operator comes in handy here. By checking whether “qFront Is qRear”, you can find out whether the two variables refer to the same object. If the condition is True, they do refer to the same object, and therefore, there’s only one item in the queue.

The diagram in Figure 6.15 demonstrates the one difficult step in removing an item. The diagram corresponds to this line of code:

Set qFront = qFront.NextItem

By moving the front pointer to the item that the first item previously pointed to, you eliminate the reference to the old first item, and VBA removes it from memory. After this step, the queue will contain one fewer item.

Figure 6.15: To remove an item, move the front pointer to the second node in the queue.

Is the Queue Empty?

You’ll often need to be able to detect whether the queue is empty, and the example implementation includes the read-only QueueEmpty property for this reason. The queue can be empty only if both the front and rear pointers are Nothing, and the code shown here checks for this condition:

Property Get QueueEmpty() As Boolean
    ' Return True if the queue contains
    ' no items.
    QueueEmpty = ((qFront Is Nothing) And (qRear Is Nothing))
End Property

The QueueEmpty property allows you to write code like this:

Do While Not q.QueueEmpty
    Debug.Print q.Remove()
Loop

A Simple Queue Example

The code in Listing 6.8 demonstrates the use of the queue data structure. It creates a new queue, adds five words to the queue, and then removes the words, one at a time. The words should come out in the same order in which they were entered. Note that if you’d used a stack for the same exercise, the words would have come out in the opposite order from the one in which they’d been entered.

Listing 6.8: Using the Queue Data Structure

Dim qTest As New Queue
Sub TestQueues()
    With qTest
        .Add "Hello"
        .Add "There"
        .Add "How"
        .Add "Are"
        .Add "You"
        Do While Not .QueueEmpty
            Debug.Print .Remove()
        Loop
    End With
End Sub