Stack implementation in C#

Question

I started to learn data structures. How can I improve my implementation? For example, I don't now how to push 0 or how to realize my own resize.

public class Stack: IStack
{
    private int[] s;

    public Stack(int N)
    {
        s = new int[N];
    }

    public void push(int x)
    {
        int i = 0;
        while (s[i] != 0)
        {
            ++i;
        }

        if (i+1 >= s.Length)
        {
            Array.Resize(ref s, s.Length*2);
        }

        s[i] = x;
    }

    public int pop()
    {
        int i = 0;

        while (i != s.Length && s[i] != 0)
        {
            i++;
        }

        s[i] = 0;
        return s[i - 1];
    }
}

Answer 1

Your stack is just one step away from being generic, which is great. I don't know if it's useful to you but usually, data structures are generics!

In the initialisation, I could pass -102 as a paramter to your Stack's length, which is flawed.

There's a bug in your push method. If I create new Stack(0), an IndexOutOfRangeException will be thrown when I push something, since you start with s[0]. But in the other cases, you expand your array to make sure you don't have an exception. This might not be a bug, but you should think about this behavior. Plus, expanding your array with a 0 length wouldn't work, since 0*2=0

As @holroy pointed out in the comments (I'm adding it to my answer just because he/she didn't post an answer yet), you're going to throw an exception if you try to pop an empty stack. To counter this, I added a check before popping!

If my Stack contains : {1,2,3}, I'm going to pop the value 3, and return 2. The expected behavior would be to return 3 since it's the poped value.

Also, instead of looping all the time to find the index to insert or pop in your stack, why don't you just keep this index as a private member of your class? You'll save useless while loops and conditions.

There goes the final result :

public class Stack<T>: IStack<T>
{
    private T[] s;
    private int currentStackIndex;

    public Stack(int N)
    {
        if(N < 0)
            throw new ArgumentOutOfRangeException("N");

        s = new T[N];
        currentStackIndex = 0;
    }

    public void push(T x)
    {
        if (currentStackIndex + 1 >= s.Length)
        {
            //Notice the + 1, to counter the 0 length problem
            Array.Resize(ref s, (s.Length + 1)*2);
        }

        s[currentStackIndex++] = x;
    }

    public T pop()
    {
        if(currentStackIndex == 0)
            throw new InvalidOperationException("The stack is empty");

        T value = s[--currentStackIndex]; 
        s[currentStackIndex] = default(T);
        return value;
    }
}

I didn't talk about the naming since it's already covered.

Answer 2

There are some problems with your code, especially

• Naming

  Names like s, N or x won't tell much about what they are used for. So maby slot, size and value would be a better fit.

• It is not possible to push a 0 to the stack

• The Stack is limited to only integers. If you want to push a decimal or a SomeClass you just can't.

• Conventions

  The default naming conventions for C# is to use PascalCase casing for naming methods, so push and pop should be Push and Pop.

  Read: Naming guidelines for NET

• You really should take care of the index of the last inserted value. This makes it easier and better to maintain if you need to pop or push.

Answer 3

Going off your question about pushing zeroes onto the stack, another user mentioned that you should keep an index into the stack to remember where to push and pop. I've updated your code only addressing that point:

Notice a couple of points:

• You can insert zeroes. Notice in the code that I don't compare the values in the array to 0 anywhere. I instead use the lastIndex integer as a pointer into the stack.
• In both the push() and pop() methods, I removed your while loops while keeping the functionality. Your methods ran in linear time because of these loops. My versions run in constant time (except for the array resize).

Code:

public class MyStack
{
    private int[] s;
    private int lastIndex = 0;

    public MyStack(int N)
    {
        s = new int[N];
    }

    public void push(int x)
    {
        //no need for your while loop

        //this condition replaces your "i + 1 >= s.Length" condition
        if (lastIndex == s.Length)
        {
            Array.Resize(ref s, s.Length * 2);
        }

        //replaces your "s[i] = x"
        s[lastIndex] = x;

        //this updates the pointer to where the next push will be
        lastIndex++;
    }

    public int pop()
    {
        //This moves the pointer to the newest item
        lastIndex--;

        //This replaces your while loop
        int result = s[lastIndex];

        return result;
    }
}

Answer 4

Style and code review

Some comments on your original code:

• Good indentation – You are consistent, and the code looks generally good
• Documentation, not so good – This is a small code base, but it is always good to add some documentation to your code. Although, do not comment or document the obvious.
• Method naming – As commented in another option, it is common in c# code to use PascalCase() for methods
• Variable naming – In many of the environment we used the following rules for variable naming: _privateVariable, PropertyVariable and localVariable. Distinguishing the scope using naming, helps reading of the code as you easily see whether it is a private, public or local variable directly. Code like the following is quite readable using this scheme:

