STACKS AND QUEUES
Stacks and queues are specialized data structures that are useful in many programming applications that need to add and remove items in a particular order. The Visual Basic Stack and Queue classes implement stacks and queues.
The difference between a stack and a queue is the order in which they return the items stored in them. The following two sections describe stacks and queues and explain the ways in which they return items.
Stack
A stack returns items in last-in-first-out (LIFO, pronounced life-o) order. Because of the LIFO behavior, a stack is sometimes called a LIFO list or simply a LIFO.
Adding an item to the stack is called pushing the item onto the stack and removing an item is called popping the item off of the stack. These operations have the names push and pop because a stack is like a spring-loaded stack of plates in a cafeteria or buffet. You push new plates down onto the top of the stack and the plates sink into the counter. You pop the top plate off and the stack rises to give you the next plate.
Figure 25-3 illustrates this kind of stack. If you haven’t seen this sort of thing before, don’t worry about it. Just remember that push adds an item and pop removes the top item.
FIGURE 25-3: A Stack lets you remove items in last-in-first-out (LIFO) order.
Normally, you use a Stack object’s Push and Pop methods to add and remove items, but the Stack class also provides some cheating methods that let you peek at the Stack’s top object or convert the Stack into an array. The following table describes the Stack class’s most useful properties and methods.
| PROPERTY/METHOD | PURPOSE |
| Clear | Removes all items from the Stack. |
| Contains | Returns True if the Stack contains a particular object. |
| CopyTo | Copies some or all of the Stack class’s objects into a one-dimensional array. |
| Count | Returns the number of items in the Stack. |
| Peek | Returns a reference to the Stack class’s top item without removing it from the Stack. |
| Pop | Returns the Stack class’s top item and removes it from the Stack. |
| Push | Adds an item to the top of the Stack. |
| ToArray | Returns a one-dimensional array containing references to the objects in the Stack. The Stack class’s top item is placed first in the array. |
A Stack allocates memory to store its items. If you Push an object onto a Stack that is completely full, the Stack must resize itself to make more room and that slows down the operation.
To make memory management more efficient, the Stack class provides three overloaded constructors. The first takes no parameters and allocates a default initial capacity. The second takes as a parameter the number of items the Stack should initially be able to hold. If you know that you will add 10,000 items to the Stack, you can avoid a lot of resizing by initially allocating room for 10,000 items.
The third version of the constructor takes as a parameter an object that implements the ICollection interface. The constructor allocates enough room to hold the items in the collection and copies them into the Stack.
Example program UseStack, which is available for download on the book’s website, uses a Stack to reverse the characters in a string.
Queue
A queue returns items in first-in-first-out (FIFO, pronounced fife-o) order. Because of the FIFO behavior, a queue is sometimes called a FIFO list or simply a FIFO.
A queue is similar to a line at a customer service desk. The first person in line is the first person to leave it when the service desk is free. Figure 25-4 shows the idea graphically.
FIGURE 25-4: Customers leave a queue in first-in-first-out (FIFO) order.
Queues are particularly useful for processing items in the order in which they were created. For example, an order-processing application might keep orders in a queue so that customers who place orders first are satisfied first (or at least their order is shipped first, whether they are satisfied or not).
Historically, the routines that add and remove items from a queue are called Enqueue and Dequeue. The following table describes these methods and the Queue class’s other most useful properties and methods.
| PROPERTY/METHOD | PURPOSE |
| Clear | Removes all items from the Queue. |
| Contains | Returns True if the Queue contains a particular object. |
| CopyTo | Copies some or all of the Queue class’s objects into a one-dimensional array. |
| Count | Returns the number of items in the Queue. |
| Dequeue | Returns the item that has been in the Queue the longest and removes it from the Queue. |
| Enqueue | Adds an item to the back of the Queue. |
| Peek | Returns a reference to the Queue class’s oldest item without removing it from the Queue. |
| ToArray | Returns a one-dimensional array containing references to the objects in the Queue. The Queue class’s oldest item is placed first in the array. |
| TrimToSize | Frees empty space in the Queue to set its capacity equal to the number of items it actually contains. |
A Queue allocates memory to store its items. If you Enqueue an object while the queue’s memory is full, the Queue must resize itself to make more room, and that slows down the operation.
To make memory management more efficient, the Queue class provides four overloaded constructors. The first takes no parameters and allocates a default initial capacity. If the Queue is full, it enlarges itself by a default growth factor.
The second constructor takes as a parameter its initial capacity. If you know that you will add 600 items to the Queue, you can save some time by initially allocating room for 600 items. With this constructor, the Queue also uses a default growth factor.
The third constructor takes as a parameter an object that implements the ICollection interface. The constructor allocates enough room to hold the items in the collection and copies them into the Queue. It also uses a default growth factor.
The final version of the constructor takes as parameters an initial capacity and a growth factor between 1.0 and 10.0. A larger growth factor will mean that the Queue resizes itself less often, but it may contain a lot of unused space.
Example program UseQueue, which is available for download on the book’s website, demonstrates a Queue.