Post
Ask Question

Introduction To Data Structures

Data structure is the heart of any programming language. Back in the days of C, all complex data structures, such as stack, linked list, queue etc., were hand coded. Writing code not only required in depth study of those data structure but also a lot of time in implementing and testing. Now, with sophisticated programming languages, they are all available ready made.

Nevertheless, I shall describe the intricacy involved in developing these data structures and a few Nunit test cases to validate what has been implemented.

In the list of data structures, first is stack.

Stack:

A stack is a data structure that follows last in first out (LIFO) strategy. The elements entered last would be the first one to come out from the list of elements. There are two operations on stack:

  1. Push (d): inserts element d in the list.
  2. Pop: remove /deletes the last element inserted from the list.

You may find several stack implementations on the internet but many of them tried growing the list of elements to double its size when the max limit is reached. The consequences of a growing list are that it gives a user a possibility to call a Pop operation more times than the number of elements in the list. Ideally, Pop should stop when the stack has hit its bottom i.e. the last element (the very first entered).

Let me give some technical details on how can it be achieved:

Push method takes an element and inserts the element in an array and currentIndex;  it records the current location of the element. As soon as currentIndex reaches to the length of the array, the size of the array is increased by one.

  1. /// <summary>  
  2. /// Pushes data on to top of stack  
  3. /// </summary>  
  4. /// <param name="data"></param>  
  5. public void Push(T data)  
  6. {  
  7.     if (_currentIndex == _stackCollection.Length)  
  8.     {  
  9.         Array.Resize(ref _stackCollection, _stackCollection.Length + 1);  
  10.     }  
  11.   
  12.     _stackCollection[_currentIndex++] = data;  
  13. }  
  14.   
  15. /// <summary>  
  16. /// removes an element from array and resizes it  
  17. /// </summary>  
  18. /// <returns></returns>  
  19. public T Pop()  
  20. {  
  21.     if (_currentIndex == 0)  
  22.         throw new InvalidOperationException("The stack is empty");  
  23.   
  24.     var value = _stackCollection[--_currentIndex];  
  25.     Array.Resize(ref _stackCollection, _stackCollection.Length - 1);  
  26.     return value;  
  27. }  
Similarly, Pop method removes the element that was inserted first and _currentIndex, the cursor, is decremented to the previous element (last but second) and the array is resized; size is reduced by one.

To validate two methods, I have written two unit test cases. Here they are for your understanding:
  1. To check if number of elements are correct in thecount even if a pop operation is called in between.
    1. [TestCase]  
    2. public void TestPushItem()   
    3. {  
    4.     IStack < int > stack = new StackImpl < int > (120);  
    5.   
    6.     stack.Push(20);  
    7.     stack.Push(30);  
    8.     stack.Push(40);  
    9.     stack.Pop();  
    10.     stack.Push(50); // <== Top Element   
    11.   
    12.     var count = stack.Count();  
    13.   
    14.     Assert.AreEqual(4, count);  
    15. }  
  2. The second test case is to check the top element after executing a couple of operations:
    1. [TestCase]  
    2. public void TestTopElement()  
    3. {  
    4.     IStack < int > stack = new StackImpl < int > (120);  
    5.   
    6.     stack.Push(20);  
    7.     stack.Push(30);  
    8.     stack.Push(40);  
    9.     stack.Pop();  
    10.     stack.Push(50); // <== Top Element   
    11.   
    12.     Assert.AreEqual(50, stack.Pop());  
    13.     Assert.AreEqual(30, stack.GetTop());  
    14. }  

For more details, have a look at the project attached.

Read more articles on Data Structures:


Similar Articles