Desktop Developer

### Manage Stacks of Data

The .NET Framework includes a Stack class that implements a stack collection. Learn how stacks are used to manage multiple states of data within an app.

*Technology Toolbox: VB.NET, .NET Framework*

Stacks are one of the many types of data structures computer scientists developed decades ago to help programmers cope with complex data and processes. Other data structures include queues, trees, linked lists, and plain old arrays. If you've been programming for any length of time, you've probably been using stacks every day without even noticing it. All .NET languages, and most other compiled languages, use stacks to manage passing parameters between function calls. The .NET Framework includes a Stack class that implements an easy-to-use stack collection. In this article, I'll describe stacks and their use, and I'll demonstrate the Stack collection class through a sample program that implements a basic calculator.

A stack is known as a last-in, first-out, or LIFO, data structure. (By contrast, a queue is a first-in, first-out, or FIFO, structure.) You can add data objects one at a time to a stack, but the first one you pull back out is always the last one you put in. Hence, last in, first out. You can imagine a stack as basically a flat surface where you pile things on top of each other, like a stack of pancakes on a plate. As you add more pancakes, the stack gets taller. When you remove pancakes, you always remove the one on the top first to avoid disaster. When you've removed all the pancakes, the stack is empty.

In .NET, stacks are part of the larger System.Collections namespace. This namespace also includes many other useful data structures, including queues, sorted lists, arrays, hash tables, and dictionaries. The Stack class is especially useful for managing historical states of data. You can record the current state of data in an object, push the object on the stack, and retrieve it off the stack later to restore the data to its original state.

Stacks include three basic operations for managing items: *push*, *pop*, and *peek* (see Figure 1). (Some stack implementations include only push and pop; peek is optional.) The push operation adds an item or object to the top of the stack. Pop removes an item from the top of the stack and returns it to you to use. Peek also lets you examine the top-most item, but the item remains on the stack until the pop operator removes it. The .NET class implementation of the stack also includes a Count method, which returns the number of items currently on the stack, and a ToArray method, which converts the stack elements to an array. Ordinarily, you can examine only the top-most item on the stack through peek or pop operators. Converting the stack to an array lets you examine any stack item without actually disturbing the stack structure.

One of the most famous uses of stacks in the computer science realm is the Towers of Hanoi puzzle, which requires you to move a stack of different-sized discs from the first of three pegs to the third peg, moving the discs one at a time (see Figure 2). The catch is that you can never put a larger disc on top of a smaller disc. It turns out that the number of moves increases exponentially as you increase the number of discs. As far as implementation goes, the three pegs can be implemented with three stacks, each holding a set of objects that indicate disc widths. To move a disc from one stack to another, you "pop" the disc object off of one stack and "push" it onto the new stack. The statement to move a disc from tower 1 to tower 3 might look like this in Visual Basic .NET:

Stack3.Push(Stack1.Pop())

Use a Stack to Track Numbers

The sample application for this article implements a simple calculator (see Figure 3). It contains most of the basic functions you would expect in a calculator, but it uses postfix notation (also known as Reverse Polish Notation, or RPN) for its entry system. Most calculators use infix notation, where the basic operators come in between their two operands:

2 + 3

In postfix notation, the operator appears after the operands:

2 3 +

To make this system work, postfix calculators include an Enter key to indicate that you're finished with the entry of the first number. Use these keystrokes to add 2 and 3 on an RPN calculator:

2 Enter 3 +

The Enter key actually pushes the value of 2 onto the calculator's stack. Operators, such as the addition (+) operator, pop their operands off of the stack, perform the operation, then push the result back onto the stack. (The onscreen value is considered the top of the stack.) You can operate on a bunch of numbers by pushing them all onto the stack at once, then using the operators. Also, parenthetical operations are performed by ordering operations correctly and pushing results onto the stack at key moments. For instance, use this sequence to calculate "(2+3)*(4+5)":

2 Enter 3 + Enter 4 Enter 5 + *

The sample application uses a single stack to keep track of all the numbers. The displayed value, although considered to be the top of the calculator's logical stack, is not actually placed on the true Stack class, but all other values are. The first step in your calculator form's class is to define a stack to use:

Private NumberStack _ As System.Collections.Stack Private ActiveEntry As Boolean

The ActiveEntry value helps the program manage keypad entry of data. The form initializes the stack during the form's Load event:

NumberStack = _ New System.Collections.Stack ActiveEntry = False

As I mentioned earlier, the displayed value is kept off of the stack proper. Instead, you simply manipulate that value right in the display text field. For instance, when you enter digits for a new number, simply append digits onto the currently displayed text, with some special code for decimal points. The shared HandleDigit_Click event handles this logic (see Listing 1).

The Enter button's Click event pushes the displayed value onto the true stack:

' ----- Convert the display to decimal. Dim newValue As Decimal _ = CDec(CalcDisplay.Text) ' ----- Push the number onto the stack. NumberStack.Push(newValue) ActiveEntry = False

Implement Operators

You can now enter and store numbers, so start implementing the operators. There are two basic types: single-operand and dual-operand. The single-operand operators are simple because they work only on the displayed value, and they return the result back to the display; the NumberStack object is not involved at all. For example, you'd implement the square-root single-operand feature like this:

Private Sub OpSquareRoot_Click(...) _ Handles OpSquareRoot.Click ' ----- Get the value to adjust. Dim theValue As Decimal = _ CDec(CalcDisplay.Text) ActiveEntry = False ' ----- Take the root of the value. theValue = _ CDec(Math.Sqrt(CDbl(theValue))) ' ----- Display the new value. CalcDisplay.Text = CStr(theValue) End Sub

For dual-operand operations, like addition, the program has to get one value from the top of the NumberStack object. If the stack is empty, a value of zero is used instead for that operand:

Private Sub OpAdd_Click(...) _ Handles OpAdd.Click ' ----- Add two values. Dim valueOne As Decimal Dim valueTwo As Decimal ' ----- Get the values to use. ActiveEntry = False valueOne = CDec(CalcDisplay.Text) If (NumberStack.Count = 0) Then _ valueTwo = 0D Else valueTwo = _ CDec(NumberStack.Pop()) ' ----- Display the new value. CalcDisplay.Text = _ CStr(valueOne + valueTwo) End Sub

You reduced the operands from two to one, so you don't need to push anything back onto the physical stack after the operation.

The calculator also includes a feature to display the contents of the physical stack (excluding the onscreen display value) through a click on the InfoDisplay label. You can use the ToArray method to convert the impenetrable stack to an easy-to-peruse array (see Listing 2).

Next to the array, the stack is probably the easiest data structure you'll use in your programs. Its operators are simple, yet they provide the power to manipulate your data in useful ways.

About the Author

Tim Patrick has spent more than thirty years as a software architect and developer. His two most recent books on .NET development -- Start-to-Finish Visual C# 2015, and Start-to-Finish Visual Basic 2015 -- are available from http://owanipress.com. He blogs regularly at http://wellreadman.com.