Stacks and Queues

Stacks and queues are specialized data structures that are useful in many programming applications. These objects are useful for storing objects temporarily before you process them and remove them from the stack or queue. The Visual Basic Stack and Queue classes implement stacks and queues.

Usually, items are removed shortly after they are added. For example, an algorithm might fill a stack with objects to process and then, as long as the stack is not empty, remove one and process it. Processing one job might add others to the stack, which would be processed later. The process would continue until the stack was empty.

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 18-6 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 18-6: 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 class’s top object or convert the Stack into an array. The following table describes the Stack class’s most useful properties and methods.

Open table as spreadsheet

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 stores 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 the operation down.

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 it 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.

The following code uses a stack to reverse the characters in a string. It gets the string from the txtInput TextBox and creates a stack. For each letter in the string, it adds the letter to the stack.

Next, while the stack is not empty, the program removes the top letter from the stack and adds it to the result string. Because the letters are popped off the stack in LIFO order, the result is the reverse of the original string.

  Dim txt As String = txtInput.Text Dim letter_stack As New Stack ' Add the letters to the stack. For i As Integer = 0 To txt.Length - 1     Debug.WriteLine(i)     letter_stack.Push(txt.Substring(i, 1)) Next ' Remove the letters from the stack. txt = "" Do While letter_stack.Count > 0     txt &= DirectCast(letter_stack.Pop(), String) Loop ' Display the result. lblResult.Text = txt  

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 18-7 illustrates a queue.

Figure 18-7: In a queue, items are removed 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.

Open table as spreadsheet

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 object stores its items in a circular array, as shown in Figure 18-8. The array isn’t really circular; the Queue just pretends it is. If it goes past the last item in the normal one-dimensional array, the Queue wraps around to the first item as if the array were circular.

Figure 18-8: A Queue stores its items in a circular array.

Counters keep track of where the first and last items in the Queue are stored. When you Dequeue an item, the Queue returns the first item and moves the first item pointer to the next item in the array. When you Enqueue an item, the Queue places the new item after the last item and updates the last item pointer.

If you Enqueue an item when the Queue’s array is full, the Queue must resize its array 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 its array 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 many empty array entries.

Queues are useful for scheduling items in a FIFO order. For example, a shared network computer uses a queue. Users on different computers send jobs to the printer, and they are printed in FIFO order.

The following code shows how a program might use a queue to arrange strings for output. When you click the btnAdd1 Button control, the program takes the text from the txtInput1 TextBox control and adds it to the queue. It then calls subroutine DisplayQueue to show the items currently in the queue. Other Button event handlers not shown similarly take strings from other TextBox controls and add them to the queue.

When you click the btnDequeue Button, the program removes the first entry from the queue and adds it to the lstResult ListBox. It then calls DisplayQueue again to show the queue’s contents.

Subroutine DisplayQueue uses the queue’s ToArray method to fetch the items in the queue. It loops through the items, adding them to a ListBox, so you can see what’s in the queue. Note that the code uses DirectCast to convert the generic Object array entries into Strings.

  ' Create the queue. Private m_Queue As New Queue ' Add an item to the queue. Private Sub btnAdd1_Click(ByVal sender As System.Object, _  ByVal e As System.EventArgs) Handles btnAdd1.Click     m_Queue.Enqueue(txtInput1.Text)     DisplayQueue() End Sub ' Other routines for adding items to the queue. ... ' Remove the first item from the queue. Private Sub btnDequeue_Click(ByVal sender As System.Object, _  ByVal e As System.EventArgs) Handles btnDequeue.Click     Dim txt As String = DirectCast(m_Queue.Dequeue(), String)     lstResult.Items.Add(txt)     DisplayQueue() End Sub ' Display the items in the queue. Private Sub DisplayQueue()     lstQueue.Items.Clear()     For Each str As String In m_Queue.ToArray()         lstQueue.Items.Add(str)     Next str     ' Enable or disable the Dequeue button.     btnDequeue.Enabled = (m_Queue.Count > 0) End Sub