Implementing a Stack using a dictionary

Rate this article

Loading ...

March 29th, 2008 by

Yaron Assa

Print This Post

In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. The stack is ubiquitous.<>

To all that already read the Queue implementation, The Stack implementation The stack implementation is a lot simpler, as only the pointer to the last element is needed. In this case, we use the entry: 'next’, which points to the location where the next 'push’ to the stack should place the element to.

Class clsStack

Private m_stack ' Dictionary Private member

' ** Class Constructor

Private Sub Class_Initialize

Set m_stack = CreateObject( "Scripting.Dictionary" )

m_stack.Add "next", 0

End Sub

' ** Class Destructor

Private Sub Class_Terminate

If m_stack.Count > 0 Then

m_stack.RemoveAll

End If

Set m_stack = Nothing

End Sub

' Add Properties Here

' Add Methods Here

End Class

The only one member required for the task is the m_stack, it will hold the Scripting.Dictionary object

When the class is first created, the Dictionary object is initialized with the entry "next" with the value zero, means that the stack is empty.

when the class is terminated, the m_stack removes all items before disposing the object.

Public Property Get Count()

Count = CLng( m_stack( "next" ) )

End Property

The first public read-only property is Count. the Count property gets the number of elements contained in the Stack. the dictionary count always have more keys that the stack actual size ( by one ), so in fact the value of the key "next" will determine the size. the Conversion to CLng is not required, but will promise a numeric return value

Public Property Get IsEmpty()

IsEmpty = CBool( Me.Count = 0 )

End Property

Another useful property is IsEmpty. when looping the stack IsEmpty will return True, when Count = 0 and False otherwise.

Public Sub Push( ByVal data )

m_stack.Item( m_stack.Item( "next" ) ) = data

m_stack.Item( "next" ) = CLng( m_stack.Item( "next" ) ) + 1

End Sub

The main method of a Stack is the Push action. it actually Adds an object to the head of the Stack. when using the dictionary here’s the trick: the "next" entry is now logically points to the new entry. so that in fact the object is not added to the head of the Stack. the CLng function is to assure that an arithmetic calculation would take place.

Public Function Pop()

If Me.IsEmpty Then

Reporter.ReportEvent micFail, "Stack", "The Stack is empty"

Pop = Empty

End If

Pop = m_stack.Item( m_stack.Item( "next" ) - 1 )

m_stack.Remove m_stack.Item( "next" ) - 1

m_stack.Item( "next" ) = CLng( m_stack.Item( "next" ) ) - 1

End Function

The second main method of a Stack is the Pop action. the Pop method removes and returns the object at the head of the Stack. when using the dictionary here’s the trick: the Dictionary returns the value pointed by "next" - 1, and then removes the same item from the Dictionary.

Public Function Peek()

If Me.IsEmpty Then

Reporter.ReportEvent micFail, "Stack", "The stack is empty"

Peek = Empty

End If

Peek = m_stack.Item( m_stack.Item( "next" ) - 1 )

End Function

A utility method, that I thought can be also useful in some cases is the Peek method. The Peek method returns the object at the head of the Stack without removing it. very similar to Pop.

Public Sub Clean()

If Not Me.IsEmpty Then

m_stack.RemoveAll

m_stack.Add "next", 0

End If

End Sub

Another utility method, that I thought can be also useful in some cases is the Clean method. The clean method just removes the contents of the Dictionary, and initialize the Dictionary again with "next" = 0. is more easy to remove all and then add the first key.

Public Function Clone()

Dim m_cloned, key

Set m_cloned = CreateObject( "Scripting.Dictionary" )

For Each key in m_stack.Keys

m_cloned.Add key, m_stack( key )

Next

Set Clone = m_cloned

End Function

This utility and the following one, are inspirations received from the Dot.Net framework, so if it’s good for Dot.Net , is also good for QTP.

When Cloning( Creates a shallow copy of the Stack. ) you just can’t say Set m_clone = m_stack ( inside the class ) because after setting the class to Nothing, m_clone will be vanish.

That’s the main idea of clone. The clone should "live" after the cloned object "died". that’s why, a creation of a new Dictionary is required, and each item has to be copied to the new one.

Public Function ToArray()

Dim m_cloned

Set m_cloned = Me.Clone()

m_cloned.Remove( "curr" )

m_cloned.Remove( "next" )

ToArray = m_cloned.Items

End Function

in my last utility, again, an inspiration of Dot.Net, is the ToArray method. this method take an advantage of the Clone method. why cloning? because displaying the array, will also display the "curr" and "next" items, so they need to be removed. but, we don’t want to destroy the original one.

HOW IT WORKS?

Set stack = New clsStack

Print "stack.Count : " & stack.Count ' Prints zero

Print "stack.IsEmpty : " & stack.IsEmpty ' Prints True

' ** Adding a value

stack.Push "Message 1″