Stack data structure implementation

Question

I have implemented in C# a stack data structure, without using any existing C#/.NET containers (data structures). I have used TDD technique to implement this requirements, so you can find tests, too. All my tests are passing, so I guess stack is behaving correctly.

I would be very pleased to have a code review for this implementation.

Please do not recommend a generic implementation :-)

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using StackDataStructure;
namespace StackTesting
{
 [TestClass]
 public class Tests
 {
 [TestMethod]
 public void TestEmptyStackSize()
 {
 var stack = new Stack();
 Assert.IsTrue(stack.IsEmpty());
 }
 [TestMethod]
 [ExpectedException(typeof(InvalidOperationException))]
 public void EmptyStackPopException()
 {
 var stack = new Stack();
 stack.Pop();
 }
 [TestMethod]
 public void PushingAndPoppintItemsToStack()
 {
 var stack = new Stack();
 stack.Push(1);
 Assert.AreEqual(1, stack.Size);
 stack.Push(2);
 Assert.AreEqual(2, stack.Size);
 Assert.AreEqual(2, stack.Pop());
 Assert.AreEqual(1, stack.Size);
 Assert.AreEqual(1, stack.Pop());
 Assert.IsTrue(stack.IsEmpty());
 Assert.IsTrue(stack.Size == 0);
 stack.Push(10);
 Assert.IsTrue(stack.Size == 1);
 Assert.IsTrue(10 == stack.Pop());
 Assert.IsTrue(stack.IsEmpty());
 }
 }
}

---

using System;
namespace StackDataStructure
{
 internal class Node
 {
 internal int value;
 internal Node underTop;
 }
 public class Stack
 {
 private int size;
 private Node top;
 public int Size { get { return size; } }
 public bool IsEmpty()
 {
 return top == null;
 }
 public int Pop()
 {
 if (IsEmpty())
 throw new InvalidOperationException("Stack is empty");
 int value = top.value;
 top = top.underTop;
 size--;
 return value;
 }
 public void Push(int v)
 {
 top = new Node{
 value = v,
 underTop = top
 };
 size++;
 }
 }
}

Answer 1

The code and the test look very good. I only found these nit-picks:

• There's a typo in the method name Poppint.
• The test sometimes uses Assert.IsTrue(a == b), which should be Assert.IsEqual(a, b).
• The name underTop does not sound perfect to me, since it refers to a top, which is meaningless for a single node. A single node doesn't have a top, therefore I would call it next or below.
• The property Size should be renamed to Count to align with the other collection types.
• I prefer to have the same namespace for the main code and the testing code. But I don't know the official convention for organizing tests.

Answer 2

Even though it's internal in its own namespace, I'd make the Node class immutable (readonly members), and provide an explicit constructor. This expresses the intent more than just making it internal, which is liable to create issues if the code is copied or moved somewhere else, and doesn't protect the class from errors in the same namespace. This is tidily done with C# 6 read-only auto properties or the readonly keyword (the former is generally preferred because it allows you to provide a custom getter in the future without breaking the interface).

If it is truly exclusive to the Stack then it might as well be a nested-class (guidelines suggest you shouldn't expose nested classes, but this will be private, so it won't matter). Either way, a class should be self-contained, regardless of accessibility, and exposed members especially should be in ProperCamelCase.

internal class Node
{
 internal int Value { get; } // ProperCamelCase on exposed members
 internal Node UnderTop { get; } // C# 6 get-only properties are backed by a readonly field
 internal Node(int value, Node underTop) // explicit constructer prevents negligence and provides a clean, discoverable interface
 {
 Value = value;
 UnderTop = underTop;
 }
}

Regarding performance, making these readonly surely can't make matters worse, and will perhaps give the JIT more opportunities to optimise (which it may or may not exploit). The real benefit is that you have a self-contained class which you can't use incorrectly.

Answer 3

Which Side is the Top?

In my experience¹, stacks have tended to grow down, rather than up. As a consequence, your use of the variable name 'top' is a little confusing. For linked list stacks, like this, I tend to prefer 'current / head / items ' to represent the last pushed item. However as with all things name related it's somewhat subjective.

What Makes a Stack Empty?

If I build a collection that has a size variable, I'd tend to use this to determine if the collection is empty. This may seem a bit knit-picky, however it means that if you decide to change the way you store the items (say implement the stack in an array), the isEmpty function would be one less thing to change.

Test Naming

Your test class is simply named Tests. This obviously doesn't scale to testing multiple classes. If I'm testing a specific class then I tend to name the test class accordingly. In this instance StackTests might be appropriate.

Your test names also don't really reflect what it is the tests are testing. For example, your TestEmptyStackSize test contains two lines. The first creates a new instance of stack and the second asserts that the newly created stack returns true if IsEmpty is called. To me, this test should really be called NewStackShouldBeEmpty. This describes what is being tested (a new stack should be empty).

