up vote 6 down vote favorite

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++;
        }
    }
}
share|improve this question
up vote 5 down vote accepted

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.
share|improve this answer
up vote 3 down vote

Even though it's internal in it's 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 surly 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.

share|improve this answer
up vote 0 down vote 
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;
share|improve this answer
    
It will reduce performance. In memory/speed trade-off requirement prefers speed. – Joan Dimko 18 hours ago
    
@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 18 hours ago
1  
@JoanDimko do you have or did you do any performance tests? – t3chb0t 18 hours ago
2  
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. – VisualMelon 14 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.