Over the past couple of months a number of articles have been presented on creating a generic dynamic array class and a stack class. (In the stack class article we also looked at how to create a list class.) The only major data structure missing is a Queue class, which we'll look at creating in this article. If you haven't read the two previous articles (the dynamic array class and the stack class article) be sure to take a moment to read them; today's article builds directly on the theory and source code presented in these two previous articles! (Also, if you are not familiar with VBScript classes, I highly recommend that you first read: Using Classes within VBScript.
As discussed in the stack class article there are a number of handy data structures that aren't inherently available in VBScript. These data structures include:
List: - An ordered collection of items. Each item in a list is "connected" to one another through some means, and a global reference exists to the starting item in the list. That way, to visit any other item in the list, the user can sequentially step through the list.
Stack: - A stack is similar to a queue except it follows a first in, last out semantic. A stack, like a queue, has two operations: push, which adds an item to the top of the stack, and pop, which removes an item from the top of the stack. A stack is like a stack of cafeteria trays. When taking a tray, you are removing the tray that was last put on the stack. Therefore, if we pushed A, B, and C onto a stack, when we popped the elements off, we'd get C, B, and A, in that order.
Queue: - An ordered collection of items that follows the following semantic: first in, first out. A queue has the following operations: enqueue and dequeue. When an item is enqueued, it is added to the queue, while a dequeue removes the item. The items are removed in the order they are added to the queue. So, if a queue had three items enqueued - A, B, and C - it would first dequeue A, then B, and then C.
Our queue class will contain a number of methods that enable elements to be added to the queue (
and removed from the queue (
Dequeue). Like the stack class, we will also provide the developer the
ability to peek at the head of the queue (
Peek). Also, as with the stack class, we will also provide
a single property,
Count, which returns the number of elements remaining in the queue.
Our queue class can be easily built using the
WeakList class that was presented in the
stack class article. (The source code to the
is available for downloading. Take a moment to download the source
and save the contents in an ASP page named
WeakList.Class.asp.) Use of the
class will make creating the queue class extremely easy. Before we begin designing the queue class, though, let's
take a moment and examine the methods of the
||Adds the |
||Removes the head element of the list, and returns its value.|
||Adds the |
||Removes the tail element of the list, and returns its value.|
||Returns the value at the head of the list, without altering the list at all.|
||Returns the value at the tail of the list, without altering the list at all.|
Our queue class will have a single member variable, an instance of the
WeakList class. The following
code illustrates the queue class's member variable declaration and