Wednesday, 10 July 2013

Microsoft internel implementation of Stack C# - Data Structure and Algorithm



What is the usage of Data structures in programming?        
      Data structures are used to store the Data in formatted manner and process the data in algorithm way

         Data structure used by an algorithm can greatly affect the algorithm's performance, it is important that there exists a rigorous method by which to compare the efficiency of various data structures. What we, as developers utilizing a data structure, are primarily interested in is how the data structures performance changes as the amount of data stored increases. That is, for each new element stored by the data structure, how are the running times of the data structure's operations effected?

Now Let we take the Example of Stack 

        Stack which follows the LIFO algorithm , LIFO means the data which is inserted last can be taken first from the collection. Real time example is Place the CD's in CD Pouch and take it back .

Stack have 2 Operations Push (insert the data into the stack), Pop (remove and returns the last item from stack)






In C# Stack Example :

using System.Collections;

class Program
    {     
        public static void Main(string[] args)
        {                 
            Stack sample=new Stack();
            sample.Push("Rajesh");
            sample.Push("Suresh");     
            string name=sample.Pop().ToString();
            Console.WriteLine(name);
            Console.Read();
        }

    }

Output : Suresh 


In this stack one dis-advantage is we have to cast the value from object to our type. It is not a Generic Stack.

Let we see how Microsoft implemented this class in .Net FrameWork, Now we see the internals of this class detailed. Not all the Stuff. we can see the Methods  Push,Pop, Contains,Clear and make the stack to iterate the values in foreach. by Implement the Enumertor.


From the below screenshot we can see that custom stack have few 4 methods and one property




calling part of custom stack, In the following code I am inserting a few objects to the stack and remove an object from the top of the stack.  Always objects are removed from Top of the stack.





Output of the Above code



From the output you can see that name "Ramu" is removed and return from the top of the stack,Values are returning in the Format of LIFO Raju is last inserted but it is printed first.then Suresh, Rajesh.

Code for the User Defined Stack : Which follows the LIFO Algorithm


namespace Custom
{



using System;
using System.Collections;

    class Stack:IEnumerable
    {

        private object[] _array;

        private int _size;

        private int _version;

        private const int _defaultCapacity = 10;

        public class StackEnumerator:IEnumerator
        {
            private Stack _stack;
            private int _index;
            private int _version;
            private object _curelement;

            public StackEnumerator(Stack stack)
            {
                this._stack = stack;
                this._version = this._stack._version;
                this._index = -2;
                this._curelement = null;
            }

            public virtual object Current
            {
                get 
                {

                    if (this._index == -2)
                    {
                       throw new InvalidOperationException("Enum not started");
                    }
                    if (this._index == -1)
                    {
                        throw new InvalidOperationException("Enum ended");
                    }

                    return this._curelement;
                
                }
            }

            public virtual bool MoveNext()
            {
                bool flag;
                if (this._index == -2)
                {
                    this._index = this._stack._size;
                    flag = (--this._index >= 0);
                    if (flag)
                    {
                        this._curelement = this._stack._array[this._index];
                    }
                    return flag;
                }
                if (this._index == -1)
                {
                    return false;
                }
                flag = (--this._index >= 0);
                if (flag)
                {
                    this._curelement = this._stack._array[this._index];
                }
                else
                {
                    this._curelement = null;
                }
                return flag;
            }

            public virtual void Reset()
            {
                this._index = -2;
                this._curelement = null;
            }
        }

        public virtual int Count
        {
            get { return this._size; }
        }

        public Stack()
        {
            this._array = new object[_defaultCapacity];
            this._size = 0;
            this._version = 0;
         }
        

        public Stack(ICollection col):this((col==null)? 32 : col.Count)
        {
            if (col == null)
                throw new ArgumentNullException("col");

            IEnumerator enumerator = col.GetEnumerator();
            while (enumerator.MoveNext())
            {
                this.Push(enumerator.Current);
            }
        }

        public Stack(int capacity)
        {
            if (capacity < 0)
            {
                throw new ArgumentNullException("capacity is less than Zero");
            }

            if(capacity>10)
            {
               this. _array = new object[capacity];
            }
            else
            {
                this._array = new object[_defaultCapacity];
            }
            this._size = 0;
            this._version = 0;
        }

        public virtual void Clear()
        {
            Array.Clear(this._array, 0this._size);
            this._size = 0;
            this._version++;
        }

        public virtual bool Contains(object obj)
        {
            int size = this._size;
            while (size-- > 0)
            {
                if (obj == null)
                {
                    if (this._array[size] == null)
                    {
                        return true;
                    }
                }
                else
                {
                    if (this._array[size].Equals(obj))
                        return true;
                }
            }
            return false;
        }

        public virtual void Push(object obj)
        {
            if (this._size == this._array.Length)
            {
                Array.Resize(ref this._array, 2 * this._array.Length);
            }
            this._array[this._size++] = obj;
            this._version++;
        }

        public virtual object Pop()
        {
            if (this._size == 0)
            {
                throw new InvalidOperationException("there is no element to remove from stack");

            }
            this._version++;
            object result = this._array[--this._size];
            this._array[this._size] = null;
            return result;
        }

        public IEnumerator GetEnumerator()
        {
            return new StackEnumerator(this);
        }

    }

}



From this article we can learn the Stack implementation and usage of algorithm in that.