Implementing Stacks in C#

sami_danish
Dec 22, 2005
98.9k
0
0
Article

Description

With the help of C# we can also implement ADT (Abstract Data Types) with little effort. An example of ADT is a simple stack of integers. You can imagine stack like a placeholder where you can save something and later on retrieve in what so called LIFO (Last In First Out) fashion. You can do very useful operations with stacks like, to save something you can PUSH elements and to retrieve something you can POP, when you POP them they come in reverse order.

Before implementing our stack class, it is desirable to do some design. It would be nice to start with some pseudo-code or algorithm, so for those who are learning C# as beginner may understand the logic behind the code.

The companion pseudo-code or algorithm is shown below. A quick examination of the algorithm shows that the stack in our case trying to input an integer (PUSH) stores it and deletes (POP) the contents or data from successive array index on every iteration.

Pseudo-code for stack class

Let stack (array) S of integers, having top T as a top of stack. With MAXSIZE as the maximum size of the stack.

[Operation: PUSH]

1- Initialize top T := 0

2- Set MAXSIZE := integer (number)

3- [Iteration] While T < MAXSIZE , PUSH the elements on to stack S

4- Set top T := T + 1

[Operation: POP]

1- [Iteration] While T > 0 and less then MAXSIZE, POP elements from stack S

2- Set top T := T-1

Stack class overview

From the above code it is clear that the stack is nothing more then a placeholder to save something for temporary basis. Now it's time to do some real gymnastic and to design some serious classes, which can do something useful. Here is the stack class.

class Stack
{
Stack() // constructor
{}
void Push(<interger-type>) // stores data for you
{}
<interger-type> Pop(void) // deletes data on demand
{}
~Stack() // destructor
}

The code typed above is just an overview of the stack class, You can see that the stack class has a constructor where you can initialize members of your class (as you might know that C# will do this for you), a method Push which can take integer as a paramter and returns nothing, a method Pop which returns integer as a returning type and in the last a destructor which can be called after the function Main().

Stack class implementation

using System ;
class Stack
{
public Stack()
{
_top = 0 ;
}
private _top ;

The constructor (having same name as that of class) initializes the variable _top to zero, because initially the stack is empty so that the top of stack must point to zero. As you can see that we have declared the _top as private, the reason to do this is that we don't want anyone to modify it directly instead with a method of the class. This feature of C# will make sure that the user will not accidentally vary the value for which he has to pay.

using System;
class Stack
{
public Stack()
{
_top = 0 ;
}
private _top ;
public int const maxSize = 10 ;

As shown in the above code snippet the maximum size of the stack is defined by maxSize and in our case it is 10.

public int const maxSize = 10 ;

The modifier const tells the compiler that the maximum size will never change through out the program lifetime. This maxSize will become more helpul as we proceed.

using System ;
class Stack
{
public Stack()
{
_top = 0 ;
}
private _top ;
public int const maxSize = 10 ;
private _arr[maxSize] ;

Now comes the _arr[maxSize], this array is of type integer and we have restrict its size to maxSize i.e 10. We have also declared it as private so nobody can harm it. The size of the array has also been declared as of type integer constant, this makes efficiency in defining explicit size of the array. The _arr[] array is the heart of the program, the reason is that whatever operation you perform with the stack class directly effects the array.

Operation PUSH

Now let's have a look at the implementation of method Push and Pop:

using System ;
class Stack
{
public Stack()
{
_top = 0 ;
}
private _top ;
public int const maxSize = 10 ;
private _arr[maxSize] ;
void Push(int val)
{
if (_top < maxSize)
{
_arr[_top] = val ;
++_top ;
}
else
{
break ;
}
}

In C# if one wants to execute several statements in a single condition, a block is being used to represent it. And if the condition met than the statement(s) inside the block executed one by one.

As you will see that stack class uses Push method to push values on to stack, it takes integer type as argument (as the stack is of type integer). A common approach is to determine that the stack is empty or not? This can be determined very easily by evaluating the expression:

if (_top < maxSize)

and if there is room than the evaluation returns true. On success the value contained by the variable val will be moved on to the stack and also the top of stack will be updated. This will continue until the expression evaluates to false or the _top of stack is greater then the maxSize of the stack.

Operation POP

The stack class uses method Pop to deletes the data ( in other words throw the data to the bit bucket) one by one and in reverse order, means that the one come last will Pop first and so on.

The method Pop works in the way that as long as the _top of stack is greater then zero and less then the size of array i.e. maxSize the code inside the block pops-up the values on every iteration plus updates the _top of stack. Note that until the expression evaluates to false, it iterates and when it encounters false condition it terminates and exits the if-block.

public static int Main(void)
{
Stack stack = new Stack() ;
}

People who have come from C/C++ and java programming environments must know the importance of the method Main().You can also write this method in different flavors where it is desirable.

In order to use our class in the Main() function, it is desirable to create an object or instantiates the class stack. The operation behind the initiation is very interesting. When we create an object of any class the compiler creates a hash value for that object and kept it in the hash table. The object is actually created on the heap memory as long as the object created with the help of operator new; now the compiler is responsible to garbage collected that object and reclaimed the memory as soon as the reference count of that object become zero.

Now it's time to fill the stack (integer array) with the data, for this we have run a for loop which starts from zero and goes to n-1, as C-type languages begins from zero and ends at n-1. With the help of C#'s magical static function WriteLine we can print the messages as well as insert the data on to the stack as described in the above code. In the above code we have used the Console.WriteLine function to echo back the inserted data.

public static int Main(void)
{
Stack stack = new Stack() ;
int i = 0 ;
for (; i<stack.maxSize; ++i)
{
Console.Write("Pushing [" + stack.Push(i+10)+ "]") ;
Console.WriteLine(" now Top becomes: " + stack._top) ;
Console.WriteLine() ;
}
int j = 0 ;
for (; j<stack.maxSize; ++j)
{
Console.Write("Popping [" + j + "] of " + stack.maxSize) ;
Console.WriteLine("Content: " + stack.Pop()) ;
}
return 0 ;
}
}

There is more then push, it's pop, which pops the data from the stack (array of integers) in reverse fashion and iterates until the maxSize reached. Again the Console.WriteLine function echoes the messages on the standard output or screen.