Reduce Test Noise

All of your tests start by creating a new empty stack. Consider promoting the stack to an instance variable and initializing it in a TestInitialize method. This removes some of the setup noise from your tests so that they become more concise.

Test Granularity

You have two essentially one-line tests and then you have PushingAndPoppintItemsToStack which seems to be testing too much. I would have broken this test up so that it was more obvious what the focus of the test was.

Taking the above into account, your tests might look more like this:

[TestClass]
public class StackTests
{
 const int knownValue = 5;
 Stack _stack;
 [TestInitialize]
 public void TestInitialize()
 {
 _stack = new Stack();
 }
 [TestMethod]
 public void NewStackShouldBeEmpty()
 {
 Assert.IsTrue(_stack.IsEmpty());
 }
 [TestMethod]
 public void StackWithValueShouldNotBeEmpty()
 {
 _stack.Push(knownValue);
 Assert.IsFalse(_stack.IsEmpty());
 }
 [TestMethod]
 public void NewStackShouldHaveNoSize()
 { 
 Assert.AreEqual(0, _stack.Size);
 }
 [TestMethod]
 [ExpectedException(typeof(InvalidOperationException))]
 public void PoppingEmptyStackShouldThrowException()
 {
 _stack.Pop();
 }
 [TestMethod]
 public void PushingShouldIncreaseSize()
 {
 _stack.Push(knownValue);
 Assert.AreEqual(1, _stack.Size);
 _stack.Push(knownValue);
 Assert.AreEqual(2, _stack.Size);
 }
 [TestMethod]
 public void PoppingShouldDecreaseSize()
 {
 _stack.Push(knownValue);
 _stack.Push(knownValue);
 _stack.Pop();
 Assert.AreEqual(1, _stack.Size);
 _stack.Pop();
 Assert.AreEqual(0, _stack.Size);
 }
 [TestMethod]
 public void PopShouldReturnPushedValue()
 {
 int[] knownValues = { 1, 2, 4, 50, 100 };
 int index = 0;
 for(index=0;index<knownValues.Length;index++)
 {
 _stack.Push(knownValues[index]);
 }
 for(;index>0;index--)
 {
 Assert.AreEqual(knownValues[index - 1], _stack.Pop());
 }
 }
}

_{1: My experience is primarily with 8086 cpus, where the push instruction decrements the stack pointer (the stack grows down). In the real world on the other hand, stacks or piles tend to grow up. However this discrepancy can create confusion, which is why I've suggested avoiding the name.}

• VisualMelon: +1, but I don't agree with the naming regarding the top of the stack. The linked question is about implementation of call stacks, and in my experience the conceptual top has always been the last element added (as per stacks in the real world, which definitely do grow up) (P.S. thanks for your edit to my answer)
• forsvarir: @VisualMelon Call stacks are based on the underlying implementation. My experience is primarily with 8086 cpus, where the push instruction decrements the stack pointer (the stack grows down). I agree that in the real world stacks or piles tend to grow up, however this discrepancy can create confusion, which is why I've suggested avoiding the name. For linked list stacks, like this, I tend to prefer 'current / head / items' to represent the last pushed item. However as with all things name related it's somewhat subjective.
• VisualMelon: I quite agree: perhaps add an alternative suggestion (like 'current'; 'head' and 'tail' scream queue to me) to the answer? It feels like you might be advocating 'bottom' at the moment, though I understand now that wasn't your intent. Personally I think top is fine, because it does relate to the real world model, and being a high-level programmer I perhaps see things more conceptually as cause.

Answer 4

int value = top.value;
top = top.underTop;

You should add two more steps to this so that the node that has just been popped isn't connected to anything else and can be garbage collected:

var value = top.value;
var tmp = top;
top = top.next;
tmp.next = null;

• Joan Dimko: It will reduce performance. In memory/speed trade-off requirement prefers speed.
• t3chb0t: @JoanDimko mhmmm... it'd be nice to know how much the performance drops by those two lines... 3ns per 10_000_000 calls? Did you forget to add the performance tag? ;-)
• t3chb0t: @JoanDimko do you have or did you do any performance tests?
• VisualMelon: I don't think this is a reasonable suggestion: it adds 2 lines of code that have no logical purpose (just add noise to the code), and I'm less than convinced they provide any benefit whatsoever (certainly shouldn't if the node is still in Gen0). If nothing is pointing at the node (which it isn't), then it doesn't matter what it is pointing at, those things can still be collected, so this is just a performance concern.
• Alejandro: In the original code the popped node will be garbage collected, as nothing else than the top field refers to it, and that reference will go away as soon as the new top is assigned, making the old top eligible for GC in that line.