|
If you look at the .NET Framework documentation, you will be overwhelmed
with the amount of types that are there. There are over 7000+
types in the framework class library and they cater to all the
needs of computing ever envisaged. There are data structures for
representing collections, hash tables, dictionaries, network protocols
and so on…
The System.Collections namespace contains a series
of types for representing various types of collections, which
can be used to store objects of various types and retrieved according
to the access method dictated by the collection.
In this article, I'm going to look at the Stack
type that is present in the System.Collections
namespace and see how the stack can be used for programming tasks.
I will show some simple examples that show the operation of this
collection and then use these concepts to build upon an application
that will perform more meaningful tasks. But before we start on
the examples, some basics…
What is a Stack?
If you look at any book on data structures, a stack is defined
as a last in first out list. We will stick to
this definition and not complicate it further!
By last-in-first-out what we mean is, if a set of objects are
put into a stack, the last object that was put in, will be the
first object to be taken out. For example, if you see in restaurants
that have an automatic plate dispenser, a stack of plates are
kept and as each person takes a plate, the next plate in the stack
becomes available. Diagrammatically, this looks like the following:
The operation of putting an object into a stack is called push
and the operation of taking an object out of the stack is called
pop. Sometimes, it might be required to just "examine"
the top element from a stack without taking it out. This operation
is called peek. This simple data structure represents
a very common concept that we keep seeing/doing in our daily lives!!
There are many ways to program a stack. The traditional method has
been to represent a stack by means of an array (wrapped around a
class) and then provide methods that allow the operations discussed
above. If you are a Visual Basic programmer, you can see an implementation
at:
http://www.developersdomain.com/vb/articles/stack.htm
Rather than having various implementations of stacks floating around
by programmers, the .NET team has provided a type called Stack
that provides the above discussed features and operations and more.
Stack in .NET
In .NET, the stack type is present in the System.Collections
namespace. The following are the operations available to us on a
stack object.
| Public Constructors |
|
| Stack Constructor |
This is an overloaded constructor that initializes a stack. |
| Public Properties |
|
| Count |
This property gets the number of elements in the stack. |
| IsSynchronized |
Gets a value indicating whether access to the Stack is synchronized
(thread-safe). |
| SyncRoot |
Gets an object that can be used to synchronize access to
the Stack. |
| Public Methods |
|
| Clear |
Removes all objects from the Stack. |
| Clone |
Creates a shallow copy of the Stack. |
| Contains |
Determines whether an element is in the Stack. |
| CopyTo |
Copies the Stack to an existing one-dimensional Array, starting
at the specified array index. |
| GetEnumerator |
Returns an IEnumerator for the Stack. |
| Peek |
Returns the object at the top of the Stack without removing
it. |
| Pop |
Removes and returns the object at the top of the Stack. |
| Push |
Inserts an object at the top of the Stack. |
| Synchronized |
Returns a synchronized (thread-safe) wrapper for the Stack. |
| ToArray |
Copies the Stack to a new array. |
| All collections also inherit from System.Object.
Therefore all the methods from the base class are also available
for access. |
We will not see examples of all the above methods, but only see
the important ones. For more information on each of these methods,
see the .NET Framework documentation.
A Simple Stack Example
Ok, enough of the basics. Let's get down to work. Fire up Visual
Studio .NET and choose Console Application (Visual
Basic .NET) as the project type and type in the following code into
the editor.
Imports
System.Collections
Module TestModule
Sub
Main()
'
Declare and initialize a stack type
Dim
oStack As Stack
oStack
= New Stack
'
Push some elements into the stack. Note that this
'
can be any object
oStack.Push("1")
oStack.Push("2")
'
Print some statistics about the stack
Console.WriteLine("Stack
Count = {0}", oStack.Count())
Console.WriteLine("Top
Element = {0}", oStack.Peek())
Console.WriteLine("Get
First Element = {0}", oStack.Pop())
'
Clear the contents of the stack
oStack.Clear()
'
Print some statistics about the stack
Console.WriteLine("Stack
Count = {0}", oStack.Count())
'
Wait for some console input so that we can see the output
from
'
the above lines
Console.Read()
End
Sub
End Module |
Note that I've changed the module name to TestModule. This means
that you have to change the VS.NET project properties to set the
startup object as TestModule.
And that's it!! We have a stack implemented. The output of the program
will be as follows:
So what did we do? We created a stack and then pushed two items
into it using the push method. Then, using some
of the stack object methods, we print some details about the stack.
Note that the peek method did not remove the top
element. Finally, we clear the stack and print
the count and its 0, indicating that the stack is now empty.
That was a very simple example that showed some details about the
stack. Now, let's build a more interesting application.
The Reverse Polish Notation Calculator
In this section, we are going to build a simple calculator application
that well, adds and subtracts numbers (there are more sophisticated
calculators in the market, but we are going to keep it simple!!).
The method that we are going to use to represent the calculator
object is by using a notation called the reverse polish notation.
You can find more details about this at: http://www.calculator.org/rpn.html.
Essentially, in the polish calculator, the various operators and
operands are "pushed" and "popped" from a stack
to obtain the results. To start with, as and when we encounter numbers,
we "push" them onto the stack and when we start encountering
operators, we "pop" the values from the stack, do the
operation and "push" the result onto the stack. So let's
take a simple example: Say we want to evaluate the expression (3
+ 5) * (7 – 2). In the RPN calculator, this expression would
be represented as 3 5 + 7 2 - * and from a programming perspective
would be made of the following steps:
| 1. |
Push 3 onto the stack. |
| 2. |
Push 5 onto the stack. The stack now contains (3, 5). |
| 3. |
Apply the + operation: take the top two numbers off the
stack, add them together, and put the result back on the stack.
The stack now contains just the number 8. |
| 4. |
Push 7 onto the stack. |
| 5. |
Push 2 onto the stack. It now contains (8, 7, 2) |
| 6. |
Apply the - operation: take the top two numbers off the
stack, subtract the top one from the one below, and put the
result back on the stack. The stack now contains (8, 5) |
| 7. |
Apply the * operation: take the top two numbers off the
stack, multiply them together, and put the result back on
the stack. The stack now contains just the number 40 |
This looks pretty interesting, right? So let's model a .NET class
for doing this operation for us. In the VS.NET project opened earlier,
right click and add a new class module (called
PolishCalc). Paste the code from the following
snippet onto the editor.
' This class is used to evaluate a reverse
polish notation calculator
Imports System.Collections
Public Class PolishCalc
Private oStack As
Stack
' A constructor that takes no
argument
Public Sub New()
' Initialize the internal
stack for use
oStack = New Stack
End Sub
' Fetch the result from
the stack. Note that the top element from the
' stack is returned without
removing it
Public ReadOnly Property
Result()
Get
Return
(oStack.Peek())
End
Get
End
Property
' This function will evaluate
an expression that is expressed in the
' reverse polish notation.
For example: 35+27-*
Public
Function
Evaluate(ByVal Expression As
String) As Integer
Dim
nLength As Integer, i As
Integer, nValue As Integer
Dim
strValue As String
nLength = Expression.Length()
For
i = 0 To (nLength - 1)
'
Get the character at the required position
strValue
= (Expression.Chars(i)).ToString()
' Evaluate the expression that was fetched
Select
Case strValue
Case
"+"
'
Retrieve two values from the stack, calculate the sum
'
and push the result back
nValue = CType(oStack.Pop(),
Integer) + CType(oStack.Pop(),
Integer)
oStack.Push(nValue.ToString())
Case
"-"
'
Retrieve two values from the stack, calculate the difference
'
and push the result back
nValue = CType(oStack.Pop(),
Integer) - CType(oStack.Pop(),
Integer)
oStack.Push(nValue.ToString())
Case
"*"
'
Retrieve two values from the stack, calculate the product
'
and push the result back
nValue = CType(oStack.Pop(),
Integer) * CType(oStack.Pop(),
Integer)
oStack.Push(nValue.ToString())
Case
Else
'
It will be a number, so push it onto the stack
oStack.Push(strValue)
End Select
Next
End
Function
' Clear the
polish calculator
Public
Function
Clear()
oStack.Clear()
End
Function
End Class |
The above code represents a simple calculator with 3 operations
(+, - and *). As mentioned in the polish specification, we use a
stack to model all out operations. The result of the expression
is available as a read-only property called Result.
Note that we use the peek function to return the
result, since we want the last result to be available in the stack
for any other operations. Finally, we have a clear
method that allows us to start all over again.
Ok, let's test our code. Go back to the console application in the
VS.NET solution window and type in the following code.
Imports
System.Collections
Module TestModule
Sub
Main()
'
Initialize our polish calculator
Dim
oPolish As PolishCalc
oPolish
= New PolishCalc
'
Evaluate a simple expression and print the results
oPolish.Evaluate("35+27-*")
Console.WriteLine("Result
= {0}", oPolish.Result)
'
Work on the previous result
oPolish.Evaluate("5+")
Console.WriteLine("Result
= {0}", oPolish.Result)
'
Clear our calculator
oPolish.Clear()
' Wait for some input so that we can
see the results in the
'
output window
Console.Read()
End
Sub
End Module |
The output from the previous program would be 40 and 45. Since the
Result property does not remove the latest value
from the stack, we are able to add another expression to it.
Advanced Concepts
The above representation of the stack worked well because you were
the only one accessing it. If you deployed this application and
had multiple threads working on this stack, then how do you guarantee
that other threads do not read off the stack or manipulate it when
you are working on it? The answer is to use synchronization. The
stack class provides properties and methods that will help you to
synchronize access to the stack while accessing it. A sample access
method would be:
SyncLock
oStack.SyncRoot
' Do the operations
here
End SyncLock
The above code lets you perform thread safe operations on the stack
so that you do not encounter sudden exceptions. For more information,
see the .NET Framwork documentation.
What's Next?
Well, if you are adventurous and want to learn .NET more, you could
try a lot of things in this program. Here are some of my thoughts…
| 1. |
Implement error handling in the pop and
push operations. |
| 2. |
Handle numbers greater than 10. Our calculator does not
handle this, since we split the string character-by-character. |
| 3. |
Handle other operations like dividing, modulus etc. |
| 4. |
Handling floating point numbers. |
| 5. |
And many more…. All the best!! |
Conclusion
The System.Collections is a vast namespace and
we have seen the application of just of one its types called Stack.
In the future articles, I will touch upon the other collection types
that are more interesting.
For comments and suggestions on this article and on articles that
you might want me to explore, mail me at: srisamp@hotmail.com.
|
