12
\$\begingroup\$

I have a exercise where I have to write a Stack class with the push and pop methods. The code compiles and works as it should. Are there better practices to use in my code? Is there something I should avoid doing?

public class Stack {

    private final int INCREMENTSIZE = 1024;
    Integer position = 0;

    int[] list = null;

    public Stack(){
        list = new int[INCREMENTSIZE];
    }

    public void push(Integer i) {
        if(position == list.length) {
            list = Arrays.copyOf(list, list.length + INCREMENTSIZE);
        }
        list[position++] = i;
    }

    public Integer pop(){
        return list[--position];
    }
}
\$\endgroup\$
  • 6
    \$\begingroup\$ Your stack grows and never shrinks... \$\endgroup\$ – Boris the Spider Sep 8 at 20:59
  • 2
    \$\begingroup\$ class Stack extends LinkedList<Integer> {} Ought to pass all your tests. No responsibility taken for your marks, but I'd give you 100% as an employee for not reinventing a very old wheel. \$\endgroup\$ – Rich Sep 9 at 4:21
  • 7
    \$\begingroup\$ @Rich Except that extending linked list allows the stack's contract to be broken. It would be usable only as a strictly class private data structure, at which point having a separate name for it makes no sense at all. I would reject that merge request. \$\endgroup\$ – TorbenPutkonen Sep 9 at 5:46
  • \$\begingroup\$ @TorbenPutkonen: All contracts can be broken by someone determined enough to do so. (For example, if your nice and well-behaved Stack class isn't final, someone could extend it and make the subclass do whatever they want. Or there's always reflection.) But I do agree that renaming a perfectly ordinary LinkedList into something else is pointless. (For that matter, using LinkedList for anything is usually a poor choice anyway — at least 99% of the time ArrayList is just as good or better.) \$\endgroup\$ – Ilmari Karonen Sep 10 at 9:44
  • \$\begingroup\$ @IlmariKaronen That's a bit useless hair splitting. Every contract can be broken via security flaws. Point is wheter breaking the contract is by design or by "malicious" use. \$\endgroup\$ – TorbenPutkonen Sep 12 at 6:04
18
\$\begingroup\$

Other answers correctly point out that using primitive types and not mixing them with Objects (=int instead of Integer), reducing visibility wherever possible (=adding private modifier to position and list) and preventing popping from empty stack are good practices. There are a few more subtleties which can be improved:

  1. Rename INCREMENTSIZE to INCREMENT_SIZE. It's customary, when naming constants using full caps, to separate words with underscores.
  2. Consider growing a stack by multiplying current size and start small, e.g. instead having new size be current+increment, make it current*factor, where factor can be 1.5 or 2, or even decreased as the stack grows. If you're implementing a general purpose stack, you don't know how small or large the user will want it to be—incrementing by a constant might be an overkill or too small, while starting small and growing it in multiples will conserve memory if user needs a small stack, and will grow it in large enough increments later on if user needs to store many elements. The two approaches can be mixed and fine-tuned for best performance.
  3. Consider generifying the stack class so it can be a stack of anything, not just Integers. It's a small cost, but can be of large benefit.
  4. If you do store arbitrarily typed objects, beware of memory leaks! The pop function as it stands won't free memory if a user decides to empty the stack. It's a merely unconservative approach when dealing with primitives or small, usually pooled Integers. It can be a real problem when storing something heavyweight—your stack will keep a reference to something which the user has popped and prevent the garbage collector from collecting it (also see Effective Java 3rd ed., Item 7). To prevent this, when popping an element, set the value of the popped element in array to null; additionally when a considerable proportion of the array is empty, deallocate a portion of it (e.g. using the Arrays.copyOf with a smaller second argument).
  5. Guard against overflows. At some point, list.length + INCREMENTSIZE will overflow, and you'll get NegativeArraySizeException from Arrays#copyOf. Unfortunately, you can't have arrays which are indexed by longs, so best you can do is use Integer.MAX_VALUE as the new size, and throw an exception (e.g. IllegalStateException with a helpful message) if the caller wants to add more items to stack after it's grown to MAX_VALUE. You can see how ArrayDeque#grow(int) and ArrayDeque#newCapacity(int, int) are implemented by OpenJDK here.
