Building Stacks with VB.Net

Summary

The following article presents a general definition of the stack data structure and its most common functions.
This article explores a sample stack implementation as a .NET class in VB.Net, as well as some interesting usage
scenarios.

Introduction

.NET includes a Stack class inside the System.Collections namespace. It is efficient because it is implemented
using a System.Collections.ArrayList, so if you need to consume a stack, it is a better idea to use the built
in .NET stack class. Just for fun and for educational purposes, the following article presents a simple way to
implement a stack and sample stack consumers.

Definition

A stack is a data structure that allows to add and remove objects at the same position. The last object placed
on the stack is the first one to be removed following a Last In First Out (LIFO) data storing method.

Common functions

The most common functions to manipulate a stack are:

• Push(element): Adds a new object to the last position of the stack.
• Pop(): Returns and removes the last object of the stack.
• Peek(): Returns the last object without removing it.
• IsEmpty(): Validates if the stack is empty.

Implementation

There are many ways to implement a stack. I will use an array to keep the demonstration simple, even though
you might consider using a linked list to allow dynamic resizing. I will define the maximum size of the stack at
compilation time, but you might also define it at runtime. I will use an index to store the last object position
(bottom of the stack) at any time.

Each time a Push() operation is done, I validate if the stack has enough space, I increment the index, and add
the new object. Each time a Pop() operation is done, I validate if the stack IsEmpty(), I decrease the index,
and return the last object. Each time a Peek() operation is done, I validate if the stack IsEmpty(), and I return
the last object.

The following sample code illustrates a sample VB.Net stack implementation:

Imports System
Namespace DotNetTreats.DataStructures

Public Class Stack

Private Const MaxSize As Integer = 100
Private _items As Object() = New Object(MaxSize - 1){}
Private _currentIndex As Integer = -1

Public Sub New()
End Sub

Public Sub Push(ByVal element As Object)
If _currentIndex >= MaxSize-1 Then
Throw New InvalidOperationException("Stack is full")
End If
_currentIndex += 1
_items(_currentIndex) = element
End Sub

Public Function Pop() As Object
If IsEmpty() Then
Throw New InvalidOperationException("No elements in stack")
End If
Dim element As Object = _items(_currentIndex)
_items(_currentIndex) = Nothing
_currentIndex -= 1
Return element
End Function

Public Function Peek() As Object
If IsEmpty() Then
Throw New InvalidOperationException("No elements in stack")
End If
Return _items(_currentIndex)
End Function

Public Function IsEmpty() As Boolean
If _currentIndex < 0 Then
Return True
Else
Return False
End If
End Function
End Class
End Namespace

Listing 1. VB.Net Stack implementation.

Usage Scenarios.

Scenario 1: Simple consumer

Once the stack is implemented, a program can consume it. The following console application represents a simple
way to consume the stack.

Imports System
Namespace DotNetTreats.DataStructures

Friend Class stackconsumer

Public Sub New()
End Sub

<STAThread> _
Shared Sub Main(ByVal args As String())
'simple stack consumer
Dim stack As Stack = New Stack()
Dim x As Integer = 9
Dim y As String = "foo"
Console.WriteLine("Push 9")
stack.Push(x)
Console.WriteLine(stack.Peek().ToString())
Console.WriteLine("Push foo")
stack.Push(y)
Console.WriteLine(stack.Peek().ToString())
Console.WriteLine("Pop -> foo, 9 is at the top now.")
stack.Pop()
Console.WriteLine(stack.Peek().ToString())
'Expression validator
Dim eval As ExpressionValidator = New ExpressionValidator()
Console.WriteLine("Write an equation.")
Dim result As Boolean = eval.Validate(Console.ReadLine())
If result Then
Console.WriteLine("Valid")
Else
Console.WriteLine("Invalid")
End If
End Sub
End Class
End Namespace

Listing 2. VB.Net Stack consumer.

Scenario 2: Expression validation

Equations as well as some string expressions use parenthesis, braces and brackets to open and close parts of
the expression. Many programs require validating if in a given string expression, all the opening parenthesis have
a matching closing parenthesis (balanced expressions). Some compilers check if functions have balanced
opening and closing brackets. Some XML and HTML editors check if all the tags have a corresponding closing
tag.

To solve this kind of problems it is recommended to use a stack. The general idea is to parse a string character
by character. Each time an opening parenthesis or tag is found, a Push() operation is executed, and each time
a corresponding closing parenthesis or tag is found a Pop() operation is executed. If the program finishes
parsing the document and the stack IsEmpty() , the equation or expression is valid; otherwise, if the stack has
elements, then some matching parenthesis are missing and the expression is invalid.

The following sample represents an expression validation with a stack.

Initial expression: ((X+Y)-1)*2

The first parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.

1. The second parenthesis is parsed ((X+Y)-1)*2 and a Push() operation is executed.
2. A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.
3. A closing parenthesis is parsed ((X+Y)-1)*2 and a Pop() operation is executed.
4. The stack is empty so the expression is valid.

NOTE: THIS ARTICLE IS CONVERTED FROM C# TO VB.NET USING A CONVERSION TOOL. ORIGINAL ARTICLE CAN BE FOUND ON C# CORNER (WWW.C-SHARPCORNER.COM).