Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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];
    }
}
share|improve this question
    
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.) –  EBrown yesterday
1  
Try writing a Stack backed by a linked list. That's two data structures in one exercise, it's also surprisingly elegant. –  RobH yesterday
    
For the purposes of cheating: Stack<T> implementation in System.Collections.Generic –  Nathan Cooper 9 hours ago

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
1  
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 –  holroy yesterday
    
True, my pop method has a problem too! –  TopinFrassi yesterday
1  
That ArgumentException should be an ArgumentOutOfRangeException. –  Pharap 14 hours ago
    
@Pharap I fixed it! –  TopinFrassi 7 hours ago

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.

share|improve this answer
2  
To elaborate on the point of being limited to integers, you could fix that by using generics @Anatoly. –  RubberDuck yesterday
    
Is is not possible to push a 0 to the stack ... without keeping an index variable. just thought that was a bit unclear. –  Rotem yesterday
    
@Rotem basically it is possible by using a nullable. –  Heslacher yesterday
    
@Heslacher While technically correct, it feels wrong to recommend that course of action in this learning exercise. –  Rotem yesterday
    
Thats why I didn't ;-) –  Heslacher yesterday

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;
    }
}
share|improve this answer
    
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 –  holroy yesterday
    
@holroy, for #1, I know that. The OP's code also throws exception in this case. I was only addressing the pointer comment. –  user2023861 yesterday
    
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. –  holroy yesterday
1  
@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. –  user2023861 yesterday
    
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). –  CodesInChaos 3 hours ago

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;
    }
}   
share|improve this answer
5  
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. –  CodesInChaos yesterday
    
@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. –  David Arno yesterday
    
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. –  CodesInChaos yesterday
    
A stack implementation is not in any way defined to be popping/pushing at the head. It could just as well be at the end. The key point is that you pop the element which was pushed last. An array implementation is one of many effective and useful implementations. Inserting at the front however is not a good idea, in most cases. –  holroy yesterday
    
@holroy I accept that, which is why I modified the code to insert/remove from the end of the list. –  David Arno yesterday

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.