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.}

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;