4
\$\begingroup\$

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];
    }
}
\$\endgroup\$
  • \$\begingroup\$ You should consider adding some more information at the begging of your posts. (Posts that start with code show content as ... on all the summary pages.) \$\endgroup\$ – 410_Gone Sep 29 '15 at 14:33
  • 1
    \$\begingroup\$ Try writing a Stack backed by a linked list. That's two data structures in one exercise, it's also surprisingly elegant. \$\endgroup\$ – RobH Sep 29 '15 at 15:09
  • \$\begingroup\$ For the purposes of cheating: Stack<T> implementation in System.Collections.Generic \$\endgroup\$ – Nathan Cooper Sep 30 '15 at 10:37
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You have an issue, as well, with popping elements of an empty stack. And you can simplify some of the logic if you look at the other answer which is using lastIndex \$\endgroup\$ – holroy Sep 29 '15 at 13:47
  • \$\begingroup\$ True, my pop method has a problem too! \$\endgroup\$ – IEatBagels Sep 29 '15 at 14:01
  • 1
    \$\begingroup\$ That ArgumentException should be an ArgumentOutOfRangeException. \$\endgroup\$ – Pharap Sep 30 '15 at 5:23
  • 1
    \$\begingroup\$ @Pharap I fixed it! \$\endgroup\$ – IEatBagels Sep 30 '15 at 12:28
  • \$\begingroup\$ @TopinFrassi Much better. +1 \$\endgroup\$ – Pharap Oct 6 '15 at 23:21
16
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ To elaborate on the point of being limited to integers, you could fix that by using generics @Anatoly. \$\endgroup\$ – RubberDuck Sep 29 '15 at 11:55
  • \$\begingroup\$ Is is not possible to push a 0 to the stack ... without keeping an index variable. just thought that was a bit unclear. \$\endgroup\$ – Rotem Sep 29 '15 at 14:32
  • \$\begingroup\$ @Rotem basically it is possible by using a nullable. \$\endgroup\$ – Heslacher Sep 29 '15 at 14:33
  • \$\begingroup\$ @Heslacher While technically correct, it feels wrong to recommend that course of action in this learning exercise. \$\endgroup\$ – Rotem Sep 29 '15 at 14:35
4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Two comments: 1) your pop method will try to pop of an empty stack... 2) Not so important, but after popping a value it is still left in the array, which some consider a small security issue \$\endgroup\$ – holroy Sep 29 '15 at 13:38
  • \$\begingroup\$ @holroy, for #1, I know that. The OP's code also throws exception in this case. I was only addressing the pointer comment. \$\endgroup\$ – user2023861 Sep 29 '15 at 13:57
  • \$\begingroup\$ The OPs is asking for review and improvement, so we should aim for excellence or at least comment on faults we notice to help to the best of our knowledge. \$\endgroup\$ – holroy Sep 29 '15 at 14:41
  • 1
    \$\begingroup\$ @holroy, other users have done a good job commenting on other parts of the code. Since no one had yet provided a pointer example, I added one. \$\endgroup\$ – user2023861 Sep 29 '15 at 14:49
  • \$\begingroup\$ I'd expect lastIndex to be the index of the last element in the array, not one beyond it. Either rename it to count or reduce it by one (I prefer the former). \$\endgroup\$ – CodesInChaos Sep 30 '15 at 16:03
3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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;
    }
}   
\$\endgroup\$
  • 5
    \$\begingroup\$ 1) Why would you insert in the front? That turns nice and fast O(1) operations into slow O(n) operations and doesn't simplify the code. 2) The OP is reinventing the wheel for learning purposes, this approach eliminates pretty much all the interesting parts. \$\endgroup\$ – CodesInChaos Sep 29 '15 at 13:09
  • \$\begingroup\$ @CodesInChaos, 1) fair point. I did it that way as a stack adds/removes from the head, so I made the code do the same. I've updated the answer though to make it more efficient. 2) I disagree. The key to a stack is the way it pushes and pops to the head. The array implementation was just implementation noise. \$\endgroup\$ – David Arno Sep 29 '15 at 13:17
  • \$\begingroup\$ A stack is pretty much the simplest collection you can use to learn how to implement a variable size collection on top of a fixed size array. You could re-implement List<T> instead, but it includes far more irrelevant features. \$\endgroup\$ – CodesInChaos Sep 29 '15 at 13:23
  • \$\begingroup\$ @holroy I accept that, which is why I modified the code to insert/remove from the end of the list. \$\endgroup\$ – David Arno Sep 29 '15 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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