public class SomeClass
{
    private int _someVariable;
    public SomeVariable { get; private set; }

    public SomeClass(someVariable) 
    {
        _someVariable = someVariable;
    }
}

• Use clear and informative names – According to previous point, and increase readability I would've changed s to _stack
• Always look at edge cases – In your case: What will happen if you push beyond the requested capacity? What will happen if initialising with a negative size? What will happen if you pop from an empty stack?
  • Negative initialisation – Not handled, should most likely thrown an exception
  • Push beyond requested capacity – Is handled by doubling array size. This can be dangerous if it happens a few times... Generally I would rather add 10% or 20%, which will grow somewhat better without requiring all memory in due time. Possibly you should/could have some fail safe mechanism if/when the Array.Resize() fails
  • Pop from empty stack – Not handled, will most likely cause an exception as you return s[-1]
• Consider going generic – This datastructure is quite useful for a lot of other cases than merely a stack of int's

Your questions

Pushing 0 is not possible

You are correct, and this is a good reason why you shouldn't use magic numbers like 0. Some options exists to fix this issue:

• Use a nullable type internally, and check for nul instead of 0
• Use a reference to indicate where your stack is currently (as suggested in some of the other answers). This could/would also reduce complexity seriously, as you could drop the loops and use the reference directly
• Change to another magic number, which would just shift the problem

Realise your own resize

Why would you want do this? You are already relying on the native array, so I don't see the issue in using the native approach for resizing.

However some options to handle resizing issues, or implementing your own version here:

• You could maintain multiple internal lists, i.e. an array of references to other Stack's. Not recommended though.
• You could switch your storage to using a linked list, which wouldn't have the same issues regarding memory usage.
• You could disallow memory usage outside the intially requested amount. If someone tries to push when it's full you could throw an exception.

Code refactoring

My refactored code is a combination of some of the other answers, with my names and error handling, and an example section to show how to use the generic version of this.

public class Stack<T>
{
    private T[] _stack;
    private int _nextFreeStackIndex;

    public int StackSize { get { return _stack.Length; } }

    public Stack(int stackSize)
    {
        if(stackSize < 0)
            throw new ArgumentOutOfRangeException("Requires a positive stack size");

        _stack = new T[stackSize];
        _nextFreeStackIndex = 0;
    }

    public void Push(T value)
    {
        // Don't reallocate before we actually want to push to it
        if (_nextFreeStackIndex == _stack.Length)
        {
            // Double for small stacks, and increase by 20% for larger stacks
            Array.Resize(ref _stack, _stack.Length < 100 
                                         ? 2*_stack.Length 
                                         : (int) (_stack.Length * 1.2));
        }

        // Store the value, and increase reference afterwards
        _stack[_nextFreeStackIndex++] = value;
    }

    public T Pop()
    {
        if(_nextFreeStackIndex == 0)
            throw new InvalidOperationException("The stack is empty");

        // Decrease the reference before fetching the value as
        // the reference points to the next free place
        T returnValue = _stack[--_nextFreeStackIndex]; 

        // As a safety/security measure, reset value to a default value
        _stack[_nextFreeStackIndex] = default(T);

        return returnValue;
    }
}

And here is some code showing how to instantiate it when using generics:

    public static void TestStack() {

        try {
            new Stack<int>(-500);
        } catch (ArgumentOutOfRangeException) {
            Console.WriteLine("Hooray, couldn't create a negative sized stack");
        }

        var myStack = new Stack<int>(3);

        try {
            myStack.Pop();
        } catch (InvalidOperationException) {
            Console.WriteLine("Hooray, it was empty and failed. :-)");
        }

        myStack.Push(1);
        myStack.Push(2);
        var popped = myStack.Pop();
        if (popped == 2) {
            Console.WriteLine("Yuhu... Found the value I pushed! :-D ");
        }

        myStack.Push(0);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);
        myStack.Pop(); myStack.Pop(); myStack.Pop();

        Console.WriteLine(String.Format("My final write: pop={0}, size={1}", myStack.Pop(), myStack.StackSize));
    }

Which gave the following expected output:

Hooray, couldn't create a negative sized stack
Hooray, it was empty and failed. :-)
Yuhu... Found the value I pushed! :-D 
My final write: pop=0, size=6

Answer 5

You are using an array and creating complex code to manage that. If you switch to using a List<T> you can make the code both generic and a lot simpler:

public class Stack<T>: IStack<T>
{
    private List<T> stack = new List<T>();

    public void Push(T item)
    {
        stack.Add(item);
    }

    public T Pop()
    {
        if (stack.Count == 0)
        {
            throw Exception("Stack is empty");
        }

        var lastElementInList = stack.Count-1;
        var itemAtTopOfStack = stack[lastElementInList];
        stack.RemoveAt(lastElementInList);
        return itemAtTopOfStack;
    }
}