\$\endgroup\$
  • 4
    \$\begingroup\$ To add to your point 2: the factor approach is asymptotically faster. As written in OP using a fixed increment, push is O(n). Using a factor like you've described makes it amortized O(1). \$\endgroup\$ – Adam Sep 9 at 5:30
12
\$\begingroup\$

This looks good, However I suggest you properly indent the code.

Further suggestions:

I would change following

private final int INCREMENTSIZE = 1024;

to

private static final int INCREMENTSIZE = 1024;

Since you are not changing this in the constructor (to a new value) we might as well make it unique for the whole class.

I would change following

Integer position = 0;

to

private int position = 0;

There is no reason to have an Integer when int will do. We can also make it private.

For push and pop functions you can also use int's instead of Integer.

\$\endgroup\$
11
\$\begingroup\$

Your class is small and does what you said it should, that's good.
However, there are a few things you could do better.

1. Use primitive types unless the boxed ones are specifically needed:

You are using the Integer type for counting the position and storing/returning data. If you actually used the fact, that it could be null, this would be acceptable use. However, any instance of null would break your code here. You are storing your integers in an int[], a primitive integer array. This leads to unboxing and a null reference will break your code.
A position of null (not zero 0) also isn't making any sense in the context of your class.

Use int instead of Integer unless you actually need null references.

2. Reduce the visibility of member fields

Other classes inside the same package as your class typically don't need access to your internal array. Make that array private.

3. Think about what you want to store in your stack.

Currently your stack only allows storing primitive ints. Maybe think about storing any type of data using generics. Extending your current class wouldn't be difficult.

Other than that: Your code is concise, not too complicated and serves its purpose. Think about formatting the code using your IDE's formatter and add comments and documentation to your code.

\$\endgroup\$
5
\$\begingroup\$

Your class is good (for me I would rename the variable list as arr), but you should consider case where you call pop on an empty stack. In this case your method could throw an exception like the code below:

public Integer pop(){
   if (position == 0) throw new RuntimeException("Empty Stack");
   return list[--position];
}

You can check from Java documentation that Stack pop() throws EmptyStackException, subclass of RuntimeException.

\$\endgroup\$
  • \$\begingroup\$ INCREMENTSIZE is an unfortunate name for a full stack :p \$\endgroup\$ – dfhwze Sep 8 at 16:38
  • 1
    \$\begingroup\$ @dfhwze lol, I realized now there is plenty of double meanings in my answer. \$\endgroup\$ – dariosicily Sep 8 at 16:50
  • 4
    \$\begingroup\$ There is no sich thing as a Full stack in the original code \$\endgroup\$ – eckes Sep 8 at 16:57
  • 1
    \$\begingroup\$ You need to remove the first line of your push method (as @eckes is suggesting). Please note what the push method is doing in the original code and you will see why. Cheers. \$\endgroup\$ – Ray Toal Sep 8 at 18:43
  • \$\begingroup\$ The general idea of this answer, that one should make sure to handle edge cases like popping from an empty stack, is valid and worth pointing out. The specific advice and code you've suggested has several errors, however, and you appear not to have understood what the code you quoted and modified actually does. \$\endgroup\$ – Ilmari Karonen Sep 8 at 19:27
3
\$\begingroup\$

In addition to what other's have said:

Your constant-increment growth scheme causes push operations to be amortized O(n). You should grow by a constant factor, as ArrayList does (1.5x, if I recall correctly). Even better, just don't use a primitive array at all, and use ArrayList instead.

\$\endgroup\$

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.